Search code examples
pythonpolygon

Resample polygon coordinates to space them evenly

I've a polygon like this:

enter image description here

The vertices are ordered correctly (anti-clockwise, I think):

coords = [
    {x: 428.0, y: 273.0}, {x: 410.0, y: 335.0}, {x: 398.0, y: 350.0}, {x: 384.0, y: 355.0}, {x: 363.0, y: 410.0},
    {x: 354.0, y: 424.0}, {x: 318.0, y: 455.0}, {x: 299.0, y: 458.0}, {x: 284.0, y: 464.0}, {x: 250.0, y: 490.0},
    {x: 229.0, y: 492.0}, {x: 204.0, y: 484.0}, {x: 187.0, y: 469.0}, {x: 176.0, y: 449.0}, {x: 164.0, y: 435.0},
    {x: 144.0, y: 392.0}, {x: 132.0, y: 349.0}, {x: 122.0, y: 334.0}, {x: 120.0, y: 324.0}, {x: 121.0, y: 294.0},
    {x: 119.0, y: 274.0}, {x: 121.0, y: 264.0}, {x: 118.0, y: 249.0}, {x: 118.0, y: 224.0}, {x: 121.0, y: 209.0},
    {x: 130.0, y: 194.0}, {x: 138.0, y: 159.0}, {x: 147.0, y: 139.0}, {x: 155.0, y: 112.0}, {x: 170.0, y: 89.0},
    {x: 190.0, y: 67.0}, {x: 220.0, y: 54.0}, {x: 280.0, y: 47.0}, {x: 310.0, y: 55.0}, {x: 330.0, y: 56.0},
    {x: 345.0, y: 60.0}, {x: 355.0, y: 67.0}, {x: 367.0, y: 80.0}, {x: 375.0, y: 84.0}, {x: 382.0, y: 95.0},
    {x: 395.0, y: 106.0}, {x: 403.0, y: 120.0}, {x: 410.0, y: 151.0}, {x: 417.0, y: 210.0}, {x: 419.0, y: 215.0},
    {x: 425.0, y: 218.0}, {x: 431.0, y: 225.0}, {x: 430.0, y: 265.0},
]

I would like to resample those vertices to space them evenly. It could be probably done by re-interpolating the 2D vertices but that's not something I'm confortable with and I wonder if a library already does that before trying to reinvent the wheel. How could I do?

EDIT

For example, with n=15, I get a set of coordinates which looks like this:

enter image description here

EDIT 2

With @kaya3 solution, n=128:

enter image description here

Solution

  • Here's a possible solution: choose k evenly spaced points by dividing the total perimeter of the polygon by k, and linearly interpolating.

    import math

def distance(p, q):
    return math.hypot(q['x'] - p['x'], q['y'] - p['y'])

def lerp(p, q, t):
    return {
        'x': (1 - t) * p['x'] + t * q['x'],
        'y': (1 - t) * p['y'] + t * q['y']
    }

def resample_polygon(polygon, k):
    edges = list(zip(polygon, polygon[1:] + polygon[:1]))
    arc_length = sum(distance(p, q) for p, q in edges) / k
    result = [polygon[0]]
    t = 0
    for p, q in edges:
        d_t = distance(p, q) / arc_length
        while t + d_t >= len(result) < k:
            v = lerp(p, q, (len(result) - t) / d_t)
            result.append(v)
        t += d_t
    return result