Получить выпуклые многоугольники из вершины

Я пишу игру на XNA и сейчас работаю над поиском пути для ИИ.

На моей карте есть круглые препятствия, и я хотел бы использовать метод навигации по сетке (http://udn.epicgames.com/Three/NavigationMeshReference.html), поэтому предварительно мне нужно преобразовать эти препятствия в набор выпуклых многоугольников.

Примерно так: введите здесь описание изображения

Я долго искал в гугле, но не мог найти, как это сделать. Любая подсказка? Спасибо!


person Chemari    schedule 31.05.2013    source источник


Ответы (1)


Вам нужна триангуляция Делоне?

person Jason    schedule 31.05.2013
comment
Похоже, это хорошая отправная точка, затем удалите края, пока полученная форма остается выпуклой. - person Nuclearman; 31.05.2013
comment
Ура! это было именно то, что я искал! Тогда я могу получить диаграмму Вороного. Спасибо, Джейсон. - person Chemari; 31.05.2013