While searching for point-in-polygon tests I've found the one described by Dean Povey here. I like the approach as it can be easily understood (raycast along the x-axis) but I've come across a small inconsistency with that method. While writing Unit-Tests for my implementation I noticed that when taking a square as a "Test-Polygon" points on the left and bottom edge of the square are recognized as part of the polygon while points on the right and top side of the polygon are recognized as outside the polygon. Here's a small drawing showing what I mean (+ are not recognized as inside, doubled lines and the x are):
+--------+
‖ |
‖ |
x========+
Does anyone know how I can change the algorithm to show consistent behaviour for points on the edge? It doesn't matter if the edges are considered as inside or not, just that the behaviour is consistant.
To test if a point P lies on an edge QR, consider the transformation that maps Q to the origin and R to the point (0, 1).
Using complex numbers, write this transformation as Z = (z - Q) / (R - Q) and transform P with (P - Q) / (R - Q). This number must be pure real and its real part be in [0, 1].
You can use this test to detect points on the outline. It is also possible to allow a tolerance, by allowing the imaginary part to be a small number. In this case, it is advisable to normalize the denominator R - Q, so that the imaginary part becomes the Euclidean distance to the segment.