Преобразование формы в полигоны

Question

Есть ли простой (или нет) алгоритм, способный создавать многоугольники из замкнутого пути?

Пусть ш имеют следующий путь:

0,0; 2,0, 2,1; 1,1; 
1,2; 2,2; 2,3; 0,3; 

Мне нужно, чтобы иметь возможность создавать полигональные индексы для OpenGL буфера вершин. Язык, который я использую, - это C#.

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

Edit:

Ответ 1 предлагает выбрать точку и соединить его с другими не связанными точками, это работает отлично представлено в форме ответа, но он не будет работать на форму я разместил, формы выше выглядит следующим образом:

Answer 1

Преобразование треугольников либо легко или трудно, в зависимости от того, что ваши требования и насколько хорошо вы хотите сделать это.

Если многоугольник является выпуклым, самый простой способ заключается в использовании GL_TRIANGLES с indicies

0, 1, 2, 0, 2, 3, 0, 3, 4, ... 

Это будет выглядеть следующим образом:

Ситуация для вогнутых больше работы. Алгоритм, который также работает для вогнутых многоугольников (не с отверстиями!), - это метод обрезания ушей, описанный на wikipedia (на этой странице больше).

Все становится действительно интересным, когда вы хотите «хорошую» триангуляцию : избегайте тощих или маленьких треугольников, уменьшайте количество треугольников и т. д., а затем вы можете обменивать качество на скорость. Здесь я не буду вдаваться в какие-либо предварительные алгоритмы; поиск триангуляции многоугольника в Google даст вам много информации.

Что касается нормалей, если ваш многоугольник плоский (он скорее всего должен «быть»), тогда возьмите два несовпадающих ребра и перекрестите их (есть две нормали, и вы, вероятно, только хотите: вам нужно выбрать порядок, в котором вы поперечный продукте (по часовой стрелке или против часовой стрелки) на основе right hand rule.