учитывая сетку, состоящую полностью из четырехугольников, где каждая вершина имеет валентность n (при n> = 3) и не лежит на одной плоскости, мне нужно найти расстояние каждой вершины в сетке от замкнутого множества семенных вершин. То есть, учитывая одну или несколько вершин сетки (начальный набор), мне нужно построить карту расстояний, в которой будет храниться расстояние каждой вершины сетки от начального набора (который будет иметь расстояние 0 от себя).
потратив некоторое время на поиск возможных решений, я получил следующую картину:
1) это не тривиально, и за последние 20 лет были разработаны различные подходы
2) каждый алгоритм, учитывающий трехмерную область, ограничен треугольной областью
сказал, что вот картинка, которую я получил:
Алгоритм Дейкстры можно использовать как способ найти кратчайший путь между двумя вершинами, следуя краям сетки, но он очень неточен и приведет к ошибочной геодезической. Лантьер (Лос-Анджелес) предложил улучшение, но ошибка все еще довольно высока.
Киммель и Сетиан (KS) предложили метод быстрого марширования -FMM-, чтобы решить уравнение Эйконала, решая проблему расчета распространения волны, начиная с начальных точек, и регистрации времени, когда волна пересекает каждую вершину. К сожалению, этот алгоритм, хотя и достаточно простой для реализации, все же дает довольно неточный результат, и необходимо соблюдать осторожность, чтобы избежать тупых треугольников или относиться к ним совершенно особым образом.
Novotni (NV) решил проблему точности (KS) в сценарии с одним начальным числом, но мне неясно, если:
а) он все еще страдает от проблемы тупого угла
b) при использовании в сценарии с множеством начальных точек для каждого отдельного начального числа должен быть реализован один FMM, чтобы найти минимальное расстояние для каждой вершины сетки от каждого начального числа (то есть в сценарии с 10 начальными точками, FMM должен быть запущен 10 раз для каждой вершины сетки)
С другой стороны, Mitchell & al. Представил точный алгоритм -MMP-, который приводит к ошибке 0. (MI) в 87, и AFAIK никогда не был действительно реализован (вероятно, из-за требуемой вычислительной мощности). С точно таким же подходом Суражский и соавт. (SU) предоставил альтернативный точный алгоритм, основанный на MMP, который должен превзойти последний по скорости, все еще приводя к правильному результату. К сожалению, вычислительная мощность, необходимая для расчета, даже если она намного меньше, чем у исходного MMP, все еще достаточно высока, поэтому в настоящее время интерактивная реализация в реальном времени невозможна.
(SU) также предложил приближение их точного алгоритма, который они назвали точным. Это должно занять то же вычислительное время FMM, принося только 1/5 ошибки, но:
в) мне неясно, можно ли его использовать в сценарии с несколькими семенами.
Другие точные алгоритмы кратчайшего пути были предложены Ченом и Ханом (CH) и Капуром (KP), но, хотя первый является абсолютно медленным, второй слишком сложен для реализации на практике.
итак ... суть в том, что мне нужно расстояние от набора, а не кратчайший путь между двумя точками.
если я правильно понял,
либо я использую FMM, чтобы получить расстояние каждой вершины из набора за один проход,
-или-
использовать другой алгоритм для вычисления геодезической от каждой вершины сетки до каждой начальной точки и нахождения самой короткой (и если бы я понял это правильно, это означало бы вызов этого алгоритма в каждой начальной точке для каждой вершины сетки, то есть на Сетка вершин в 10 000 и начальный набор из 50 точек, я должен был бы вычислить 500 000 геодезических, чтобы получить 10 000 самых коротких)
Я что-то упустил? Является ли FMM единственным способом справиться с несколькими расстояниями семян за один проход? Кто-то знает, можно ли использовать алгоритм с точной плоской точкой в сценарии с множеством начальных точек?
Thnx
Примечания:
(LA): Lanthier & al. «Аппроксимация взвешенных кратчайших путей на многогранных поверхностях»
(KS): Kimmel, Sethian "Вычисление геодезических путей на многообразиях"
(NV): Новотни "Вычисление геодезических расстояний на треугольных сетках"
(МИ): Митчелл и др. «Дискретная геодезическая задача»
(SU): Суражский, Кирсанов и др. «Быстрые точные и приближенные геодезические на сетках»
(CH): Чен, Хан, "Кратчайшие пути на многограннике"
(КП): Капур "Эффективное вычисление кратчайших путей геодеков"