Boost logo

Geometry :

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

Regards, Barend

-------------- next part --------------
An HTML attachment was scrubbed...

Geometry list run by mateusz at