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

Subject: [ggl] Point in triangle test available?
From: Barend Gehrels (barend.gehrels)
Date: 2010-12-02 15:40:47

Hi Luke,

> 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.

Our within function using winding works correctly for all cases, be it 
inside, outside, or on a border or on a border of a whole. So I don't 
get your post.

Furthermore it is slightly (hardly detectable) slower, but not much slower.

> 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.

That is not related.

>    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  (...)
I also don't get this.  There is no accumulation in a bit switching from 
0 to 1 and from 1 to 0. I think you referring to another library or to 
how you think it works (as indicated above, this is not how it really 
works).

Regards, Barend

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/ggl/attachments/20101202/dd123f0c/attachment.html