Ordering 3dpoints ?

TIG

http://en.wikipedia.org/wiki/Graham_scan ?
Ensures 'convex' shapes...

thomthom

@tig said:

http://en.wikipedia.org/wiki/Graham_scan ?
Ensures 'convex' shapes...

I got an implementation of Grahams Scan in TT_Lib (version 1)
From geom2d.rb

<span class="syntaxdefault"><br /></span><span class="syntaxcomment"># Graham's Scan<br /># Computational Geometry Algorythms and Appliations (ISBN-10; 3540779736)<br /># Chapter 1.1<br />#<br /># @param [Array<Geom;;Point3d>] points<br /># @return [Array<Geom;;Point3d>]<br /># @since 1.1.0<br /></span><span class="syntaxdefault">def self</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">convex_hull</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">points</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">  return nil if points</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">length </span><span class="syntaxkeyword"><</span><span class="syntaxdefault"> 2<br />  <br />  points </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> self</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">sort_points_by_x_y</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">points</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">  <br />  l_upper </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">[</span><span class="syntaxdefault"> points</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">0</span><span class="syntaxkeyword">],</span><span class="syntaxdefault"> points</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">1</span><span class="syntaxkeyword">]</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">]<br /></span><span class="syntaxdefault">  2</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">upto</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">points</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">length </span><span class="syntaxkeyword">-</span><span class="syntaxdefault"> 1</span><span class="syntaxkeyword">)</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">{</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">|</span><span class="syntaxdefault">i</span><span class="syntaxkeyword">|<br /></span><span class="syntaxdefault">    l_upper </span><span class="syntaxkeyword"><<</span><span class="syntaxdefault"> points</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">i</span><span class="syntaxkeyword">]<br /></span><span class="syntaxdefault">    while l_upper</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">length </span><span class="syntaxkeyword">></span><span class="syntaxdefault"> 2 </span><span class="syntaxkeyword">&&</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">!</span><span class="syntaxdefault">self</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">right_turn</span><span class="syntaxkeyword">?(</span><span class="syntaxdefault">l_upper</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">last</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">3</span><span class="syntaxkeyword">))<br /></span><span class="syntaxdefault">      l_upper</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">delete_at</span><span class="syntaxkeyword">(-</span><span class="syntaxdefault">2</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">    end<br />  </span><span class="syntaxkeyword">}<br /></span><span class="syntaxdefault">  <br />  l_lower </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">[</span><span class="syntaxdefault"> points</span><span class="syntaxkeyword">[-</span><span class="syntaxdefault">1</span><span class="syntaxkeyword">],</span><span class="syntaxdefault"> points</span><span class="syntaxkeyword">[-</span><span class="syntaxdefault">2</span><span class="syntaxkeyword">]</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">]<br /></span><span class="syntaxdefault">  </span><span class="syntaxkeyword">(</span><span class="syntaxdefault">points</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">length </span><span class="syntaxkeyword">-</span><span class="syntaxdefault"> 3</span><span class="syntaxkeyword">).</span><span class="syntaxdefault">downto</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">0</span><span class="syntaxkeyword">)</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">{</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">|</span><span class="syntaxdefault">i</span><span class="syntaxkeyword">|<br /></span><span class="syntaxdefault">    l_lower </span><span class="syntaxkeyword"><<</span><span class="syntaxdefault"> points</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">i</span><span class="syntaxkeyword">]<br /></span><span class="syntaxdefault">    while l_lower</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">length </span><span class="syntaxkeyword">></span><span class="syntaxdefault"> 2 </span><span class="syntaxkeyword">&&</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">!</span><span class="syntaxdefault">self</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">right_turn</span><span class="syntaxkeyword">?(</span><span class="syntaxdefault">l_lower</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">last</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">3</span><span class="syntaxkeyword">))<br /></span><span class="syntaxdefault">      l_lower</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">delete_at</span><span class="syntaxkeyword">(-</span><span class="syntaxdefault">2</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">    end<br />  </span><span class="syntaxkeyword">}<br /></span><span class="syntaxdefault">  l_lower</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">delete_at</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">0</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">  l_lower</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">delete_at</span><span class="syntaxkeyword">(-</span><span class="syntaxdefault">1</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">  <br />  return l_upper </span><span class="syntaxkeyword">+</span><span class="syntaxdefault"> l_lower<br />end<br /><br /><br /></span><span class="syntaxcomment"># Lexicographic order x, y<br />#<br /># @param [Array<Geom;;Point3d>] points<br /># @return [Array<Geom;;Point3d>]<br /># @since 1.1.0<br /></span><span class="syntaxdefault">def self</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">sort_points_by_x_y</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">points</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">  return points</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">sort </span><span class="syntaxkeyword">{</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">|</span><span class="syntaxdefault">a</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">b</span><span class="syntaxkeyword">|</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">(</span><span class="syntaxdefault">a</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">x</span><span class="syntaxkeyword">==</span><span class="syntaxdefault">b</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">x</span><span class="syntaxkeyword">)</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">?</span><span class="syntaxdefault"> a</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">y </span><span class="syntaxkeyword"><=></span><span class="syntaxdefault"> b</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">y </span><span class="syntaxkeyword">;</span><span class="syntaxdefault"> a</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">x </span><span class="syntaxkeyword"><=></span><span class="syntaxdefault"> b</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">x </span><span class="syntaxkeyword">}<br /></span><span class="syntaxdefault">end<br /></span>

Didier Bur

Thanks TIG and TT, I was just starting coding Graham's scan, this will save me time.
Left turn/right turn and cross products will do the trick I presume.

What's all that for: I'm working on subdivision curves and surfaces: Catmull-Clark, Loop, Doo-Sabin, Peters-Reif, Kobbelt, Chaikin, and others. Peters-Reif seemed too me the simplest algorithm but turned out to be one of the most complex, comparing to Catmull which I have coded in an hour or so.
I'm facing the CW/CCW and ordering problem, and the 'correctly orienting faces' problem. That's fun

@TT: didn't you encounter problems with == method when comparing Floats (in (a.x==b.x) for instance) ?
I've come across this:

plane1=Geom.fit_plane_to_points(pArray[0],pArray[1],pArray[2])
plane2=(Geom.fit_plane_to_points(pArray[0],pArray[1],pArray[3]))
return plane1==plane2

Assuming the 4 3dPoints are coplanar, this always return false. I had to code another method 'isEqual?' for the Float class that compares with a tolerance of 1 to the power of -10 to get correct results when comparing such arrays of floats.

thomthom

@didier bur said:

@TT: didn't you encounter problems with == method when comparing Floats (in (a.x==b.x) for instance) ?

Good point. I haven't tested it that much, I just ported some pseudo code which I read in a book.
One should probably do a tolerance comparison.

[quote="Didier Bur"]


    plane1=Geom.fit_plane_to_points(pArray[0],pArray[1],pArray[2])
    plane2=(Geom.fit_plane_to_points(pArray[0],pArray[1],pArray[3]))
    return plane1==plane2

<span class="syntaxdefault"><br /></span><span class="syntaxcomment">#&nbsp;Check&nbsp;if&nbsp;all&nbsp;points&nbsp;in&nbsp;the&nbsp;array&nbsp;are&nbsp;on&nbsp;the&nbsp;same&nbsp;plane.<br />#<br />#&nbsp;@todo&nbsp;Ensure&nbsp;that&nbsp;the&nbsp;first&nbsp;three&nbsp;points&nbsp;are&nbsp;not&nbsp;co-linear.<br />#<br />#&nbsp;@param&nbsp;[Array<Geom;;Point3d>]&nbsp;points<br />#<br />#&nbsp;@since&nbsp;2.0.0<br /></span><span class="syntaxdefault">def&nbsp;self</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">planar_points</span><span class="syntaxkeyword">?(</span><span class="syntaxdefault">points</span><span class="syntaxkeyword">)<br />&nbsp;&nbsp;return&nbsp;</span><span class="syntaxdefault">false&nbsp;</span><span class="syntaxkeyword">if&nbsp;</span><span class="syntaxdefault">points</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">length&nbsp;</span><span class="syntaxkeyword"><&nbsp;</span><span class="syntaxdefault">3<br />&nbsp;&nbsp;v1&nbsp;</span><span class="syntaxkeyword">=&nbsp;</span><span class="syntaxdefault">points</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">0</span><span class="syntaxkeyword">].</span><span class="syntaxdefault">vector_to</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">points</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">1</span><span class="syntaxkeyword">])<br />&nbsp;&nbsp;</span><span class="syntaxdefault">v2&nbsp;</span><span class="syntaxkeyword">=&nbsp;</span><span class="syntaxdefault">points</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">0</span><span class="syntaxkeyword">].</span><span class="syntaxdefault">vector_to</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">points</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">2</span><span class="syntaxkeyword">])<br />&nbsp;&nbsp;return&nbsp;</span><span class="syntaxdefault">false&nbsp;unless&nbsp;v1</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">valid</span><span class="syntaxkeyword">?&nbsp;&&&nbsp;</span><span class="syntaxdefault">v2</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">valid</span><span class="syntaxkeyword">?<br />&nbsp;&nbsp;</span><span class="syntaxdefault">vector&nbsp;</span><span class="syntaxkeyword">=&nbsp;</span><span class="syntaxdefault">v1&nbsp;</span><span class="syntaxkeyword">*&nbsp;</span><span class="syntaxdefault">v2<br />&nbsp;&nbsp;plane&nbsp;</span><span class="syntaxkeyword">=&nbsp;[&nbsp;</span><span class="syntaxdefault">points</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">0</span><span class="syntaxkeyword">],&nbsp;</span><span class="syntaxdefault">vector&nbsp;</span><span class="syntaxkeyword">]<br />&nbsp;&nbsp;</span><span class="syntaxdefault">3.upto</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">points</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">length</span><span class="syntaxkeyword">-</span><span class="syntaxdefault">1</span><span class="syntaxkeyword">)&nbsp;{&nbsp;|</span><span class="syntaxdefault">i</span><span class="syntaxkeyword">|<br />&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;</span><span class="syntaxdefault">false&nbsp;unless&nbsp;points</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">i</span><span class="syntaxkeyword">].</span><span class="syntaxdefault">on_plane</span><span class="syntaxkeyword">?(</span><span class="syntaxdefault">plane</span><span class="syntaxkeyword">)<br />&nbsp;&nbsp;}<br />&nbsp;&nbsp;return&nbsp;</span><span class="syntaxdefault">true<br />end<br /></span>

thomthom

@didier bur said:

What's all that for: I'm working on subdivision curves and surfaces: Catmull-Clark, Loop, Doo-Sabin, Peters-Reif, Kobbelt, Chaikin, and others. Peters-Reif seemed too me the simplest algorithm but turned out to be one of the most complex, comparing to Catmull which I have coded in an hour or so.

I wish I could understand algorithm formulas. I always need to search up a pseudo code version, or an implementation in another language to work it out.

thomthom

@didier bur said:

@TT: didn't you encounter problems with == method when comparing Floats (in (a.x==b.x) for instance) ?

Actually, Point3d.x, Point3d.y and Point3d.z return Length objects. They have built in tolerances - same as SU's.
You can easily get in trouble with unpredictable results if you're not 100% sure if you're dealing with Floats or Lengths.

Didier Bur

@unknownuser said:

I wish I could understand algorithm formulas. I always need to search up a pseudo code version, or an implementation in another language to work it out.

Me too. When I speak of 'algorithm' I mean pseudo-code or (even better) natural language

Here is my snippet for coplanarity test of 4 points (can be extended to any number of points):

# Given a set of 4 3dPoints, return true if coplanar, or false
	def quadPointsCoplanar?(pArray)
		return (Geom.fit_plane_to_points(pArray[0],pArray[1],pArray[2]).isEqual?(Geom.fit_plane_to_points(pArray[0],pArray[1],pArray[3])))
	end

Where Array of floats comparison method must be 'aliased' with isEqual?

class Array
	def isEqual?(otherArray)
		self.each_index { |i| return false if self[i].isNotEqual(otherArray[i]) }
		return true
	end
end

and where == method for floats must be aliased with isNotEqual()

class Float
	def isNotEqual(value)
		delta = self - value
		return ((delta > Math;;EPSILON) or (delta < -Math;;EPSILON))
	end
end

and finaly requires a constant

Math.const_set("EPSILON", 1.0e-10)

thomthom

I came across a very good site on the topic of floating precision: http://floating-point-gui.de/
Comparison with tolerance is a bit more complex in order to account for the various pit-falls.

The Floating-Point Guide - Comparison

Explanation of the various pitfalls in comparing floating-point numbers.

(floating-point-gui.de)

thomthom

Ooops! Seems that I forgot to post all required methods:

<span class="syntaxdefault"><br />module TT_Lib<br /> module Geom2D<br />  <br />  </span><span class="syntaxcomment"># Graham's Scan<br /></span><span class="syntaxdefault">  </span><span class="syntaxcomment"># Computational Geometry Algorythms and Appliations (ISBN-10; 3540779736)<br /></span><span class="syntaxdefault">  </span><span class="syntaxcomment"># Chapter 1.1<br /></span><span class="syntaxdefault">  </span><span class="syntaxcomment">#<br /></span><span class="syntaxdefault">  </span><span class="syntaxcomment"># @param [Array<Geom;;Point3d>] points<br /></span><span class="syntaxdefault">  </span><span class="syntaxcomment"># @return [Array<Geom;;Point3d>]<br /></span><span class="syntaxdefault">  </span><span class="syntaxcomment"># @since 1.1.0<br /></span><span class="syntaxdefault">  def self</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">convex_hull</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">points</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">    return nil if points</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">length </span><span class="syntaxkeyword"><</span><span class="syntaxdefault"> 2<br />    <br />    points </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> self</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">sort_points_by_x_y</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">points</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">    <br />    l_upper </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">[</span><span class="syntaxdefault"> points</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">0</span><span class="syntaxkeyword">],</span><span class="syntaxdefault"> points</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">1</span><span class="syntaxkeyword">]</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">]<br /></span><span class="syntaxdefault">    2</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">upto</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">points</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">length </span><span class="syntaxkeyword">-</span><span class="syntaxdefault"> 1</span><span class="syntaxkeyword">)</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">{</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">|</span><span class="syntaxdefault">i</span><span class="syntaxkeyword">|<br /></span><span class="syntaxdefault">      l_upper </span><span class="syntaxkeyword"><<</span><span class="syntaxdefault"> points</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">i</span><span class="syntaxkeyword">]<br /></span><span class="syntaxdefault">      while l_upper</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">length </span><span class="syntaxkeyword">></span><span class="syntaxdefault"> 2 </span><span class="syntaxkeyword">&&</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">!</span><span class="syntaxdefault">self</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">right_turn</span><span class="syntaxkeyword">?(</span><span class="syntaxdefault">l_upper</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">last</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">3</span><span class="syntaxkeyword">))<br /></span><span class="syntaxdefault">        l_upper</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">delete_at</span><span class="syntaxkeyword">(-</span><span class="syntaxdefault">2</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">      end<br />    </span><span class="syntaxkeyword">}<br /></span><span class="syntaxdefault">    <br />    l_lower </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">[</span><span class="syntaxdefault"> points</span><span class="syntaxkeyword">[-</span><span class="syntaxdefault">1</span><span class="syntaxkeyword">],</span><span class="syntaxdefault"> points</span><span class="syntaxkeyword">[-</span><span class="syntaxdefault">2</span><span class="syntaxkeyword">]</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">]<br /></span><span class="syntaxdefault">    </span><span class="syntaxkeyword">(</span><span class="syntaxdefault">points</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">length </span><span class="syntaxkeyword">-</span><span class="syntaxdefault"> 3</span><span class="syntaxkeyword">).</span><span class="syntaxdefault">downto</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">0</span><span class="syntaxkeyword">)</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">{</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">|</span><span class="syntaxdefault">i</span><span class="syntaxkeyword">|<br /></span><span class="syntaxdefault">      l_lower </span><span class="syntaxkeyword"><<</span><span class="syntaxdefault"> points</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">i</span><span class="syntaxkeyword">]<br /></span><span class="syntaxdefault">      while l_lower</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">length </span><span class="syntaxkeyword">></span><span class="syntaxdefault"> 2 </span><span class="syntaxkeyword">&&</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">!</span><span class="syntaxdefault">self</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">right_turn</span><span class="syntaxkeyword">?(</span><span class="syntaxdefault">l_lower</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">last</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">3</span><span class="syntaxkeyword">))<br /></span><span class="syntaxdefault">        l_lower</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">delete_at</span><span class="syntaxkeyword">(-</span><span class="syntaxdefault">2</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">      end<br />    </span><span class="syntaxkeyword">}<br /></span><span class="syntaxdefault">    l_lower</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">delete_at</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">0</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">    l_lower</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">delete_at</span><span class="syntaxkeyword">(-</span><span class="syntaxdefault">1</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">    <br />    return l_upper </span><span class="syntaxkeyword">+</span><span class="syntaxdefault"> l_lower<br />  end<br />  <br />  <br />  </span><span class="syntaxcomment"># @param [Array<Geom;;Point3d>] points<br /></span><span class="syntaxdefault">  </span><span class="syntaxcomment"># @return [Array<Geom;;Point3d>]<br /></span><span class="syntaxdefault">  </span><span class="syntaxcomment"># @since 1.1.0<br /></span><span class="syntaxdefault">  def self</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">sort_points_by_x</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">points</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">    return points</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">sort </span><span class="syntaxkeyword">{</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">|</span><span class="syntaxdefault">a</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">b</span><span class="syntaxkeyword">|</span><span class="syntaxdefault"> a</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">x </span><span class="syntaxkeyword"><=></span><span class="syntaxdefault"> b</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">x </span><span class="syntaxkeyword">}<br /></span><span class="syntaxdefault">  end<br />  <br />  <br />  </span><span class="syntaxcomment"># Lexicographic order x, y<br /></span><span class="syntaxdefault">  </span><span class="syntaxcomment">#<br /></span><span class="syntaxdefault">  </span><span class="syntaxcomment"># @param [Array<Geom;;Point3d>] points<br /></span><span class="syntaxdefault">  </span><span class="syntaxcomment"># @return [Array<Geom;;Point3d>]<br /></span><span class="syntaxdefault">  </span><span class="syntaxcomment"># @since 1.1.0<br /></span><span class="syntaxdefault">  def self</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">sort_points_by_x_y</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">points</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">    return points</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">sort </span><span class="syntaxkeyword">{</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">|</span><span class="syntaxdefault">a</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">b</span><span class="syntaxkeyword">|</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">(</span><span class="syntaxdefault">a</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">x</span><span class="syntaxkeyword">==</span><span class="syntaxdefault">b</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">x</span><span class="syntaxkeyword">)</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">?</span><span class="syntaxdefault"> a</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">y </span><span class="syntaxkeyword"><=></span><span class="syntaxdefault"> b</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">y </span><span class="syntaxkeyword">;</span><span class="syntaxdefault"> a</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">x </span><span class="syntaxkeyword"><=></span><span class="syntaxdefault"> b</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">x </span><span class="syntaxkeyword">}<br /></span><span class="syntaxdefault">  end<br />  <br />  <br />  </span><span class="syntaxcomment"># @param [Array<Geom;;Point3d>] points array of 3 +Geom;;Point3d+ objects.<br /></span><span class="syntaxdefault">  </span><span class="syntaxcomment"># @since 1.1.0 - Renamed from +.right_turn+ to +.right_turn?+ at version 1.2.0<br /></span><span class="syntaxdefault">  def self</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">right_turn</span><span class="syntaxkeyword">?(</span><span class="syntaxdefault">points</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">    p</span><span class="syntaxkeyword">,</span><span class="syntaxdefault"> q</span><span class="syntaxkeyword">,</span><span class="syntaxdefault"> r </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> points<br />    array </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">[</span><span class="syntaxdefault"> 1</span><span class="syntaxkeyword">,</span><span class="syntaxdefault"> p</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">x</span><span class="syntaxkeyword">,</span><span class="syntaxdefault"> p</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">y</span><span class="syntaxkeyword">,<br /></span><span class="syntaxdefault">          1</span><span class="syntaxkeyword">,</span><span class="syntaxdefault"> q</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">x</span><span class="syntaxkeyword">,</span><span class="syntaxdefault"> q</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">y</span><span class="syntaxkeyword">,<br /></span><span class="syntaxdefault">          1</span><span class="syntaxkeyword">,</span><span class="syntaxdefault"> r</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">x</span><span class="syntaxkeyword">,</span><span class="syntaxdefault"> r</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">y </span><span class="syntaxkeyword">]<br /></span><span class="syntaxdefault">    return self</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">determinant_3x3</span><span class="syntaxkeyword">(array)</span><span class="syntaxdefault"> </span><span class="syntaxkeyword"><</span><span class="syntaxdefault"> 0.0<br />  end<br />  <br />  </span><span class="syntaxcomment"># @param [Array<Number>] array<br /></span><span class="syntaxdefault">  </span><span class="syntaxcomment"># @return [Number]<br /></span><span class="syntaxdefault">  </span><span class="syntaxcomment"># @since 1.1.0<br /></span><span class="syntaxdefault">  def self</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">determinant_3x3</span><span class="syntaxkeyword">(array)<br /></span><span class="syntaxdefault">    a</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">b</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">c</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">d</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">e</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">f</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">g</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">h</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">i </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> array<br />    return a</span><span class="syntaxkeyword">*</span><span class="syntaxdefault">e</span><span class="syntaxkeyword">*</span><span class="syntaxdefault">i </span><span class="syntaxkeyword">-</span><span class="syntaxdefault"> a</span><span class="syntaxkeyword">*</span><span class="syntaxdefault">f</span><span class="syntaxkeyword">*</span><span class="syntaxdefault">h </span><span class="syntaxkeyword">+</span><span class="syntaxdefault"> b</span><span class="syntaxkeyword">*</span><span class="syntaxdefault">f</span><span class="syntaxkeyword">*</span><span class="syntaxdefault">g </span><span class="syntaxkeyword">-</span><span class="syntaxdefault"> b</span><span class="syntaxkeyword">*</span><span class="syntaxdefault">d</span><span class="syntaxkeyword">*</span><span class="syntaxdefault">i </span><span class="syntaxkeyword">+</span><span class="syntaxdefault"> c</span><span class="syntaxkeyword">*</span><span class="syntaxdefault">d</span><span class="syntaxkeyword">*</span><span class="syntaxdefault">h </span><span class="syntaxkeyword">-</span><span class="syntaxdefault"> c</span><span class="syntaxkeyword">*</span><span class="syntaxdefault">e</span><span class="syntaxkeyword">*</span><span class="syntaxdefault">g<br />  end<br />  <br /> end </span><span class="syntaxcomment"># module Geom2D<br /></span><span class="syntaxdefault">end </span><span class="syntaxcomment"># module TT_Lib<br /></span><span class="syntaxdefault"> </span>

fredo6

@didier bur said:

Here is my snippet for coplanarity test of 4 points (can be extended to any number of points):

# Given a set of 4 3dPoints, return true if coplanar, or false
> 	def quadPointsCoplanar?(pArray)
> 		return (Geom.fit_plane_to_points(pArray[0],pArray[1],pArray[2]).isEqual?(Geom.fit_plane_to_points(pArray[0],pArray[1],pArray[3])))
> 	end

I had a method for that in LibFredo6. Here is the code (slightly modified in order to return the plane or nil)


#Check if a set of points are coplanar
#  --> Return the plane or nil
def G6.points_coplanar?(pts)
	n = pts.length
	return nil if n < 3
	return Geom.fit_plane_to_points(pts) if n == 3
	
	n1 = [n / 2, 3].max
	n2 = [n - n1, 3].max
	plane1 = Geom.fit_plane_to_points *(pts[0..n1-1])
	plane2 = Geom.fit_plane_to_points *(pts[n-n2..n-1])
	normal1 = Geom;;Vector3d.new *plane1[0..2]
	normal2 = Geom;;Vector3d.new *plane2[0..2]
	(normal1.parallel?(normal2) && pts[0].on_plane?(plane2)) ? plane1 ; nil
end

Fredo

PS: I don't think it is a good idea to extend the Array and Float ruby classes. Better used a specific private method


def compare_float_arrays(array1, array2, epsilon)
   for i in 0..array1.length
       return false if (array1[i] - array2[i]).abs > epsilon
   end
   true
end

thomthom

@unknownuser said:

PS: I don't think it is a good idea to extend the Array and Float ruby classes. Better used a specific private method

Ditto. Any Ruby and Sketchup base classes. There's been a few cases with clashes over methods like this.

Dan Rathbun

@unknownuser said:

PS: I don't think it is a good idea to extend the Array and Float ruby classes. Better used a specific private method

And I was going to say the same... and also suggest a compare method with multiple arguemnts.

1) Never extend Ruby base classes, solely to solve one coding challenge that only applies to your project. Use a custom subclass and extend that subclass.
IF you absolutely must have an instance method that acts on the object... then you should create a custom Array subclass and/or a custom Float subclass, and then add your custom methods to those custom classes.

2) Custom classes are never defined at the top level (only Ruby base classes are.) Just because someone else does it, does not mean you should.
Just as Google defined their custom classes inside the modules (Sketchup, UI, Geom,) you should define any custom classes inside your Toplevel module (but they can be nested inside submodules if you wish.)

3) There is an alternative to extending base classes or creating a custom subclass. It's called extending an object. You create a mixin module that has your custom method(s) in it, written as instance methods (not module methods.) Then when you have an INSTANCE object, you extend that specific object via:
require 'epsilon_compare.rb' my_array.extend(EpsilonCompare)
Then that specific array (and only that array,) will have your custom method(s). This way you do not interfere with the rest of the Ruby world's use of the Array class.

4) Sometimes it is necessary to extend or fix a base class for everyone, but this should be done with community approval... and likely for temporary use only, until either the SU API or the Ruby Core can be updated to include the fix or feature. (I'm actually working on such a global fix right now.. but I will post it in the SKX forum for comment and testing. I will not just release it to the Sketchup world, unitl it's tested, proven and approved.)
~

Dan Rathbun

Although == is often overriden in custom subclasses (to do type conversion etc.,) .eql?() is usually not overriden, and retains the original finctionality of the == inherited from the superclass.

Also .equal?() is NEVER overriden! (It's a really big no no.)
~

Jim

moved - ot.

Dan Rathbun

@didier bur said:

Here is my snippet for coplanarity test of 4 points (can be extended to any number of points):

# Given a set of 4 3dPoints, return true if coplanar, or false
> 	def quadPointsCoplanar?(pArray)
> 		return (Geom.fit_plane_to_points(pArray[0],pArray[1],pArray[2]).isEqual?(Geom.fit_plane_to_points(pArray[0],pArray[1],pArray[3])))
> 	end

Will this work to simplify things ?

<span class="syntaxdefault"></span><span class="syntaxcomment"># Given a set of 4 3dPoints, return true if coplanar, or false<br /></span><span class="syntaxdefault">    def quadPointsCoplanar</span><span class="syntaxkeyword">?(</span><span class="syntaxdefault">pArray</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">        return </span><span class="syntaxkeyword">(</span><span class="syntaxdefault">Geom</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">fit_plane_to_points</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">pArray</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">0</span><span class="syntaxkeyword">],</span><span class="syntaxdefault">pArray</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">1</span><span class="syntaxkeyword">],</span><span class="syntaxdefault">pArray</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">2</span><span class="syntaxkeyword">]).</span><span class="syntaxdefault">eql</span><span class="syntaxkeyword">?(</span><span class="syntaxdefault">Geom</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">fit_plane_to_points</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">pArray</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">0</span><span class="syntaxkeyword">],</span><span class="syntaxdefault">pArray</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">1</span><span class="syntaxkeyword">],</span><span class="syntaxdefault">pArray</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">3</span><span class="syntaxkeyword">])))<br /></span><span class="syntaxdefault">    end</span>

I have no problem on Ruby 1.8.6 comparing floats that are very close:
1.0000000001 == 1.0000000002 false 1.0000000001 == 1.0000000001 true

fredo6

I don't think eql? or any float comparison method would work, because the plane defined by [a0, a1, a2, a3] is the same as the one defined by [2 * a0, 2 * a1, 2 * a2, 2 * a3] or any other multiplying factor.

It may be however that Geom.fit_plane_to_points normalizes the returned array, but it is not sure.

So to be on the safe side, both for the precision and for the comparison, I would recommend to compare the planes A[a0, a1, a2, a3] and B[b0, b1, b2, b3] by:

checking if their normals [a0, a1, a2] and [b0, b1, b2] are parallel. SU will answer true or false taking into account the float precision
checking if the first point in the set of points is located on the second plane B.

So, in Dider's example:


def quadPointsCoplanar?(pArray)
   planeA = Geom.fit_plane_to_points pArray[0], pArray[1], pArray[2]
   planeB = Geom.fit_plane_to_points pArray[1], pArray[2], pArray[3]
   normalA = Geom;;Vector3d.new *planeA[0..2]
   normalB = Geom;;Vector3d.new *planeB[0..2]
   normalA.parallel?(normalB) && pArray[0].on_plane?(planeB)
end

Now for 4 points which are different and non-aligned, it is of course easier to do


def quadPointsCoplanar?(pArray)
    planeA = Geom.fit_plane_to_points pArray[0], pArray[1], pArray[2]
    pArray[3].on_plane?(planeA)
end

Fredo

PS to Dan: very instructive your tuto on subclassing, really! Thanks.

Didier Bur

@Dan:
@unknownuser said:

Will this work to simplify things ?
No, it doesn't work.
@all: OK for not adding methods to base classes or SU classes. Module/sub-module stuffs are annoying to code (although the mixin mecanism is fun...) but far more secure.
@tt: your Graham's scan works on every common or horizontal face, but not on vertical faces (I mean sets of 4 points that are in a main vertical plane (red-blue), (green-blue), see pic. I suppose that this is due to points having same X and same Y are not sorted correctly. I've tried to apply a transformation to each point before sorting, and apply the inverse transformation after, but no luck.
This transformation was taking the normal of the plane of the 4 points as the Z axis, so the 4 points were virtually in a horizontal plane to be correctly handled by Graham, which is '2D'.)

Dan Rathbun

@didier bur said:

and finaly requires a constant

Math.const_set("EPSILON", 1.0e-10)

I am not sure I agree with this... I do like constants defined in a module that makes sense.

However... is this constant only to be used by your plugin, Didier ?
If so, it needs to be defined inside your plugin submodule, not a Ruby Core module.

If it is to be used by more than one of your plugins, then it should be defined just inside your toplevel module.

Never define global constants that are really your own private constants.

If you wish.. you can create your own Math submodule but it must be defined as Didier::Math or whatever your toplevel namespace is. If you wish your custom Math module to have everthing the standard Math module has, do this:

<span class="syntaxdefault">module Didier<br />  module Math<br />    include</span><span class="syntaxkeyword">(;;</span><span class="syntaxdefault">Math</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">    const_set</span><span class="syntaxkeyword">(</span><span class="syntaxstring">"EPSILON"</span><span class="syntaxkeyword">,</span><span class="syntaxdefault"> 1.0e-10</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">  end<br />end</span>

** The toplevel operator ( **::**) does not work for Ruby 1.8.0

Now any plugin submodule of Didier when it calls Math, will find your nested custom Math module, instead of the standard one up at the toplevel. Example:this:

<span class="syntaxdefault">module Didier<br />  module WizardPlugin<br />    def self</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">epsilon<br />      return Math</span><span class="syntaxkeyword">;;</span><span class="syntaxdefault">EPSILON<br />    end<br />  end<br />end</span>

~

thomthom

@unknownuser said:

checking if their normals [a0, a1, a2] and [b0, b1, b2] are parallel. SU will answer true or false taking into account the float precision

Comparing normals to check if faces where co-planar caused me problems. Doing what Google recommended, taking all the points and checking if they all lie on the same plane has worked great.

Here's what I got from Simone Nicolo:

@unknownuser said:

I'm afraid that comparing 2 unit vectors (within a tolerance of 0.001") is not NEARLY sufficient to determine of two faces are coplanar. Depending on the size of the faces, it is entirely possible (and in fact probable) that two faces with the same face normal (within tolerance) could be highly coplanar (again, within a tolerance of 0.001").

The correct way to check if 2 faces are coplanar is to collect all the vertices of both faces and check that they all lie in a common plane. One can use the method Geom.fit_plane_to_points to compute a best (least squares fit) plane through all the points and then follow that with calls to Geom.on_plane? for each point to verify that all points lie on the computed plane.

Note:this is the way SketchUp determines if 2 faces are coplanar

thomthom

@didier bur said:

@tt: your Graham's scan works on every common or horizontal face, but not on vertical faces (I mean sets of 4 points that are in a main vertical plane (red-blue), (green-blue), see pic. I suppose that this is due to points having same X and same Y are not sorted correctly. I've tried to apply a transformation to each point before sorting, and apply the inverse transformation after, but no luck.
This transformation was taking the normal of the plane of the 4 points as the Z axis, so the 4 points were virtually in a horizontal plane to be correctly handled by Graham, which is '2D'.)

And that didn't work?
hmm... you'd think that;d work.
Did you use Transformation.axes to transform into 2d? Or some other method?