Алгоритм триангуляции облаков точек
Я хотел бы создать простое приложение на C ++, которое при 100 случайных точках (с их выпуклой оболочкой) будет триангулировать облако этих точек. Я искал эту тему, и я вижу, что триангуляция Делоне является вариантом, но я до сих пор не могу понять, как это реализовать (например, в c ++). Также на следующем уровне я хотел бы нарисовать все «незаконные» треугольники Делоне другим цветом, чтобы лучше показать и понять алгоритм Делоне.
Может ли кто-нибудь помочь мне понять, как триангулировать эти точки? Может быть, небольшая часть кода или вообще алгоритм, который мне нужно реализовать?
Решение
Я полагаю, вам сначала нужна общая триангуляция, а затем исправить все, что не легально по Делоне?
Алгоритм очень плохой триангуляции (с плохим вектором угла) выглядит примерно так:
(i) Получить выпуклую оболочку облака точек
(ii) Соединить случайную точку CH (удобно использовать первую) с каждой другой точкой CH (кроме, конечно, следующей и предыдущей, с которой она уже образует ребро).
(iiiA) Для любой другой точки на плоскости, если точка лежит в треугольнике, сделайте из него три треугольника, соединив точку с тремя вершинами треугольника, в котором она лежит.
(iiiB) Если он лежит на ребре (немного маловероятно для 100 точек, я думаю, вы можете его пропустить), соедините его с двумя другими вершинами четырехугольника, в котором он лежит.
Я думаю, вы могли бы начать с этого. Облако будет полностью триангулировано, но, возможно, более половины краев будет Делоне незаконным. Затем вы можете продолжать закреплять (переворачивать) необходимые края.
Если у вас возникнут проблемы с его реализацией, я мог бы предоставить пример кода для начала работы. А пока имейте в виду, что возвращаемым значением алгоритма было бы удобно быть набором / вектором треугольников; таким образом, вы можете манипулировать ими и менять их цвет по отдельности.
Другие решения
я мог бы сильно предложить не кодирование любого алгоритма триангуляции Делоне с нуля. Если бы я делал это, чтобы получить интуитивное понимание того, как выглядит вывод алгоритма, я бы взял Код треугольника Джонатана Шевчука и изменить его, чтобы назначить разные цвета и т. д.
Однако, если вы достаточно мотивированы, чтобы реализовать это с нуля, то я бы предложил сначала реализовать 2D триангуляцию Делоне, прежде чем приступить к 3D-версии.
Если вы хотите узнать об обоих алгоритмах триангуляции и их кодировании в C ++, то Совместный проект триангуляции кодирования в C ++ может показаться заманчивым, но это, безусловно, слишком сложно для начинающего. Поэтому я предлагаю вам сначала учиться о алгоритмические аспекты триангуляции а также основы C ++ отдельно прежде чем заняться объединенной проблемой.