Inconsistent / confusing behavior of Polygon2D.EnclosesPoint()

[DaveInCaz]

I created a Polygon2D with the following corner points:

0, 0, 
10, 0, 
10, 10,
0, 10

i.e., a simple square.

Note that Polygon2D.EnclosesPoint is documented as follows:

...Points on the polygon edges are not counted as contained within the polygon.

Accordingly .EnclosesPoint(new Point2D(10, 10) returns False as expected, since that point is on the polygon edge.

But .EnclosesPoint(new Point2D(0, 1) returns True which was unexpected since point 0, 1 is on the "leftmost" edge of this square. Testing with 0, 5 had the same result.

Is this a bug or am I misunderstanding the documentation? (Or am I misunderstanding something else?)

Thank you

[Jones-Adam]

The library currently implements the algorithm described by W. Randolph Franklin at url

As he notes this algorithm does not specifically deal with points on the edge. So depending upon floating point rounding errors a given point on the edge may or may not be considered part of the polygon.

Perhaps the documentation could make that clearer...

[RiSearcher]

The documentation is incorrect. As far as I remember, this algorithm treats points on left-bottom edge as "inside", and top-right edge as outside. So that if you have multiple touching non-overlapping polygons, each point will belong to one and only one polygon.

[DaveInCaz]

Here's the wording from the link provided above:

PNPOLY partitions the plane into points inside the polygon and points outside the polygon. Points that are on the boundary are classified as either inside or outside.
...
Any particular point is always classified consistently the same way. ... Depending on internal roundoff errors, PNPOLY may say that [some point on the boundary] P is [either inside or outside a given polygon]. However it will always give the same answer when P is tested against those triangles.

FYI 'PINPOLY' is the name of the algorithm.

But I don't think this is just a documentation issue. It means you essentially cannot trust the return value from EnclosesPoint() . It might return either a false positive or false negative, and you can't tell the difference.

Ideally there would be a method which would be totally consistent. But as a workaround, maybe there is a good way of checking if a point IS on the boundary or not. That would help to clarify what EnclosesPoint means.

[RiSearcher]

Check this URL: http://geomalgorithms.com/a03-_inclusion.html

[Jones-Adam]

Well that kind of depends on how accurate you need it to be. For things like hit testing or collision testing in games, this algorithm is probably close enough that the speed advantage it provides more than makes up for the ambiguity along the edges. If one of the other algorithms for determining this better suits your need then you are certainly welcome to submit a PR with it, but I suspect that we have a different concern here which they will not solve and it has more to do with the precision (or limitations there of) with respect to calculations performed with floating point numbers.

Since we are dealing with floating point numbers in this library there are a few questions which become highly relevant. Firstly, what does precision actually mean to you? Accurate to 2 decimal places, 3? 20? or maybe 0? Secondly, what does being on the boundary mean to you? If it is a line which has a width equal to the limit of point precision you are using? What happens if the point partially overlaps this line? Should it be 100% overlapped to be on the line, or more than 50% or on the line if it is a mere sliver on the line. Think about a tennis match and the ball bouncing on the line.

If you are accustomed to dealing with classical geometry these kinds of questions might not make immediate sense - after all a point is a point and line's don't have widths. However it is perhaps more helpful to think of floating point math as being an approximation than an absolute, so we get points which are only accurate within a given error and lines which have an error width.

There is a fairly good explanation about errors and floating point numbers here

[DaveInCaz]

In my case at least we would be able to identify a tolerance for which we would consider a point "on" the boundary or not.