Есть ли современная реализации алгоритма триангуляции невыпуклого многоугольника с отверстиями?

Question

[Даниил]

Для этих целей я нашёл две различные библиотеки, но все они не подходят:

1) https://algolist.manual.ru/maths/geom/polygon/deco... - тут выложен исходный код.
Её проблема, в том что данные ограниченны стичными структурами.( Да, можно выделить массив на 1 миллион вершин, и потерять всего где-то 40-80мб оперативной памяти, но это ужасно в 2024 году) . Я пытался переписать её на современный код, но часть реализации вызывает сомнения. Есть места где странно объявлены переменные. И в целом реализация довольно запутанна, авторы не любят начинать массивы с 0, и везде пропускают нулевой элемент, используя его как NULL.

2) https://github.com/PhilipLudington/Triangle - прекрасная библиотека, но триангулирует лишь выпуклые многоугольники, хоть и с отверстиями.

Есть ли библиотека, для интересующей меня задачи?

Comments

[Wataru]

"стичными структурами"? Что такое стичные структуры?

По поводу второй библиотеки, что будет, если передать ей многоугольник с дырками на границе? Если она так работает, то можно просто построить выпуклую оболочку вашего многоугольника и передать ее в библиотеку. А дырки новые будут ограничены стороной выпуклой оболочки и невошедшими в нее сторонами вашего невыпуклого многоугольника.

[Mercury13]

Poly2tri — катит?

[mayton2019]

( Да, можно выделить массив на 1 миллион вершин, и потерять всего где-то 40-80мб оперативной памяти, но это ужасно в 2024 году) .

Это странно. В 2024 минимальный футпринт браузера уже идет от гигабайтов. И почму вы что-то там
боитесь непонятно. Что у вас за железо? Вместо серверов - ардуино?

И в целом реализация довольно запутанна, авторы не любят начинать массивы с 0, и везде пропускают нулевой элемент, используя его как NULL.

В этом есть следы автоматической транспилляции кода с одного языка на другой. Возможно
оригиналом был Pascal. Вот отсюда и идет индекс с единички.