У меня есть облако со случайно распределенными точками и еще одно облако с теми же точками, но перемещающееся случайным образом. Таким образом, каждой точке облака A соответствует точка облака B.
Теперь я хочу триангулировать оба облака с помощью одной и той же треугольной сетки, найдя сетку с наименьшим количеством пересечений в обоих облаках.
Любые идеи?
Спасибо
Создайте случайную триангуляцию точек в облаке A и измерьте количество пересечений как в A, так и в B. Затем примените симуляцию отжиг для случайного добавления/удаления/перемещения ребер, которые сохраняют интересующие вас функции триангуляции, сохраняя и измеряя количество пересечений после каждой итерации.
В качестве отправной точки, если вы не хотите начинать со случайного набора ребер, вы можете начать с триангуляции Делони в A, а затем измерить общее количество пересечений в B. Приступить к методу имитации отжига, как и раньше. .
Первый очень простой подход, сделать (Делоне) триангуляцию на полусдвинутых позициях и использовать ее для обоих облаков. Это может дать хороший результат, если движение не слишком большое.
Триангуляция имеет пересечения тогда и только тогда, когда существуют треугольники с отрицательной ориентацией. Таким образом, хорошая триангуляция для обоих облаков состоит из треугольников, положительно ориентированных в обоих облаках.
Подход может быть, очень похожим на то, что упоминалось и, чтобы создать начальную триангуляцию в облаке A и попытаться локально восстановить отрицательно ориентированные треугольники в облаке B. Вероятно, стандартное переворачивание может решить эту проблему.
Я думаю, что можно проверить, какие точки (область) не могут быть хорошо триангулированы в обоих облаках, сделав пересечение треугольников с положительной ориентацией на обоих облаках и ища точки, которые не находятся ни в одном треугольнике пересечения. Для этого достаточно (нужно) взять треугольники узла за соседнюю область (с соседними узлами).
