Разложение полигонов - удаление вогнутых точек для образования выпуклых многоугольников - PullRequest
Новая
       59

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

3 голосов
/ 13 ноября 2010

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

alt text

В настоящее время я пытаюсь сделать следующее:

  • Возьмите каждую точку из многоугольника
  • Проверьте точку, чтобы увидеть, попадает ли она в многоугольник, созданный остальной частью набора
  • Если истина, удалить точку
  • Если false, оставьте точку

Это работает в большинстве случаев, но в предыдущем случае точки в (2,3) и (2,4) не будут удалены. В обоих случаях одна из точек будет удалена, но другая не будет зависеть от порядка, в котором передается массив.

Что мне интересно, так это:

  1. Есть ли способ проверить, имеет ли один из этих случаев многоугольник, с которым я имею дело (IE: 3 точки сбоя подряд?)
    или
  2. Есть ли просто более эффективный способ создания выпуклых многоугольников?

Спасибо.

Ответы [ 4 ]

6 голосов
/ 13 ноября 2010

Я думаю, что, возможно, вы ищете выпуклую оболочку ?

Первый алгоритм, который приходит на ум, это QuickHull.Сначала возьмите крайнюю левую и правую точки l и r.Они должны быть на корпусе.

Построить первое предположение на корпусе, это две внешние грани, одна от l до r и одна от r до l.Таким образом, у вас есть многоугольник с нулевым объемом.

Разделите все оставшиеся точки на точки перед lr и перед rl.

С этого момента, пока любое лицо имеет какие-либо точки впередииз этого:

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

В конце у вас будет выпуклая оболочка.

1 голос
/ 13 ноября 2010

Почему бы просто не вычислить выпуклую оболочку точек?

Это хорошо изученная проблема с рядом алгоритмов в книгах и онлайн. Метод "широких углов" особенно распространен, например.

http://courses.csail.mit.edu/6.854/06/scribe/s25-rasmu-sweepline.pdf

0 голосов
/ 14 ноября 2010

Имейте в виду, что выпуклая оболочка уже реализована в некоторых языках / средах.

Пример в Mathematica: 

<< ComputationalGeometry`; 
   data2D = {{4.4, 14}, {6.7, 15.25}, {6.9,12.8}, {2.1, 11.1}, {9.5, 14.9}, 
             {13.2, 11.9}, {10.3, 12.3}, {6.8, 9.5}, {3.3, 7.7}, {0.6, 5.1}, 
             {5.3, 2.4}, {8.45, 4.7}, {11.5,9.6}, {13.8, 7.3}, {12.9, 3.1}, 
             {11, 1.1}};

PlanarGraphPlot[data2D, ConvexHull[data2D]]

Вывод:

alt text

0 голосов
/ 13 ноября 2010

То, что вы ищете, известно как поиск "выпуклой оболочки".Посмотрите здесь в википедии алгоритмы для этой проблемы.Алгоритм «упаковка подарков» прост в реализации.Когда вы нашли корпус, просто удалите все точки, которые не являются частью корпуса.

...