Shrink polygon using corner coordinates

Question

I'm trying to figure out how to shrink a polygon using only the coordinates of its corners. For example, if I have the following shape with corners at [(0, 0), (0, 100), (20, 100), (30, 60), (40, 100), (60, 100), (60, 0), (40, 10), (40, 40), (20, 40), (20, 10)] so the shape looks like this:

And I want to find the corner coordinates for if I shrink this polygon by some width and height factor. For example, If I want to shrink its width by 10% and height by 20% then this could be shown as something like this:

I was trying to do this using cv2.resize() by could not get the corners after resizing. I have been trying to find an algorithm for polygon resizing or polygon shrinking, but cannot find anything about how to do this. Do any algorithms or packages for doing something like this exist?

Answer 1

I have tested this solution on more than 1200 polygons of real life building in california and it works like charm.

One more thing is that this same approach works find for enlarging polygons as well equally well. This below method can be used as it is:

def shrink_or_swell_shapely_polygon(my_polygon, factor=0.10, swell=False):
    ''' returns the shapely polygon which is smaller or bigger by passed factor.
        If swell = True , then it returns bigger polygon, else smaller '''
    from shapely import geometry

    #my_polygon = mask2poly['geometry'][120]

    shrink_factor = 0.10 #Shrink by 10%
    xs = list(my_polygon.exterior.coords.xy[0])
    ys = list(my_polygon.exterior.coords.xy[1])
    x_center = 0.5 * min(xs) + 0.5 * max(xs)
    y_center = 0.5 * min(ys) + 0.5 * max(ys)
    min_corner = geometry.Point(min(xs), min(ys))
    max_corner = geometry.Point(max(xs), max(ys))
    center = geometry.Point(x_center, y_center)
    shrink_distance = center.distance(min_corner)*0.10

    if swell:
        my_polygon_resized = my_polygon.buffer(shrink_distance) #expand
    else:
        my_polygon_resized = my_polygon.buffer(-shrink_distance) #shrink

    #visualize for debugging
    #x, y = my_polygon.exterior.xy
    #plt.plot(x,y)
    #x, y = my_polygon_shrunken.exterior.xy
    #plt.plot(x,y)
    ## to net let the image be distorted along the axis
    #plt.axis('equal')
    #plt.show()    
    
    return my_polygon_resized

Answer 2

As far as I have understood you are searching the functionality of ST_Buffer from postgis, but with separated factors. This is unfortunately not easy to achieve (see one question in the qgis-stack for more on it).

But if it already helps to do it with the same factor of x and y (or as a start for a more elaborate algorithm) here you go:

One library that makes ST_Buffer function accessible within python is shapely.

(If you need more geo-data specific power geoalchemy2 might be the better option. Beware the crs/srid changes in that case)

from shapely import geometry
import matplotlib.pyplot as plt

# your variables
coords = [(0, 0), (0, 100), (20, 100), (30, 60), (40, 100), (60, 100), (60, 0), (40, 10), (40, 40), (20, 40), (20, 10)]
lines = [[coords[i-1], coords[i]] for i in range(len(coords))]

# your factor of 10%
# Note: with 20% the polygon becomes a multi-polygon, so a loop for plotting would be needed.
factor = 0.1

# code from nathan
xs = [i[0] for i in coords]
ys = [i[1] for i in coords]
x_center = 0.5 * min(xs) + 0.5 * max(xs)
y_center = 0.5 * min(ys) + 0.5 * max(ys)

min_corner = geometry.Point(min(xs), min(ys))
max_corner = geometry.Point(max(xs), max(ys))
center = geometry.Point(x_center, y_center)
shrink_distance = center.distance(min_corner)*factor

assert abs(shrink_distance - center.distance(max_corner)) < 0.0001

my_polygon = geometry.Polygon(coords)
my_polygon_shrunken = my_polygon.buffer(-shrink_distance)


x, y = my_polygon.exterior.xy
plt.plot(x,y)
x, y = my_polygon_shrunken.exterior.xy
plt.plot(x,y)

# to net let the image be distorted along the axis
plt.axis('equal')

plt.show()

Answer 3

I do not think it is mathematically possible to have a percentage shrink in x, a percentage shrink in y and never have the layout move outside the original layout. That is however just a hunch.

This code shifts all the lines a certain amount closer to the center and then finds the new intersection points of all the lines:

import matplotlib.pyplot as plt

def det(a, b):
        return a[0] * b[1] - a[1] * b[0]

def line_intersection(line1, line2):
    xdiff = (line1[0][0] - line1[1][0], line2[0][0] - line2[1][0])
    ydiff = (line1[0][1] - line1[1][1], line2[0][1] - line2[1][1]) #Typo was here

    div = det(xdiff, ydiff)
    if div == 0:
       raise Exception('lines do not intersect')

    d = (det(*line1), det(*line2))
    x = det(d, xdiff) / div
    y = det(d, ydiff) / div
    return x, y

# how much the coordinates are moved as an absolute value
shrink_value_x = 3
shrink_value_y = 1.5

# coords must be clockwise
coords = [(0, 0), (0, 100), (20, 100), (30, 60), (40, 100), (60, 100), (60, 0), (40, 10), (40, 40), (20, 40), (20, 10)]
lines = [[coords[i-1], coords[i]] for i in range(len(coords))]

new_lines = []
for i in lines:
    dx = i[1][0] - i[0][0]
    dy = i[1][1] - i[0][1]

    # this is to take into account slopes
    factor = 1 / (dx*dx + dy*dy)**0.5
    new_dx = dy*shrink_value_x * factor
    new_dy = dx*shrink_value_y * factor

    new_lines.append([(i[0][0] + new_dx, i[0][1] - new_dy),
                      (i[1][0] + new_dx, i[1][1] - new_dy)])

# find position of intersection of all the lines
new_coords = []
for i in range(len(new_lines)):
    new_coords.append((line_intersection(new_lines[i-1], new_lines[i])))

I got the line intersection code from this answer @Paul Draper.

This outputs

Answer 4

I misread the question, I'm leaving up the anwer because it might help someone, but I realize the final output is not the desired one

To get the new coordinates of the polygon after shrinking you can multiply all coordinates (position vectors) with the shrinkage factor like this:

x_shrink = 0.1
y_shrink = 0.2

coords = [(0, 0), (0, 100), (20, 100), (30, 60), (40, 100), (60, 100), (60, 0), (40, 10), (40, 40), (20, 40), (20, 10)]
xs = [i[0] for i in coords]
ys = [i[1] for i in coords]

# simplistic way of calculating a center of the graph, you can choose your own system
x_center = 0.5 * min(xs) + 0.5 * max(xs)
y_center = 0.5 * min(ys) + 0.5 * max(ys)

# shrink figure
new_xs = [(i - x_center) * (1 - x_shrink) + x_center for i in xs]
new_ys = [(i - y_center) * (1 - y_shrink) + y_center for i in ys]

# create list of new coordinates
new_coords = zip(new_xs, new_ys)

This outputs the following (blue is original, green is the shrunk polygon)