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

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

Я ищу алгоритм, чтобы сделать следующее:

Входными данными является массив двумерных точек (P 0… P N-1). Длина N массива варьируется (3 ≤ N ‹∞).
Для любого M ≤ N может быть или не быть выпуклый многоугольник с вершинами P 0… P M- 1 в некотором порядке.

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

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

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

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

Пример № 2: [(-2,2), (2,2), (-2,-2), (1,-1)]
Диаграмма для примера № 2
результат: 4 (поскольку выпуклый четырехугольник можно построить из всех 4 точек в массиве)

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

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

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

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

algorithm geometry convex-hull convex-polygon
person finnw    schedule 14.01.2011    source источник
comment
Чем это отличается от обычного выпуклого корпуса? Хотим ли мы получить выпуклую оболочку с наибольшим количеством вершин в ней?   -  person biziclop    schedule 14.01.2011
comment
@biziclop, да, я хочу корпус с наибольшим количеством вершин. И я надеюсь, что это можно сделать более эффективно, чем вычисление корпуса для каждого возможного размера.   -  person finnw    schedule 14.01.2011
comment
Как упоминалось biziclop: это просто вопрос поиска выпуклой оболочки набора точек. Количество точек, лежащих на краю этого выпуклого корпуса, соответствует вашему размеру. Итак, O (n * log (n)) с использованием сканирования Грэма или алгоритма Quick-Hull. Или я что-то упускаю?   -  person Bart Kiers    schedule 14.01.2011
comment
@ Барт Кирс, не совсем так. Меня интересуют только корпуса, которые являются префиксами массива. Я должен прекратить сканирование массива, когда вижу точку, которая не может быть частью корпуса. Любые последующие точки следует игнорировать, даже если они могут быть частью (другого) корпуса.   -  person finnw    schedule 14.01.2011
comment
@Bart Kiers, я добавил пример №3, чтобы проиллюстрировать это.   -  person finnw    schedule 14.01.2011

Ответы (4)


arrow_upward
2
arrow_downward

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

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

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

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

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

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

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

  6. Выполнено.

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

person Chris Hopman    schedule 14.01.2011

arrow_upward
2
arrow_downward

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

person Raph Levien    schedule 14.01.2011

arrow_upward
2
arrow_downward

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

  • Сохраните верхнюю и нижнюю точки корпуса в деревьях поиска с координатами X.
  • Когда появится новая точка, найдите верхний и нижний сегменты линии, покрывающие ее значение X (поиск по деревьям).
  • Если новая точка находится между двумя линиями, значит, ее нет на корпусе. Сдаться.
  • В противном случае вставьте точку в верхнюю или нижнюю часть корпуса (в зависимости от того, какой из них имеет более близкий отрезок линии).
  • Если вставка острия превратила соседние точки во внутренние углы, то они не находятся на корпусе. Сдаться.
  • Работайте с крайними случаями, такими как новая крайняя левая точка, вертикальные точки и т. Д.
  • Продолжайте до тех пор, пока не будет обработано желаемое количество точек.
person Craig Gidney    schedule 14.01.2011
comment
Я писал примерно такой же ответ, когда появился ваш ответ. - person oosterwal; 15.01.2011

arrow_upward
0
arrow_downward

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

person mbeckish    schedule 14.01.2011