7

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

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

Т.е. имеем:

введите сюда описание изображения

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

введите сюда описание изображения


Пробовал использовать готовые пакеты для нахождения Concave Hull/Alpha Shape, но при этом пропускаются некоторые точки.

Кроме того пробовал алгоритм из этого ответа на подобный вопрос. Но при большом количестве точек полный перебор всех возможных перестановок выходит очень долгим.

Буду рад любым советам. Куда смотреть, что почитать.

  1. Пакет 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()

введите сюда описание изображения

  1. Пакет 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()

введите сюда описание изображения

3
  • Создай выпуклый полигон, потом добавь впуклости вставками
    – eri
    5 июл 2020 в 23:32
  • 1
    Здесь есть варианты
    – MBo
    6 июл 2020 в 4:48
  • 1
    @eri , можете на пальцах объяснить как "добавить впуклости вставками"?
    – Duncan
    6 июл 2020 в 19:42

2 ответа 2

3

Обратите внимание, что точка 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()

Результат введите сюда описание изображения

7
  • похоже на ru.wikipedia.org/wiki/… 6 июл 2020 в 9:58
  • 1. Если центроид и две (или больше) точек исходного массива лежат на одной прямой, причем все точки - по одну сторону от центроида - работать не будет. Надо ставить дополнительную проверку. 2. Переход к полярным координатам с центроидом в центре по идее должно существенно упростить алгоритм. Просто - сортировка по полярному углу. А в остальном - вполне разумная идея.
    – passant
    6 июл 2020 в 10:04
  • Ответ, который должен получиться, показан на втором графике в вопросе.
    – Duncan
    6 июл 2020 в 19:35
  • @Duncan Добавил ещё один вариант. Сейчас больше похоже на требуемый график, но есть небольшие различия.
    – MiniMax
    7 июл 2020 в 22:40
  • 1
    @MiniMax 1) Если получится, то обязательно выложу. 2,3)Это тестовое задание. Надо получить контур реального земельного участка. Возможно даже с не минимальным периметром. Про минимальный периметр - это было моё предположение.
    – Duncan
    8 июл 2020 в 10:44
0

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

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

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

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.