Есть ли какой-либо алгоритм , который позволяет разбить вогнутый многоугольник на выпуклые или представлять собой многоугольник треугольниками. I знаю есть запись в Википедии о триангуляции, но это на самом деле не помогает мне. I знаю У нас уже есть вопрос о Stackoverflow, но это мне не очень полезно. Я был бы признателен за любой псевдокод (или реальный код на понятном языке программирования), чтобы сломать вогнутый многоугольник в выпуклых или треугольниках. Btw, алгоритм должен также работать для выпуклых многоугольников и не вмешиваться в них.Разделенный вогнутый многоугольник в выпуклых
Спасибо за помощь!
Как вы представляете многоугольник? Вы знаете, как определить, является ли вершина выпуклой или вогнутой? – Beta
Он представлен n точками по координатам. Да, все внутренние углы должны быть меньше 180 градусов, чтобы быть выпуклым многоугольником. – borchero
Итак, найдите выпуклую вершину (там должны быть некоторые) и разделим ее как треугольник. {..., A, B, ** C **, D, E, ...} => {..., A, B, D, E, ...} + {B, C, D} , Продолжайте, пока у вас нет треугольников. Это работает для всех полигонов без отверстий, выпуклых или вогнутых. – Beta