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

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

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

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

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

Дополнительно:

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

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

  • Poly2tri — катит?

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

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

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

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


    • + Заказать

     

    Для решения данной проблемы вы можете воспользоваться услугами фрилансеров. Мы выполним необходимую работу быстро и качественно.

     

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

      Да, существуют современные реализации алгоритмов триангуляции невыпуклых многоугольников с отверстиями. Один из таких алгоритмов называется алгоритмом "Ear Clipping". Этот алгоритм находит набор треугольников, которые полностью покрывают многоугольник, включая его отверстия.

      Пример реализации этого алгоритма на языке программирования PHP:

      function earClipping($polygon) {
    $triangles = [];
    $numVertices = count($polygon);
 
    while ($numVertices > 3) {
        for ($i = 0; $i = 0 && $BC >= 0 && $CA >= 0) || ($AB <= 0 && $BC <= 0 && $CA  0, 'y' => 0],
    ['x' => 0, 'y' => 4],
    ['x' => 4, 'y' => 4],
    ['x' => 4, 'y' => 0],
    ['x' => 2, 'y' => 2],
    ['x' => 1, 'y' => 1],
    ['x' => 3, 'y' => 1]
];
 
$triangulation = earClipping($polygon);
print_r($triangulation);

      Этот код реализует алгоритм "Ear Clipping" для триангуляции невыпуклых многоугольников с отверстиями. Передайте в функцию `earClipping()` массив точек многоугольника, включая отверстия, и она вернет массив треугольников, покрывающих многоугольник.

    Оставить комментарий