I tried using the following code for the Even-Odd Rule from Wikipedia
# x, y -- x and y coordinates of point
# poly -- a list of tuples [(x, y), (x, y), ...]
def isPointInPath(x, y, poly):
num = len(poly)
i = 0
j = num - 1
c = False
for i in range(num):
if ((poly[i][1] > y) != (poly[j][1] > y)) and \
(x < (poly[j][0] - poly[i][0]) * (y - poly[i][1]) / (poly[j][1] - poly[i][1]) + poly[i][0]):
c = not c
j = i
return c
Unfortuantely, it's giving wrong results for my simple rectilinear polygon when my test point is aligned with one of the horizontal edges
-----
| |
| x ----|
x |--------|
Treating a horizontal edge as an edge makes both points regarded as within while ignoring the horizontal edge makes both points regarded as outside
So how can I make the even-odd rule work for such a polygon? Or suggest alternative algorithms?
The following rules taken from here seems to work
Note that the above rules follow the convention that
Also the author notes that this method only works for simple (non-self-intersecting) polygons. It also suggests using an efficient implementation of winding numbers instead which handles non-simple polygons better