## Wednesday, May 27, 2015

### Centroid Drift Point in Polygon algorithm

Suppose you have a polygon, possibly concave, like so:
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()