Триангуляция Полигона с "отверстием"

[Roman777]

Добрый день!
Интересуют алгоритмы триангуляции произвольного многоуголника (не самопересекающегося) с отверстиями (1-н и более) внутри. Без отверстий, триангулировать, вроде бы, получилось. А вот с ними как-то посложнее.
Пока думаю, что необходимо сводить такой "полигон" к полигонам без отверстий, тобишь разрезать его на отдельные кусочки через эти "дырки", так чтобы внутри каждого кусочка отверстий не было.

Наверняка кто-то уже работал с подобным вопросом, подскажите направление, плз)

[jetyb]

Каждый многоугольник и каждая дырка - не пересекающийся набор треугольников.

Сделайте сперва "вычитание" одного треугольника ABC из другого DEF: триангуляцию первого треугольника, ABC не пересекающуюся с вычитаемым треугольником DEF.

[Roman777]

Думаю, что Ваше предложение должно рассматриваться при определённых случаях (алгоритмах) триангуляции произвольного полигона без отверстий, типа того же Делоне, я правильно понимаю? Я же пока выполнил триангуляцию с "ухообрезанием". В рамках данного алгоритма (ухообрезание) триангуляции, описанный Вами метод мне кажется недостижим...

[IDoNotExist]

Я же пока выполнил триангуляцию с "ухообрезанием".

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

[Roman777]

Получается у тебя триангуляция идёт по последовательному набору точек (полилиния)

В общем то да. И проблем нет. Просто сложности появляются, если этих отверстий несколько (много) на полигоне, поскольку такую диагональ уже может и не получиться провести непосредственно до этой полилинии без пересечения других отверстий. Собственно, поэтому думаю о похожем методе деления этого полигона на кусочки, которые будут отрезаться по 1 куску сквозь отверстие (надо только алгоритм продумать), чтобы получить несколько полигончиков уже без отверстий. Но тему создавал не потому что у меня появились конкретные проблемы, а просто хотел узнать ещё разные направления и способы решения данной задачи, чтобы определиться, куда стоит копать, а может быть и попробовать разное)

[IDoNotExist]

Алгоритмы булевого вырезания как вариант.