1

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.

Emil S.
  • 412
  • 4
  • 20
  • It is tricky to get this correct. You should start with code that has been tested. One (among many) source is [WR Franklin](https://wrf.ecse.rpi.edu//Research/Short_Notes/pnpoly.html). – Joseph O'Rourke Jul 04 '18 at 13:12
  • 1
    Depending on applications, this behavior can be more consistent than you imagine. For instance, if you consider a tiling with several polygons sharing edges, the behavior can ensure that a point is interior to at most one polygon. Also for other applications, behavior on the edges is simply unimportant. And lastly, when edges are oblique telling if you are exactly on an edge can be impossible. –  Jul 06 '18 at 17:02
  • As a quick workaround, you can check if the test point belongs to any of the sides and accept or reject it before performing the pip test proper. –  Jul 06 '18 at 17:05

1 Answers1

0

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.