Многоугольник в задаче обобщения многоугольника

9

Я хотел бы извиниться перед всеми постами ниже. Выбрал не тот форум, чтобы опубликовать это в оригинале. Однако вместо того, чтобы сделать это пустой тратой, я переработал вопрос, чтобы он стал настоящей проблемой «теоретической информатики».

Задача: Создать алгоритм, который принимает набор из n упорядоченных точек в 2D-плоскости, которые образуют контур простого многоугольника A, который может быть или не быть вогнутым, и создает новый многоугольник B с m точками, так что:

  1. все точки в A содержатся в B
  2. 3 <= m <n
  3. B - многоугольник в наборе всех B с наименьшей площадью
  4. B должен быть простым многоугольником (то есть без самопересечений).
  5. Вход в алгоритм - полигон A и «m».
  6. Совпадение сегментов в B с сегментами в A допускается.

Некоторые примеры входных и ожидаемых результатов:

  1. Если A является квадратом, а m равно 3, то B будет треугольником с наименьшей площадью поверхности, содержащей A.
  2. Если A является шестиугольником, а m равно 4, то B будет четырехугольником с наименьшей площадью поверхности, которая содержит A.

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

Тирлан
источник
1
@Joe: Не верно: если A - квадрат, то Тириан просит треугольник минимальной площади, содержащий A. С другой стороны, если A - треугольник (Nзнак равно3) тогда действительно нет действительного решения.
Джефф
3
Думаю, добавлю 17 к моему первому комментарию. Почему 20?
Джефф
3
Не является ли БПФ низким порогом для «сложного»?
Сашо Николов
2
Я не думаю, что это совершенно верно, что проблема вообще не изменится, если вы, скажем, установите m = 3. Проблема заключается в том, что вам может потребоваться экспонента по времени в m, и это нормально, если m фиксировано для некоторого числа, но это не хорошо, если m является частью ввода.
Суреш Венкат
5
«все знают, в чем проблема» - это не правда. Мы спрашиваем, потому что выбор, не указанный, имеет значение.
Суреш Венкат

Ответы:

10

Я не знаю, как выглядят ваши полигоны, но, возможно, достаточно упрощенной версии алгоритма Рамера-Дугласа-Пекера :

  • для каждой выпуклой части рассчитайте площадьAJ из треугольников пяпя+1пя+2 состоит из трех последовательных точек;
  • для каждой вогнутой части рассчитать площадьВК из двух треугольников пяпя'пя+1 а также пя+1пя+2'пя+2 образованный расширением двух точек пя,пя+2 и средняя точка пя+1
  • рассчитать мяN{AJ,ВК} и удалить соответствующую точку (и точки смещения, если операция выполняется на вогнутой части);
  • цикл до N-м точки были удалены.

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

Для более сложных алгоритмов вы можете искать « методы обобщения полигонов », хотя ваше первое условие (точки в A содержатся в B) подразумевает некоторые дополнительные операции масштабирования.

Марцио де Биаси
источник
@Suresh: я почти уверен, что текущие 4 голоса за прозрачность, а не за (почти тривиальный) алгоритм :)
Marzio De Biasi
1
Это страдает от той же проблемы, что и алгоритмы Рамера-Дугласа-Пекера: выходной результат не обязательно будет простым многоугольником!
Джефф
1
@Jeffe: вы правы, но (далеко не оптимально, если многоугольник сложен) можно избежать упрощений, которые приводят к конфликту . В конце, если есть другие точки, которые необходимо удалить, но нельзя избежать непростого многоугольника, используйте метод разрешения конфликтов (например, рассчитайте точки пересечения и полностью отбросьте «дыры»). Однако я хотел бы увидеть реальный пример из ОП.
Марцио Де Биаси,
1
@MarzioDeBiasi That might work. But it might not. I think it's possible for every simplification you describe to cause a self-intersection. And "throwing out loops" can makes things worse, not better. This is probably a fine solution in practice, but remember where we are!
Jeffε
Спасибо, Марцио, теперь я, по крайней мере, знаю, как называются такие проблемы! К сожалению, решение, которое вы дали, это то, что (3) и (4) входят в мои предложенные решения, и (4) имеет проблему с этим. Элипсы, которые очень растянуты и, следовательно, имеют острые кончики с углами примерно 30 градусов и менее, легко нарушают требование (1).
Тирлан
6

Я давно написал статью, в которой подробно описан алгоритм линейного времени для нахождения наименьшего треугольника площади, включающего множество точек (или многоугольник):

J. O'Rourke, Alok Aggarwal, Sanjeev Maddila, Michael Baldwin, "Оптимальный алгоритм для нахождения минимальных вмещающих треугольников", J. Algorithms , 1986, 7 : 258--269. Link .

За нашей работой следовал общий алгоритм:

«Минимальная площадь, описывающая многоугольники», Alok Aggarwal, JS Chang и Chee K. Yap, The Visual Computer , том 1, номер 2 (1985), 112-117. Link .

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

Джозеф О'Рурк
источник