Как сформировать вогнутую форму из выпуклой формы?

Question

Я пытаюсь обойти правило, позволяющее формировать только выпуклые формы в библиотеке SFML c ++.

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

То, что я хотел бы знать, это ...

• Что такое уравнение для проверки формы формы: что это такое и как оно работает?

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

• Какая лучшая практика для достижения моей цели?

Спасибо!

---

Answer 1

Вы можете проверить форму выпуклой оболочки, обойдя все края и проверив, что следующий край всегда движется в одном и том же направлении (влево / вправо).Это быстрый и дешевый алгоритм.Вот реализация этого здесь: en.wikipedia.org / wiki / Graham_scan

Если у вас нет выпуклой оболочки, выполните алгоритм обтекания пакета, чтобы получить выпуклую оболочку, котораяохватывает все ваши очки (снова довольно быстро). ru.wikipedia.org / wiki / Gift_wrapping_algorithm

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

Рекурсия теперь ваш друг: выполните точно такой же процесс для каждой из подформВы только что сделали.

Я использовал эту технику для проверки точки, содержащейся в произвольной форме: то есть точка должна быть внутри выпуклой оболочки (легко проверить), но не какая-либо из подгрупп.формы, или их подформы, или их подформы ....

Answer 2

Библиотека Boost Geometry , которая была опубликована вчера , имеет реализацию Convex Hull algorithm. Картина говорит более тысячи слов:

Хотя это создает «новую» форму, которая не является вогнутой (то есть выпуклой); Это может или не может быть именно то, что вы хотите. Тем не менее, в процессе работы алгоритм связан с способностью классифицировать форму вогнутой / выпуклой, так что вам, вероятно, будет интересна библиотека.

Общая информация об алгоритме выпуклой оболочки:

• http://en.wikipedia.org/wiki/Convex_hull
• http://en.wikipedia.org/wiki/Convex_hull_algorithms

---

Поскольку Адриан Джапон более или менее предположил, что «тестирование попадания» (тест сдерживания) является обычной причиной заботиться о выпуклой / вогнутой геометрии, без дальнейших церемоний я выделю соответствующий алгоритм Boost Geometry для этого: within.

_{Опять же, потому что картинка такая красивая. Обратите внимание, что хотя на рисунке предлагается запросить точку для многоугольника, алгоритмы являются полностью общими и могут использоваться для проверки полной локализации на n -мерных полигонах в другом}

Answer 3

Хорошо, просто соберите всю информацию вместе:

• Чтобы проверить согласованность полигонов, посмотрите на эту страницу , предоставленную Адрианом Тейлором
• Один из способов достижения моей цели - использовать монотонную декомпозицию и триангуляцию
• Вы можете узнать о монотонной декомпозиции на этом прекрасном сайте : (краткое изложение ниже)

• Наконец, триангулируйте теперь монотонные формы, используя информацию в этой Powerpoint :

  1. Вставьте u1 и u2 в стек.
  2. j = 3 / * j - индекс текущей вершины * /
  3. u = uj
  4. Случай (i): u смежен с v1, но не vi.добавить диагонали uv2, uv3,…, uvi.поп vi, vi-1,…, v1 из стека.нажмите vi, u в стеке.Случай (ii): u смежен с vi, но не v1.в то время как i> 1 и угол uvivi-1 < добавьте диагональ uvi-1 pop vi из стека, в то время как push u Случай (iii): u рядом с v1 и vi.добавить диагонали uv2, uv3,…, uvi-1.выход </li>
  5. j = j + 1 Перейдите к шагу 3.

---

**Note:**
By “adjacent” we mean connected by an edge in P.   
Recall that v1 is the bottom of the stack, vi is the top.    
By “Push” we mean push the item(s) to the back of the list    

---

Надеюсь, это кому-нибудь поможет ..... но я все еще ищу какие-то лучшие / более быстрые решения.

Answer 4

Полагаю, у вас есть полигон в виде списка точек, очень простой способ - обойти ваш полигон и рассмотреть последовательность триплетов последовательных точек (A, B, C).

ТогдаВы просто проверяете, что в какой-то момент det (AB, BC) меняет свой знак, где

det (AB, AC) = (x_a-x_b) (yc-yb) - (x_c-x_b) (y_a-y_b)

Answer 5

О чем стоит подумать:

• Левосторонние и правосторонние углы (знак перекрестного продукта - простой способ различения). Все углы в выпуклой форме одинаковы.

• Расширение ребра и добавление новой вершины может дать вам лучшие результаты, чем добавление ребер между существующими вершинами.