У меня есть местность, представленная большим набором точек в 3D-space. Как лучше триангулировать?
Я могу просто спроецировать все точки на 2D-space, затем сделать триангуляцию Делоне за время O(n * log(n)) и поднять ее обратно на прежнюю высоту. Но достаточно ли это хорошо? Я слышал о триангуляции Делоне во времени O(n * log(log(n))) в некоторых особых случаях. Возможно ли это в моем случае? Или, может быть, я должен использовать какой-то алгоритм приближения?
Проекция и триангуляция Делоне в 2D, безусловно, являются хорошим решением, позволяющим генерировать треугольники правильной формы. Для ландшафта вам также может понадобиться применить определенные ребра, поэтому ищите триангуляцию Делоне с ограничениями.
Что касается времени выполнения: для реальных данных вы можете предположить линейное время выполнения. Если важна производительность, убедитесь, что ваши входные данные не вырождены: сканирующие устройства часто возвращают точки на сетке. Вы можете улучшить ситуацию, добавив немного шума.
На самом деле вы сделали свою домашнюю работу. Хорошо, триангуляция Делоне - очень хорошее решение вашей проблемы.
