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

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

alt text

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

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

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

Мне интересно вот что:

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

Спасибо.


geometry computational-geometry convex-optimization convex-polygon
person Aaron Nicely    schedule 13.11.2010    source источник

Ответы (4)


arrow_upward
6
arrow_downward

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

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

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

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

С этого момента, пока перед любым лицом есть точки:

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

В итоге у вас будет выпуклый корпус.

person Tommy    schedule 13.11.2010

arrow_upward
1
arrow_downward

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

Это хорошо изученная проблема с рядом алгоритмов в книгах и в Интернете. Особенно распространен метод «охвата углов», например.

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

person winwaed    schedule 13.11.2010

arrow_upward
0
arrow_downward

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

person Doc Brown    schedule 13.11.2010

arrow_upward
0
arrow_downward

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

Пример в системе 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

person Dr. belisarius    schedule 13.11.2010