I found an algorithm that works for telling whether a point is inside the polygon or not... The first step in the reasoning is to consider the normalized vectors from the point P to the set of vertices V, those will be on a unit circle, but it will look very different depending on whether P is inside the polygon or not...

So my idea was to consider what happens when every connected pair of vertices on the polygon is replaced with the normalized midpoint of those 2 vertices...

You can see that if the point is inside the normalized polygon gets closer to a regular polygon and if the point is outside the vertices bunch together, so a way to measure that is to ask whether the centroid of the transformed polygon has moved closer to P or farther away after the midpoint operation...

A test of the algorithm...

In every case and some others I've tried it could tell whether the point was inside or outside!

** Note **

I think I thought of a counter example when the winding number exceeds 1 for a period of time.

**Source Code**

def distance(point):

return (point[0]**2.0 + point[1]**2.0)**.5

def normal(point):

d = distance(point)

if d == 0:

return [0,0]

return [point[0]/d, point[1]/d]

def centroid(v):

sumx = 0

sumy = 0

for i in range(0, len(v)):

sumx += v[i][0]

sumy += v[i][1]

return [1.0*sumx/len(v), 1.0*sumy/len(v)]

def halves(v):

v2 = []

for i in range(0, len(v)-1):

v2.append(normal([(v[i][0]+v[i+1][0])/2.0, (v[i][1]+v[i+1][1])/2.0]))

v2.append(normal([(v[len(v)-1][0]+v[0][0])/2.0, (v[len(v)-1][1]+v[0][1])/2.0]))

return v2

def pointinpoly(polygon, point):

v = []

for i in range(0, len(polygon)):

v.append(normal([polygon[i][0]-point[0], polygon[i][1]-point[1]]))

c1 = centroid(v)

v2 = halves(v)

c2 = centroid(v2)

d1 = distance(c1)

d2 = distance(c2)

if d1 - d2 >= 0:

return True

else:

return False

def main():

polygon = [[3.22, 2.18],[4.24, 4.7],[7,5],[9.82,3.4],[7.58,.52],[6.14,2.52]]

points = [[6, 4.68],[8.4, 4.28],[4.1,4.52],[6.97,1.04],[8.7,3.07], [4.16,2.12]]

for i in range(0, len(points)):

point = points[i]

print(point, pointinpoly(polygon, point))

main()

## No comments:

## Post a Comment