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
        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))

No comments:

Post a Comment