How to compare points on a plane?

Dan Rathbun

The simpliest means is to use the methods that are inherited by the Array class, from the Enumerable and Comparible mixin modules, along with the built in .x and .y methods of the Geom::Point3d class.

** keep in mind that the function returns the FIRST max.

given some points pt1, pt2, pt3, pt4, pt5 of Geom::Point3d

<span class="syntaxdefault"></span><span class="syntaxkeyword">array=[</span><span class="syntaxdefault">pt1</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">pt3</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">pt2</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">pt4</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">pt5</span><span class="syntaxkeyword">]<br /></span><span class="syntaxcomment"># the Enumerable.max block form using <=>,<br /># returns whatever class the members are.<br /></span><span class="syntaxdefault">x_max_pt </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> array</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">max </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">y_max_pt </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> array</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">max </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">y </span><span class="syntaxkeyword"><=></span><span class="syntaxdefault"> b</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">y </span><span class="syntaxkeyword">}<br /></span><span class="syntaxdefault"> </span>

You can also use Enumerable.min to find the FIRST member with the minimum.

If you wish to know after the above test, if any other points have equal x or y coords ... you will have to again go through the array, using the coord (x or y,) as a test:

<span class="syntaxdefault"></span><span class="syntaxcomment"># Enumerable.find_all returns an Array<br /></span><span class="syntaxdefault">pts_with_max_x </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> array</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">find_all </span><span class="syntaxkeyword">{|</span><span class="syntaxdefault">e</span><span class="syntaxkeyword">|</span><span class="syntaxdefault"> e</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">x </span><span class="syntaxkeyword">==</span><span class="syntaxdefault"> x_max_pt</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">x </span><span class="syntaxkeyword">}<br /></span><span class="syntaxdefault">pts_with_max_y </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> array</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">find_all </span><span class="syntaxkeyword">{|</span><span class="syntaxdefault">e</span><span class="syntaxkeyword">|</span><span class="syntaxdefault"> e</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">y </span><span class="syntaxkeyword">==</span><span class="syntaxdefault"> y_max_pt</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">y </span><span class="syntaxkeyword">}<br /></span><span class="syntaxdefault"> </span>

THEN you'll need to test the resultant array(s) length, to see if you have more than 1 max point, respectively, and do whatever ... make a choice somehow.

Dan Rathbun

FYI.. beware Point3d.< and Point3d.== were overriden in the Geom::Point3d class, and may not give you the same results you'd expect from standard Ruby objects.

Cleverbeans

Since you have the vectors defining your x and y directions, you can get a third by taking their cross product giving you to get the vector normal to the plane giving you a custom z as well. For the purposes of finding the points with maximal custom x and y values you can choose any point in the plane as an origin since the relative position of the other points will not change depending on your selection.

The Transformation.new method can take an origin and three axis as arguments. This transformation can be thought to take the world x,y,z axis and turn them into the custom axis your plane defines. The idea is to transform your points using the inverse of this transformation, which will lay them neatly in the world x-y plane. Then you can find the maximum by comparing the x and y values in the usual way, and then do the transformation on the points once you've identified them to retrieve the points you want. Here is a function which you can tailor to your needs.


def custom_max_x_and_y(custom_x,custom_y,pt_array)
    custom_z = custom_x.cross(custom_y)
    trans = Geom;;Transformation.new(pt_array[0],custom_x, custom_y, custom_z)
    new_points = pt_array.map{|pt| pt.transform(trans.inverse)}
    max_x = new_points[0]
    max_y = new_points[0]
    for pt in new_points
        if pt.x > max_x.x then
		max_x = pt
	end
	if pt.y > max_y.y then
		max_y = pt
	end
    end
    return max_x.transform(trans), max_y.transform(trans)
end

Dan Rathbun

@cleverbeans said:

Then you can find the maximum by comparing the x and y values in the usual way, ...


>     new_points = pt_array.map{|pt| pt.transform(trans.inverse)}
>     max_x = new_points[0]
>     max_y = new_points[0]
>     for pt in new_points
>         if pt.x > max_x.x then
> 		max_x = pt
> 	end
> 	if pt.y > max_y.y then
> 		max_y = pt
> 	end
>     end
>

Why use slow interpreted Ruby to wite your own interator, when the example I gave above, uses the compiled C interator that all Array objects inherit from module Enumerable?


def custom_max_x_and_y(custom_x,custom_y,pt_array)
    custom_z = custom_x.cross(custom_y)
    trans = Geom;;Transformation.new(pt_array[0],custom_x, custom_y, custom_z)
    new_points = pt_array.map{|pt| pt.transform(trans.inverse)}
    max_x = new_points.max {|a,b| a.x <=> b.x }
    max_y = new_points.max {|a,b| a.y <=> b.y }
    return max_x.transform(trans), max_y.transform(trans)
end

Again.. however this assumes that only 1 point will be at maxiumum x and/or y. (If it matters, see my post for the find_all test.)

Cleverbeans

@dan rathbun said:

Why use slow interpreted Ruby to wite your own interator, when the example I gave above, uses the compiled C interator that all Array objects inherit from module Enumerable?

In general I find it superior to use code I understand to code which I find opaque. Ruby's syntactic quirks are still something of a mystery to me, and I didn't want to present code I couldn't explain. I'll definitely want to take advantage of the method you've presented however since I'm doing similar things in my current project. On that note, it appears there are two independent iterations over the same collection occurring here.


max_x = new_points.max {|a,b| a.x <=> b.x }
max_y = new_points.max {|a,b| a.y <=> b.y }

Is there a means of bundling them into a single traversal?

Cleverbeans

It's nice to see that the enumerable class supports so many functional methods. Thanks for pointing it out.

Dan Rathbun

@cleverbeans said:

@dan rathbun said:

Why use slow interpreted Ruby to wite your own interator, when the example I gave above, uses the compiled C interator that all Array objects inherit from module Enumerable?

In general I find it superior to use code I understand to code which I find opaque. Ruby's syntactic quirks are still something of a mystery to me, and I didn't want to present code I couldn't explain.

That's OK if speed is not an issue .. especially a first go around and you wish to just prove a concept. (Optimization can always come later.)

@cleverbeans said:

... it appears there are two independent iterations over the same collection occurring here.


> max_x = new_points.max {|a,b| a.x <=> b.x }
> max_y = new_points.max {|a,b| a.y <=> b.y }
>

True.. I might argue that it still may be faster, as the iteration vars are created and managed on the C-side.
The only way to know is to test it out. (The answer would be valuable for the Optimization topic.)

@cleverbeans said:

Is there a means of bundling them into a single traversal?

Yes I believe you could using the Enumerable.inject method.


# pts is an array of Geom;;Point3d objects
# the returned array will be max_xy_pair = [max_x_pt,max_y_pt]
# set initial mem var to array whose 2 elements are the 1st pt

max_xy_pair = pts.inject([pts[0],pts[0]]) {|mem,pt|
  # this array below is returned as var mem on each loop
  [ mem[0].x>pt.x ? mem[0];pt, mem[1].y>pt.y ? mem[1];pt ]
}

EDIT - TESTED at Console:
** pts=[pt1,pt2,pt3,pt4,pt5,pt6]

[Point3d(1, 2, 3), Point3d(0, 2, 3), Point3d(3, 1, 2), Point3d(5, 6, 7), Point3d(4, 2, 1), Point3d(6, 1, 8)]
max_xy_pair = pts.inject([pts[0],pts[0]]) {|mem,pt| [ mem[0].x>pt.x ? mem[0]:pt, mem[1].y>pt.y ? mem[1]:pt ] }
[Point3d(6, 1, 8), Point3d(5, 6, 7)]**

Looks like it works. (I was afraid after looking at the C source that the 1st arg, initial had to be an integer.) So I thought I should do a quick test.

P.S. - Do you have the Standard Ruby Core CHM Reference ?
If not, get it in the Ruby Resources topic.

Cleverbeans

So I ran some test this morning, and surprisingly the code I presented appears to be the fastest. Here is the code I used to test it.

First Method


def first_test(pts)
    xmax = pts[0].x
    ymax = pts[0].y		
    for p in pts
	if p.x > xmax then
	    xmax = p.x
	end
	if p.y > ymax then
		ymax = p.y
	end
    end
    return xmax,ymax
end

Second Method


def second_test(pts)
    return pts.inject([pts[0],pts[0]]){|mem,pt| [ mem[0].x>pt.x ? mem[0];pt, mem[1].y>pt.y ? mem[1];pt ]}
end

Third Method


def third_test(pts)
    xmax = pts.max{|a,b| a.x <=> b.x}
    ymax = pts.max{|a,b| a.y <=> b.y}
    return xmax,ymax
end

The Testing Routine


def the_test()
    pts = []
    for x in 0...10000000
	pts.push(Geom;;Point3d.new(rand,rand,rand))
    end 
    start = Time.now()
    first_test(pts)
    finish = Time.now()
    interval = finish.to_i - start.to_i
    puts("First Time; " + interval.to_s)
	
    start = Time.now()
    second_test(pts)
    finish = Time.now()
    interval = finish.to_i - start.to_i
    puts("Second Time; " + interval.to_s)

    start = Time.now()
    third_test(pts)
    finish = Time.now()
    interval = finish.to_i - start.to_i
    puts("Third Time; " + interval.to_s)

    return "Complete."
end

Results


qt()
First Time; 18
Second Time; 61
Third Time; 56
Complete.

Truth is stranger than fiction sometimes.

thomthom

If you converted the first one to use each instead of for - would it still be as fast? I wonder if it's Ruby's overhead of creating variables that might play a part in this.

Dan Rathbun

Perhaps the time to make the method call? Hmm.. but they are called only once or twice.

It doesn't make sense... the 1st test is what inject does but in C code:

rb_iterate(rb_each, obj, inject_i, (VALUE)&memo);

and this is max, in

rb_iterate(rb_each, obj, rb_block_given_p() ? max_ii ; max_i, (VALUE)&result);

We should run the test several times in different orders.