将多边形坐标重新采样为 space 它们均匀
Resample polygon coordinates to space them evenly
我有一个这样的多边形：
顶点顺序正确（我认为是逆时针方向）：
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},
]
我想对这些顶点进行重新采样，使其 space 均匀。它可能可以通过重新插值 2D 顶点来完成，但这不是我喜欢的东西，我想知道在尝试重新发明轮子之前图书馆是否已经这样做了。我该怎么办？
编辑
例如，使用 n=15，我得到一组坐标，如下所示：
编辑 2
使用@kaya3解决方案，n=128:
这里有一个可能的解决方案：通过将多边形的总周长除以 k 选择 k 个均匀分布的点，然后进行线性插值。
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
我在寻找一种以 numpy 数组格式对多边形进行重采样的方法时遇到了这个问题。
同时，我解决了问题；也许这对其他人有帮助：
import numpy as np
def resample_polygon(xy: np.ndarray, n_points: int = 100) -> np.ndarray:
# Cumulative Euclidean distance between successive polygon points.
# This will be the "x" for interpolation
d = np.cumsum(np.r_[0, np.sqrt((np.diff(xy, axis=0) ** 2).sum(axis=1))])
# get linearly spaced points along the cumulative Euclidean distance
d_sampled = np.linspace(0, d.max(), n_points)
# interpolate x and y coordinates
xy_interp = np.c_[
np.interp(d_sampled, d, xy[:, 0]),
np.interp(d_sampled, d, xy[:, 1]),
]
return xy_interp
对于提供的数据，函数可以像这样使用：
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},
]
# construct numpy array from list of dicts
xy = np.array([(c['x'], c['y']) for c in coords])
# resample polygon
xy_resampled = resample_polygon(xy, 100)
# plot result
import matplotlib.pyplot as plt
fig, ax = plt.subplots(figsize=(7,14))
ax.scatter(xy[:, 0], xy[:, 1], marker='o', s=150)
ax.scatter(xy_resampled[:, 0], xy_resampled[:, 1])
ax.set_aspect(1)
ax.invert_yaxis()
我有一个这样的多边形：
顶点顺序正确（我认为是逆时针方向）：
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},
]
我想对这些顶点进行重新采样，使其 space 均匀。它可能可以通过重新插值 2D 顶点来完成，但这不是我喜欢的东西，我想知道在尝试重新发明轮子之前图书馆是否已经这样做了。我该怎么办？
编辑
例如，使用 n=15，我得到一组坐标，如下所示：
编辑 2
使用@kaya3解决方案，n=128:
这里有一个可能的解决方案：通过将多边形的总周长除以 k 选择 k 个均匀分布的点，然后进行线性插值。
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
我在寻找一种以 numpy 数组格式对多边形进行重采样的方法时遇到了这个问题。
同时，我解决了问题；也许这对其他人有帮助：
import numpy as np
def resample_polygon(xy: np.ndarray, n_points: int = 100) -> np.ndarray:
# Cumulative Euclidean distance between successive polygon points.
# This will be the "x" for interpolation
d = np.cumsum(np.r_[0, np.sqrt((np.diff(xy, axis=0) ** 2).sum(axis=1))])
# get linearly spaced points along the cumulative Euclidean distance
d_sampled = np.linspace(0, d.max(), n_points)
# interpolate x and y coordinates
xy_interp = np.c_[
np.interp(d_sampled, d, xy[:, 0]),
np.interp(d_sampled, d, xy[:, 1]),
]
return xy_interp
对于提供的数据，函数可以像这样使用：
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},
]
# construct numpy array from list of dicts
xy = np.array([(c['x'], c['y']) for c in coords])
# resample polygon
xy_resampled = resample_polygon(xy, 100)
# plot result
import matplotlib.pyplot as plt
fig, ax = plt.subplots(figsize=(7,14))
ax.scatter(xy[:, 0], xy[:, 1], marker='o', s=150)
ax.scatter(xy_resampled[:, 0], xy_resampled[:, 1])
ax.set_aspect(1)
ax.invert_yaxis()