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

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

edit: Распространенным расширением этого метода является удаление слабых треугольников на корпусе, где самый длинный край или наименьший внутренний угол превышает заданное значение. Это сформирует лучший вогнутый корпус.

В CGAL есть необходимый вам инструмент: Ограниченные триангуляции

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

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

Чтобы дать вам еще несколько вариантов выбора библиотек:

Полибул. Я никогда не пробовал этот, но он выглядит многообещающим: http://www.complex-a5.ru/polyboolean/index.html

Универсальный многоугольник Clipper. Это очень хорошо работает на практике и выполняет триангуляцию, а также обрезку и отверстия: http://www.cs.man.ac.uk/~toby/alan/software/

Моя личная рекомендация: используйте тесселяцию из GLU (OpenGL Utility Library). Код надежен, быстрее, чем GPC, и генерирует меньше треугольников. Вам не нужен инициализированный OpenGL-дескриптор или что-то подобное, чтобы использовать библиотеку.

Если вам не нравится идея включения системных библиотек OpenGL в приложение DirectX, есть решение: просто загрузите эталонный код реализации SGI OpenGL и снимите с него триангулятор. Он просто использует имена OpenGL-Typedef и набор перечислений. Вот и все. Вы можете извлечь код и сделать автономную библиотеку за час или два.

В общем, я бы посоветовал использовать что-то, что уже работает, и не начинать писать свою собственную триангуляцию.

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

Я написал алгоритм триангуляции на языке C для компании, с которой работаю. На то, чтобы основной алгоритм заработал, потребовалось два дня. Чтобы заставить его работать со всеми видами дегенерированных входных данных, потребовалось еще два года (я не работал над этим полный рабочий день, но поверьте мне - я потратил на это больше времени, чем должен был).

Это обычная проблема в анализе методом конечных элементов. Это называется «автоматическое создание сетки». Google нашел этот сайт со ссылками на коммерческое программное обеспечение и программное обеспечение с открытым исходным кодом. Обычно они предполагают, что для начала требуется какое-то представление геометрии в САПР.

Библиотека треугольников Джонатана Шевчука феноменален; Раньше я использовал его для автоматизации триангуляции. Вы можете попросить его попытаться избежать маленьких / узких треугольников и т. д., Чтобы вы получили «хорошие» триангуляции вместо какой-либо триангуляции.

Другой вариант (с очень гибкой лицензией) - портировать алгоритм из VTK:

vtkDelaunay2D

Этот алгоритм работает довольно хорошо. Использование напрямую возможно, но требует наличия ссылок на VTK, которые могут иметь больше накладных расходов, чем вы хотите (хотя у него также есть много других хороших функций).

Он поддерживает ограничения (отверстия / границы и т. д.), А также триангуляцию поверхности, которая не обязательно находится в плоскости XY. Он также поддерживает некоторые функции, которые я нигде не видел (см. Примечания к значениям Alpha).

попробуйте libtess2

https://code.google.com/p/libtess2/downloads/list

основан на оригинальном тесселаторе SGI GLU (с либеральным лицензированием). Решает некоторые проблемы с управлением памятью, связанные с большим количеством мелких маллокаторов.

Я обнаружил, что библиотека poly2tri - именно то, что мне нужно для триангуляции. Он создает гораздо более чистую сетку, чем другие библиотеки, которые я пробовал (включая libtess), а также поддерживает дыры. Он переведен на несколько языков. Лицензия - Новый BSD, поэтому вы можете использовать ее в любом проекте.

Библиотека Poly2tri в Google Code

Я реализовал трехмерный многоугольник триангулятор на C#, используя метод отсечения ушей. Он прост в использовании, поддерживает отверстия, численно устойчив и поддерживает произвольные (не самопересекающиеся) выпуклые / невыпуклые многоугольники.