Упорядочить массив, содержащий координаты точек, чтобы создать замкнутый полигон

Question

Есть набор координат в случайном порядке. Требуется упорядочить точки так, что бы получился замкнутый контур без пересечений рёбер.

Вероятно однозначного ответа может не быть, тогда предполагаю выбирать контур с минимальным периметром.

Т.е. имеем:

Надо получить:

Пробовал использовать готовые пакеты для нахождения 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()

Answer 1

Обратите внимание, что точка 30.2308853, 59.9450448 повторяется в вашем списке с координатами два раза. На графике она также имеет два номера - 0 и 31, которые наложились друг на друга. Таким образом, в списке points 31 уникальная точка, при 32 элементах. Понятно, что это сделано для замыкания полигона при отрисовке.

Вариант №1

По алгоритму из этого ответа (на английском).

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]
        ]

leftmost_point, *_, rightmost_point = sorted(points, key=lambda lst: lst[0])
x1, y1 = leftmost_point
x2, y2 = rightmost_point

border_slope = (y2 - y1) / (x2 - x1)

points_below_border = [(x1, y1)]
points_above_border = [(x2, y2)]

for x, y in points:
    border = border_slope * (x - x1) + y1
    if y < border:
        points_below_border.append((x, y))
    elif y > border:
        points_above_border.append((x, y))

points_below_border.sort()
points_above_border.sort(reverse=True)

points_above_border.append((x1, y1))

merged_points = points_below_border + points_above_border

x_lst = [x for x, _ in merged_points]
y_lst = [y for _, y in merged_points]

plt.plot(x_lst, y_lst, marker='o')

ax = plt.gca()
for number, point in enumerate(merged_points[:-1]):
    ax.annotate(number, point)

plt.show()

Результат

Вариант №2

Придумал свой способ, на примере из вопроса работает, на других не проверял.

Идея: найти точку равноудалённую от всех (центроид), вычислить наклон и длину воображаемой линии, проведённой от центроида до каждой точки. Отсортировать исходные координаты на основании этих значений.

import matplotlib.pyplot as plt
from math import asin, degrees, sqrt

def order(centroid_x, centroid_y, points):
    lst = []
    for x, y in points:
        adjacent = x - centroid_x 
        opposite = y - centroid_y 
        hypotenuse = sqrt(adjacent**2 + opposite**2)
        sine = abs(opposite) / hypotenuse
        angle = degrees(asin(sine))

        if adjacent < 0 and opposite > 0:
            angle = 180 - angle
        elif adjacent < 0 and opposite < 0:
            angle += 180
        elif adjacent > 0 and opposite < 0:
            angle = 360 - angle

        lst.append((angle, hypotenuse, x, y))

    # Сортируем по углу и расстоянию от центра до точки
    lst.sort(key=lambda tup: (tup[0], tup[1]))
    # Замыкаем фигуру, чтобы была линия от последней точки к первой
    lst.append(lst[0])

    return [(x, y) for _, _, x, y in lst]

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]
        ]

centroid_x = sum(x for x, _ in points) / len(points)
centroid_y = sum(y for _, y in points) / len(points)

ordered_points = order(centroid_x, centroid_y, points)

x_lst = [x for x, _ in ordered_points]
y_lst = [y for _, y in ordered_points]

plt.plot(x_lst, y_lst, marker='o')

ax = plt.gca()
for number, point in enumerate(ordered_points[:-1]):
    ax.annotate(number, point)

plt.scatter(centroid_x, centroid_y, color="red")
plt.show()

Результат

Answer 2

Бери 4 точки: минимум-максимум по x и y. получается [A,B,C,D]

Потом бери точку из оставшихся и считай растояние до отрезков из того массива (AB,BC,CD,DA)

Вставляешь точку E между координатами до которых ближе [ABECD]

Следующую точку до отрезков (AB,BE,EC,CD,DA)

БЛОГ НА HUSL

Упорядочить массив, содержащий координаты точек, чтобы создать замкнутый полигон

Ответы (2 шт):

Вариант №1

Вариант №2