Есть набор координат в случайном порядке. Требуется упорядочить точки так, что бы получился замкнутый контур без пересечений рёбер.
Вероятно однозначного ответа может не быть, тогда предполагаю выбирать контур с минимальным периметром.
Т.е. имеем:
Надо получить:
Пробовал использовать готовые пакеты для нахождения Concave Hull/Alpha Shape, но при этом пропускаются некоторые точки.
Кроме того пробовал алгоритм из этого ответа на подобный вопрос. Но при большом количестве точек полный перебор всех возможных перестановок выходит очень долгим.
Буду рад любым советам. Куда смотреть, что почитать.
- Пакет alphashape
import alphashape
import matplotlib.pyplot as plt
points = [
[30.2327664, 59.9457466], [30.2342787, 59.9456499], [30.2308853, 59.9450448], [30.2326936, 59.9457579],
[30.2370232, 59.9447672], [30.2357721, 59.9442218], [30.2357188, 59.9442059], [30.2310267, 59.9459625],
[30.2352922, 59.9441033], [30.2342418, 59.9451794], [30.2356708, 59.9459594], [30.2325756, 59.9454373],
[30.2317671, 59.9430963], [30.2354012, 59.9461423], [30.2320000, 59.9432289], [30.2321622, 59.9432709],
[30.2345152, 59.9455305], [30.2335813, 59.9436467], [30.2308853, 59.9450448], [30.2345618, 59.9456060],
[30.2367058, 59.9444656], [30.2370621, 59.9448292], [30.2344635, 59.9455385], [30.2314986, 59.9435107],
[30.2321512, 59.9432815], [30.2309007, 59.9454682], [30.2320584, 59.9431722], [30.2310421, 59.9446529],
[30.2327082, 59.9457816], [30.2310559, 59.9460404], [30.2347403, 59.9464515], [30.2368819, 59.9445064]
]
hull = alphashape.alphashape(points, 900)
hull_pts = hull.exterior.coords.xy
X = hull_pts[0]
Y = hull_pts[1]
XY = list(zip(hull_pts[0], hull_pts[1]))
plt.plot(X, Y, marker='o')
ax = plt.gca()
for i, point in enumerate(XY):
ax.annotate(i, point)
plt.show()
- Пакет geopolygon
import matplotlib.pyplot as plt
import numpy as np
from geopolygon import ConcaveHull
points = [
[30.2327664, 59.9457466], [30.2342787, 59.9456499], [30.2308853, 59.9450448], [30.2326936, 59.9457579],
[30.2370232, 59.9447672], [30.2357721, 59.9442218], [30.2357188, 59.9442059], [30.2310267, 59.9459625],
[30.2352922, 59.9441033], [30.2342418, 59.9451794], [30.2356708, 59.9459594], [30.2325756, 59.9454373],
[30.2317671, 59.9430963], [30.2354012, 59.9461423], [30.2320000, 59.9432289], [30.2321622, 59.9432709],
[30.2345152, 59.9455305], [30.2335813, 59.9436467], [30.2308853, 59.9450448], [30.2345618, 59.9456060],
[30.2367058, 59.9444656], [30.2370621, 59.9448292], [30.2344635, 59.9455385], [30.2314986, 59.9435107],
[30.2321512, 59.9432815], [30.2309007, 59.9454682], [30.2320584, 59.9431722], [30.2310421, 59.9446529],
[30.2327082, 59.9457816], [30.2310559, 59.9460404], [30.2347403, 59.9464515], [30.2368819, 59.9445064]
]
hull_poly = ConcaveHull.concaveHull(np.array(points), 3)
hull_poly_arr = np.array(hull_poly)
X = [x for x, _ in hull_poly_arr]
Y = [y for _, y in hull_poly_arr]
plt.plot(X, Y, marker='o')
ax = plt.gca()
for i, point in enumerate(hull_poly_arr):
ax.annotate(i, point)
plt.show()