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:48:59

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 va
lues, 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.

Regards,
Luke