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

Question

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

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

Спасибо.

Answer 1

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

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

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

Если одноранговой подход не обращается к вам, используйте ваш любимый поисковик и искать параллельно триангуляции Делоне

Answer 2

Если сетка подключена с использованием линейных элементов (прямых сторон), единственный способ, которым вы можете иметь зазоры, - это то, что конечные точки на смежных ребрах не совпадают.

Вы можете проверить в пределах некоторой сферы допуска, должны ли быть сделаны две точки, но допуск должен быть меньше, чем самый короткий край в вашей сетке, или вы разрушите элементы.

Самое умное, что я могу придумать, это распараллелить работу. Разделите сетку на один кусок на поток/процесс и выполните проверку допуска на каждом из них.

Это может быть хорошая работа по сокращению карты. Или, возможно, GPU и CUDA будут хорошим способом.

Когда вы вычисляете расстояние между двумя точками, вы можете отказаться от дорогого квадратного корня и просто посмотреть на квадрат расстояния по сравнению с допуском.