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

Ответ 1

Как сказал кто-то, решение минимальной длины - это проблема коммивояжера. Здесь неоптимальный, но допустимый подход:

Вычислить триангуляцию Деланея ваших точек. Последовательно удаляйте граничные сегменты до тех пор, пока вы не останетесь с границей, которая будет интерполировать все точки или больше сегментов можно удалить. Не удаляйте граничные сегменты, если все точки треугольника, использующие этот сегмент, находятся на границе. Возьмите эту границу как свой путь.

Я реализовал это в Mathematica, используя 40 случайных точек. Вот типичный результат:

Очевидное возражение состоит в том, что вы можете добраться до точки, где не все ваши точки являются граничными точками, но вы не можете удалить граничный сегмент, не сделав пересечение границы самопересекающимся. Это действительное возражение. Мне потребовалось десятки прогонов, чтобы увидеть случай, когда это произошло, но, наконец, получил этот случай:

Вероятно, вы можете увидеть некоторые очевидные способы исправить это, используя локальную топологию, но я оставлю детали вам! Одна вещь, которая может помочь, - это "перевертывание края", где вы берете два треугольника, которые разделяют сторону, например треугольник (p, q, r) и (q, p, s) и заменяют их на (r, p, s) и ( r, s, q) (все координаты против часовой стрелки вокруг треугольника). Это можно сделать, если результирующие треугольники в этом преобразовании также упорядочены по часовой стрелке.

Чтобы уменьшить потребность в исправлениях, вы захотите сделать хороший выбор сегментов для удаления на каждом шаге. Я использовал отношение длины граничного сегмента к сумме длин другой стороны треугольника-кандидата (треугольник, образованный потенциально входящей точкой с сегментом).

Ответ 2

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

Algorithm:

1. Найти крайние левые точки p
2. Найдите самую правую точку q
3. Разбейте точки на A, множество точек ниже pq и B, множество точек выше pq [вы можете использовать тест левого поворота (p, q ,?) для определить, находится ли точка выше линии].
4. Сортировать A по x-координате (по возрастанию)
5. Сортировать B по x-координате (по убыванию).
6. Вернуть многоangularьник, определенный как p, точки в A по порядку, q, точки из B по порядку.

Runtime:

Steps 1,2,3 take O(n) time.
Steps 4,5 take O(nlogn) time.
Step 6 take O(n) time.
Total runtime is O(nlogn).

Correctness:

По построению все точки, кроме p, q, находятся в множестве A или установить B. Наш выходной многоangularьник из строки 6, поэтому выводит многоangularьник с все точки. Теперь нам нужно утверждать, что ни один из отрезков линии в наш выходной полигон пересекается.

Рассмотрим каждый сегмент в Выходной полигон. Первое ребро от p до первой точки в A не может пересекают любой сегмент (потому что еще нет сегмента). Как мы продолжаем по порядку по координате х через точки в А, из каждой точки следующий сегмент идет вправо, а все предыдущие сегменты левый. Таким образом, при переходе от р через все точки А к точке д, у нас не будет пересечений.

То же самое верно, как мы идем от д назад через точки B. Эти отрезки не могут пересекаться друг с другом потому что они идут справа налево. Эти сегменты также не могут пересекают что-нибудь в A, потому что все точки в A находятся ниже линии pq, и все точки в B находятся выше этой линии.

Таким образом, ни один сегмент не пересекает каждый другой, и у нас есть простой многоangularьник.

Источник: Неработающая ссылка

Я понимаю, что это действительно поздно, но это может быть полезно для будущих зрителей.

Ответ 3

Вот код Python 3.6 (требуются библиотеки: matplotlib, numpy), основанный на bdean20ответе.

Описание фотографий:

• Слева вверху - предопределенный многоangularьник, остальные многоangularьники генерируются случайным образом.
• Пунктирная линия - соединяет зеленый (крайний левый) и красный (крайний правый) полигоны точки.
• Черные точки лежат на пунктирной линии.
• Оранжевые точки лежат ниже пунктирной линии.
• Синие точки лежат выше пунктирной линии.

=========

import random
from operator import itemgetter
import numpy
import matplotlib
import matplotlib.pyplot

class Create_random_polygon:

    def __init__(self, array, min_rand_coord = None, max_rand_coord = None, points_num = None):        
        self.array = array
        self.min_rand_coord = min_rand_coord 
        self.max_rand_coord = max_rand_coord
        self.points_num = points_num

    def generate_random_points(self):
        random_coords_list = []
        for x in range(self.points_num):
            coords_tuple = (random.randint(self.min_rand_coord, self.max_rand_coord),
                            random.randint(self.min_rand_coord, self.max_rand_coord))
            random_coords_list.append(coords_tuple)
        self.array = random_coords_list
        return random_coords_list

    def close_line_to_polygon(self):
        a = self.array[0]
        b = self.array[len(self.array)-1]
        if a == b:
            pass
        else:
            self.array.append(a)    

    def find_leftmost_point(self):
        leftmost_point = None
        leftmost_x = None
        for point in self.array:
            x = point[0]
            if leftmost_x == None or x < leftmost_x:
                leftmost_x = x
                leftmost_point = point
        return leftmost_point

    def find_rightmost_point(self):
        rightmost_point = None
        rightmost_x = None
        for point in self.array:
            x = point[0]
            if rightmost_x == None or x > rightmost_x:
                rightmost_x = x
                rightmost_point = point
        return rightmost_point

    def is_point_above_the_line(self, point, line_points):
        """return 1 if point is above the line
           return -1 if point is below the line
           return  0 if point is lays on the line"""
        px, py = point
        P1, P2 = line_points
        P1x, P1y = P1[0], P1[1]
        P2x, P2y = P2[0], P2[1]
        array = numpy.array([
            [P1x - px, P1y - py],
            [P2x - px, P2y - py],
            ])
        det = numpy.linalg.det(array)
        sign = numpy.sign(det)
        return sign

    def sort_array_into_A_B_C(self, line_points):
        [(x_lm, y_lm), (x_rm, y_rm)] = line_points
        A_array, B_array, C_array = [], [], []
        for point in self.array:
            x, y = point
            sing = self.is_point_above_the_line( (x, y), line_points)
            if sing == 0:
                C_array.append(point)
            elif sing == -1:
                A_array.append(point)
            elif sing == 1:
                B_array.append(point)
        return A_array, B_array, C_array

    def sort_and_merge_A_B_C_arrays(self, A_array, B_array, C_array):
        A_C_array = [*A_array, *C_array]
        A_C_array.sort(key=itemgetter(0))
        B_array.sort(key=itemgetter(0), reverse=True)        
        merged_arrays = [*A_C_array, *B_array]
        self.array = merged_arrays

    def show_image(self, array, line_points, A_array, B_array, C_array):
        [(x_lm, y_lm), (x_rm, y_rm)] = line_points        
        x = [x[0] for x in array]
        y = [y[1] for y in array]
        Ax = [x[0] for x in A_array]
        Ay = [y[1] for y in A_array]
        Bx = [x[0] for x in B_array]
        By = [y[1] for y in B_array]
        Cx = [x[0] for x in C_array]
        Cy = [y[1] for y in C_array]          
        matplotlib.pyplot.plot(Ax, Ay, 'o', c='orange') # below the line
        matplotlib.pyplot.plot(Bx, By, 'o', c='blue') # above the line
        matplotlib.pyplot.plot(Cx, Cy, 'o', c='black') # on the line
        matplotlib.pyplot.plot(x_lm, y_lm, 'o', c='green') # leftmost point
        matplotlib.pyplot.plot(x_rm, y_rm, 'o', c='red') # rightmost point
        x_plot = matplotlib.pyplot.plot([x_lm, x_rm], [y_lm, y_rm], linestyle=':', color='black', linewidth=0.5) # polygon division line
        x_plot = matplotlib.pyplot.plot(x, y, color='black', linewidth=1) # connect points by line in order of apperiance        
        matplotlib.pyplot.show()

    def main(self, plot = False):
        'First output is random polygon coordinates array (other stuff for ploting)'
        print(self.array)
        if self.array == None:
            if not all(
                [isinstance(min_rand_coord, int),
                 isinstance(max_rand_coord, int),
                 isinstance(points_num, int),]
                ):
                print('Error! Values must be "integer" type:', 'min_rand_coord =',min_rand_coord, ', max_rand_coord =',max_rand_coord, ', points_num =',points_num)
            else:                
                self.array = self.generate_random_points()            

        print(self.array)
        x_lm, y_lm = self.find_leftmost_point()
        x_rm, y_rm = self.find_rightmost_point()
        line_points = [(x_lm, y_lm), (x_rm, y_rm)]

        A_array, B_array, C_array = self.sort_array_into_A_B_C(line_points)
        self.sort_and_merge_A_B_C_arrays(A_array, B_array, C_array)
        self.close_line_to_polygon()
        if plot:
            self.show_image(self.array, line_points, A_array, B_array, C_array)
        return self.array

if __name__ == "__main__":
    # predefined polygon
    array = [ 
        (0, 0),
        (2, 2),
        (4, 4),
        (5, 5),
        (0, 5),        
        (1, 4),
        (4, 2),
        (3, 3),
        (2, 1),
        (5, 0),
        ]    
    array = None # no predefined polygon
    min_rand_coord = 1
    max_rand_coord = 10000
    points_num = 30

    crt = Create_random_polygon(array, min_rand_coord, max_rand_coord, points_num)
    polygon_array = crt.main(plot = True)    

==========

Ответ 4

То, что вы ищете, называется простой полигонизацией в литературе. См., Например, эту веб-страницу по этой теме. Легко создать полигонизацию star-shaped, как говорит Мигель, но сложно найти, например, минимальную полигонизацию по периметру, которая является минимальным TSP, как упоминает Аксель Кемпер. В общем случае существует экспоненциальное число различных полигонизаций для заданного множества точек.

Для звездообразованной полигонизации существует одна проблема, которая требует некоторого внимания: дополнительная точка x (в "ядре" звезды) не должна совпадать с существующей точкой! Вот один алгоритм для гарантии x. Найдите ближайшую пару точек (a, b) и пусть x - середина сегмента ab. Затем продолжайте движение по почте Мигеля.

Ответ 5

Хорошо, если вы на самом деле не заботитесь о минимальности или что-то в этом роде, вы можете просто разместить новую точку внутри выпуклого корпуса, а затем упорядочить другие точки под углом к ​​этой новой точке. Вы получите непересекающийся многоугольник.

Ответ 6

Тестирование, если два сегмента пересекаются, является простым и быстрым. См. например.

С этим вы можете построить свой полигон итеративно:

Исходные точки: S = {S0, ... Si, Sj,...}

Конечный многоугольник: A = {A0, ... Ai, Aj,...}

Вы начинаете с S full и A empty.

Возьмите первые 3 точки S и переместите их в A. Этот треугольник, конечно, не является самопересекающимся.

Затем, пока S не будет пустым, возьмите свою первую оставшуюся точку, которую мы назовем P, и найдите позицию в A, где она может быть вставлена.

Эта позиция i+1 для первого i, подтверждающего, что ни [Ai-P], ни [Ai+1-P] не пересекаются ни с какими другими сегментами [Ak-Ak+1].

Таким образом, ваш новый многоугольник A {A0, ... Ai, P, Ai+1, ...}

Ответ 7

Я считаю, что вы можете использовать алгоритм Graham scan, чтобы решить вашу проблему.

Изменить: вообще Выпуклые алгоритмы корпуса - это что-то, что можно посмотреть.

Ответ 8

У меня была та же самая проблема, и я нашел довольно простое решение, также со сложностью n * log (n).

Сначала возьмем некоторую внутреннюю точку фигуры, не имеет значения, какая из них имеет смысл быть центральной точкой, либо в середине наиболее удаленных точек, либо в среднем по всем точкам (например, в центре тяжести).

Затем отсортируйте все точки по углу, под которым они видны из центральной точки. Ключ сортировки будет эквивалентен atan2 для точки и центра.

Это. Предполагая, что p является массивом точек (x, y), это код Python.

center = reduce(lambda a, b: (a[0] + b[0], a[1] + b[1]), p, (0, 0))
center = (center[0] / len(p), (center[1] / len(p)))
p.sort(key = lambda a: math.atan2(a[1] - center[1], a[0] - center[0]))