самый большой префикс массива вершин, который образует выпуклый многоугольник

Question

Относится к: Разложение многоугольника - удаление вогнутых точек для формирования выпуклых многоугольников

Я ищу алгоритм для выполнения следующих действий:

Входные данные - это массив2D точек (P ₀ … P _N-1 ).Длина N массива варьируется (3 ≤ N <∞) <br>Для любого M ≤ N может быть или не быть выпуклый многоугольник, вершины которого равны P ₀ … P _M-1 в некотором порядке.

Примечание ребра не обязательно являются смежными парами в массиве.

Какой наиболее эффективный алгоритм для нахождения максимального значения M такой, чтоэтот выпуклый многоугольник существует?

Мой текущий алгоритм очень неэффективен.Я тестирую с M = 3, затем M = 4, M = 5 и т. Д., Вычисляю корпус, затем проверяю, что все P ₀ … P _M-1 являются вершинами корпуса, еслине тогда я вырываюсь из цикла и возвращаю M-1.

Пример # 1: [(-2,2), (2,2), (-2,-2), (-1,1)]

результат: 3 (потому что первые три точки образуют треугольник, но добавляяP ₃ = (-1,1) сделает полигон невыпуклым)

Пример № 2: [(-2,2), (2,2), (-2,-2), (1,-1)]

результат: 4 (потому что выпуклый четырехугольникможет быть построен из всех 4 точек массива)

Обновление Пример # 3: [(-3,3), (3,3), (2,-1), (-3,-3), (3,-3), (-2,1)]
результат: 4.

В этом примере демонстрируетсяпочему недостаточно взять выпуклую оболочку всех предоставленных точек и найти префикс, который является ее подмножеством.(3,-3) не может быть частью выпуклого многоугольника, состоящего из первых пяти точек, потому что тогда предыдущая точка (2,-1) больше не будет лежать на корпусе.Но это (3,-3), которое должно быть отклонено, даже если оно лежит на корпусе всех шести точек, а (2,-1) - нет.

Примеры неверных входных данных:

• [(-1,-1), (0,0)] (слишком мало точек)
• [(-1,-1), (0,0), (1,1), (1, -1)] (первые три точки коллинеарны: я не ожидал бы алгоритмчтобы справиться с этим.)

Answer 1

Для этого существует очень простое решение O (m log m).

Учитывая, что есть как минимум 3 точки, а первые 3 не коллинеарны:

1. Найдите точку P в треугольнике первых 3 точек.

2. Сортируйте 3 точки по их углу относительно P (против часовой стрелки).(Этот отсортированный список будет выпуклой оболочкой)

3. Пока мы не находимся в конце списка, найдите позицию следующей точки в отсортированном списке.

4. Если при вставке точки полигон будет вогнутым, перейдите к 6. (Это можно проверить, просто проверив два соседних новых витка и текущий оборот)

5. Вставьте точку и перейдите к 3.

6. Готово.

Основной край, который вы должны здесь обработать, этовставка находится на одном из концов списка, поскольку список на самом деле является круглым.Один простой способ справиться с этим - для каждой точки вставить ее под своим углом и под углом + - 2pi.

Answer 2

Вы можете сделать это за время O (m lg m).

• Сохранить точки верхнего и нижнего корпусов в деревьях поиска, обозначенных координатой X.
• Когда новыйПрибывает точка, найдите верхний и нижний отрезки, покрывающие ее значение X (ищите деревья).
• Если новая точка находится между двумя линиями, то она не находится на корпусе.Сдавайтесь.
• В противном случае вставьте точку в верхний или нижний корпус (в зависимости от того, какой отрезок линии ближе).
• Если при вставке точки соседние точки были повернуты во внутренние углы, онине на корпусе.Сдавайся.
• Обращайся с случаями ребер, такими как новая крайняя левая точка, вертикальные точки и т. Д.
• Продолжайте до тех пор, пока не будет обработано нужное количество точек.

Answer 3

Я думаю, вы хотите инкрементальный выпуклый корпус.Вот несколько ссылок:

• http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/ConvexHull/incrementCH.htm
• http://ww3.algorithmdesign.net/handouts/IncrementalHull.pdf
• http://www.fandm.edu/computer-science/professors-emeriti/anderson/jay-martin-anderson/research-and-development/portal-algorithm-visualization-in-computational-geometry/convex-hull-an-incremental-algorithm

Answer 4

Что если вы попробуете что-то вроде бинарного поиска?Каждый раз, когда весь префикс образует выпуклый многоугольник, удваивайте размер префикса.Каждый раз, когда это не удается, уменьшите размер префикса до половины между текущим размером и предыдущим размером.