Geometry Boost List: [ggl] Point in triangle test available?

Subject: [ggl] Point in triangle test available?
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 2010-12-02 13:59:23

Simonson, Lucanus J wrote:
> Barend Gehrels wrote:
>> I don't think it will be much faster; points are not sorted for the
>> point-in-polygon test. There are three algorithms provided, the
>> winding (slightly slower but able to detect border case), and two
>> crossing algorithms. By default, the winding algorithm is used
>> because it correctly detects if a point is located on the border, and
>> returns false then.
> 
> Consider a polygon and its holes.  You want to detect whether the
> point is inside the polygon, but not within one of its holes.  You
> detect the point is inside the polygon, your function returns true. 
> You detect the point is on the boundary of a hole, your function
> returns false for the hole.  Now you have an asymetric behavior where
> points on the boundary of the outer polygon are considered outside
> but points on the boundary of its holes are consided inside.  That
> isn't acceptable, so now the user needs to check whether the point is
> on the boundary seperately to get the right answer.  I don't know why
> the crossing algorithms should be slower than the winding algorithm. 
> Perhaps your algorithm for detecting crossing is not optimal.  Also,
> detecting crossing should be able to return a trianry result of yes,
> no, touch, which would allow you to handle the boundary case.  One
> way to compute crossing is to compute the y value at the x of the
> point on the line segment using the line equation and then compare y
> values, if the computed value is less, greater or equal gives yes, no
> or touch.  It should be two subtractions, one divisision, one
> multiply and one add per line segment and you can ignore all line
> segments that don't overlap with the point in their x interval, which
> is 1.5 branch on less on average per line segment with good branch
> prediction odds because it will usually branch the same direction as
> the last several times it was evaluated.  It should be very fast.    

Oops, I just remembered that your winding algorithm will return true for outside the hole and false for on the boundary because it will have clockwise winding, of course.  I still think the crossing algorithm should be faster and I also think that the crossing algorithm will be more robust because error accumulates in the winding algorithm and it is easy to construct a polygon such that the accumulated error exceeds the number of bits in even a long double floating point data type.  That means that for polygons with a very large number of verticies not even the sign bit can be trusted in the result.

Regards,
Luke