pythonalgorithmgeometrypolygoncomputational-geometry

How to Expand a Polygon Until One of the Borders Reaches a Point


I have code to expand the polygon, it works by multiplying the xs and ys by a factor then re centering the resultant polyon at the center of the original.

I also have code to find the value for the expansion factor, given a point that the polygon needs to reach:

import numpy as np
import itertools as IT
import copy
from shapely.geometry import LineString, Point

def getPolyCenter(points):
    """
    http://stackoverflow.com/a/14115494/190597 (mgamba)
    """
    area = area_of_polygon(*zip(*points))
    result_x = 0
    result_y = 0
    N = len(points)
    points = IT.cycle(points)
    x1, y1 = next(points)
    for i in range(N):
        x0, y0 = x1, y1
        x1, y1 = next(points)
        cross = (x0 * y1) - (x1 * y0)
        result_x += (x0 + x1) * cross
        result_y += (y0 + y1) * cross
    result_x /= (area * 6.0)
    result_y /= (area * 6.0)
    return (result_x, result_y)

def expandPoly(points, factor):
    points = np.array(points, dtype=np.float64)
    expandedPoly = points*factor
    expandedPoly -= getPolyCenter(expandedPoly)
    expandedPoly += getPolyCenter(points)
    return np.array(expandedPoly, dtype=np.int64)

def distanceLine2Point(points, point):
    points = np.array(points, dtype=np.float64)
    point = np.array(point, dtype=np.float64)

    points = LineString(points)
    point = Point(point)
    return points.distance(point)

def distancePolygon2Point(points, point):
    distances = []
    for i in range(len(points)):
        if i==len(points)-1:
            j = 0
        else:
            j = i+1
        line = [points[i], points[j]]
        distances.append(distanceLine2Point(line, point))

    minDistance = np.min(distances)
    #index = np.where(distances==minDistance)[0][0]

    return minDistance 

"""
    Returns the distance from a point to the nearest line of the polygon,
    AND the distance from where the normal to the line (to reach the point)
    intersets the line to the center of the polygon.
"""
def distancePolygon2PointAndCenter(points, point):
    distances = []
    for i in range(len(points)):
        if i==len(points)-1:
            j = 0
        else:
            j = i+1
        line = [points[i], points[j]]
        distances.append(distanceLine2Point(line, point))

    minDistance = np.min(distances)
    i = np.where(distances==minDistance)[0][0]
    if i==len(points)-1:
        j = 0
    else:
        j = i+1
    line = copy.deepcopy([points[i], points[j]])

    centerDistance = distanceLine2Point(line, getPolyCenter(points))

    return minDistance, centerDistance

minDistance, centerDistance = distancePolygon2PointAndCenter(points, point)
expandedPoly = expandPoly(points, 1+minDistance/centerDistance)

This code only works when the point is directly opposing one of the polygons lines.


Solution

  • Modify your method distancePolygon2PointAndCenter to instead of

    Returns the distance from a point to the nearest line of the polygon

    To return the distance from a point to the segment intersected by a ray from the center to the point. This is the line that will intersect the point once the polygon is fully expanded. To get this segment, take both endpoints of each segment of your polygon, and plug them into the equation for the line parallel & intersecting the ray mentioned earlier. That is y = ((centerY-pointY)/(centerX-pointX)) * (x - centerX) + centerY. You want to want to find endpoints where either one of them intersect the line, or the two are on opposite sides of the line.

    Then, the only thing left to do is make sure that we pick the segment intersecting the right "side" of the line. To do this, there are a few options. The fail-safe method would be to use the formula cos(theta) = sqrt((centerX**2 + centerY**2)*(pointX**2 + pointY**2)) / (centerX * pointX + centerY * pointY) however, you could use methods such as comparing x and y values, taking the arctan2(), and such to figure out which segment is on the correct "side" of center. You'll just have lots of edge cases to cover. After all this is said and done, your two (unless its not convex, in which case take the segment farthest from you center) endpoints makeup the segment to expand off of.