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

C# Алгоритмы Триангуляция

1 ответ

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

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. Вот отсюда и идет индекс с единички.

Нужно решить такую задачу?

Опишите проблему, и специалист поможет с настройкой, исправлением ошибки или доработкой сайта. Подберём понятный план работ без лишней переписки.

Заказать помощь

Лучший ответ

Ирина WP Ответ

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

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

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

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()` массив точек многоугольника, включая отверстия, и она вернет массив треугольников, покрывающих многоугольник.

Другие ответы (0)

Пока нет других ответов. Будьте первым, кто поможет автору.

Ответить на вопрос

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

Вам также может быть интересно

VPN Как правильно настроить vless для Android TV? 1 ответ Pyrogram Как правильно зарегистрировать юзер бота в Telegram? 1 ответ печатные-платы Как заставить запускаться программу M3.exe от компании Hanxing AOI в инспекционной машине на Windows 7 Pro? 1 ответ Figma Баг с переносом слов в Figma? 1 ответ

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

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

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

Вам также может быть интересно

Ежедневно, круглосуточно