Точки облака Алгоритм триангуляции

Question

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

Может ли кто-нибудь помочь мне понять, как триангулировать эти точки? Может быть, небольшая часть кода или вообще алгоритм, который мне нужно реализовать?

Answer 1

Я думаю, вам нужна общая триангуляция в первую очередь, а затем исправить все, что не является Делоне-законным?

очень плохой алгоритм триангуляции (с плохим углом вектором) выходит что-то вроде этого:

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

(iiiA) Для каждой другой точки плоскости, если точка лежит в треугольнике, выведите из нее три треугольника, соединяя точку с тремя вершинами треугольника, в котором она лежит. (iiiB) Если это лежит на ребре (немного маловероятно для 100 пунктов, я думаю, вы можете пропустить его), соедините его с двумя другими вершинами четырехстороннего, в котором он лежит.

Я думаю, вы могли бы начать с этого. Облако будет полностью триангулировано, но, возможно, более половины краев будет незаконным. Затем вы можете продолжить исправление (перевертывание) необходимых краев.

Если вы обнаружили проблемы с его реализацией, я мог бы предоставить несколько примеров кода, чтобы вы начали. Теперь имейте в виду, что возвращаемое значение алгоритма было бы удобным быть множеством/вектором треугольников; таким образом вы можете манипулировать ими и изменять свой цвет индивидуально.

Answer 2

Я сильно предложить не кодирования любой алгоритм триангуляции Делоне с нуля. Если бы я делал это, чтобы получить интуитивное понимание того, как выглядит результат алгоритма, я бы взял Johnathan Shewchuk's Triangle code и изменил его, чтобы назначить разные цвета и т. Д.

Если, однако, вы достаточно мотивированы, чтобы реализовать это с нуля , тогда мое предложение состояло бы в том, чтобы сначала реализовать триангуляцию 2D Delaunay, прежде чем заниматься 3D-версией.

Answer 3

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