кратчайшие пути и геодезические

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

после некоторых затрат При поиске возможных решений я получил следующую картину:

1) это нетривиально, и за последние 20 лет или около того были разработаны различные подходы

2) каждый алгоритм, который учитывает трехмерную область, является ограничен треугольной областью

сказал, что это картина, которую я получил:

Алгоритм Дейкстры может использоваться как способ найти кратчайший путь между двумя вершинами, следуя краям сетки, но это очень неточно и приведет к ошибочной геодезической. Lanthier (LA) предложил улучшение, но ошибка все еще довольно высока.

Kimmel и Sethian (KS) предложили метод быстрого марша -FMM- для решения уравнения Эйконала, обращаясь к проблеме расчета распространения волны, начиная с исходные точки и запись времени, когда волна пересекает каждую вершину. К сожалению, этот алгоритм, хотя и достаточно прост в реализации, по-прежнему дает довольно неточный результат, и необходимо соблюдать осторожность, чтобы избегать тупых треугольников или обращаться с ними особым образом. Novotni (NV) обратился к проблеме точности (KS) в сценарии с одним начальным значением, но мне неясно, если:

a) он все еще страдает от проблемы тупого угла

b) при использовании в нескольких начальных условиях В сценарии точек, для каждого начального числа необходимо реализовать один FMM, чтобы найти минимальное расстояние для каждой вершины сетки от каждого начального числа (то есть, в сценарии с 10 начальными точками FMM необходимо будет запускать 10 раз для каждой сетки вершина)

С другой стороны, точный алгоритм -MMP-, приводящий к 0 ошибкам, был представлен Mitchell & al. (MI) в 87 году, и AFAIK никогда не применялся (вероятно, из-за требуемой вычислительной мощности). При таком же точном подходе Суражский и др. (SU) предоставил альтернативный точный алгоритм, основанный на MMP, который должен превосходить последний с точки зрения скорости, все же приводя к правильному результату. К сожалению, вычислительная мощность, необходимая для вычисления, даже если она намного меньше, чем у исходной MMP, все еще достаточно высока, так что интерактивная реализация в реальном времени в настоящее время невозможна. (SU) также предложили аппроксимацию своего точного алгоритма, которую они назвали плоской точной. Это должно занять столько же вычислительного времени, что и FMM,приводя только к 1/5 части ошибки, но:

c) мне неясно, можно ли его использовать в сценарии с несколькими начальными числами.

Другие точные алгоритмы кратчайшего пути были предложены Ченом и Ханом (CH ) и Капура (КП), но в то время как первый абсолютно медленный, второй слишком сложен для реализации на практике.

итак ... суть в следующем: мне нужно расстояние от набора, а не кратчайший путь между двумя точками.

если я понял,

либо я использую FMM для получения расстояния каждой вершины от набора за один проход,

-или-

использую другой алгоритм для вычисления геодезической от каждой вершины сетки до каждой исходной точки и найти самую короткую (и если бы я понял это правильно, это означало бы вызов этого алгоритма для каждой исходной точки для каждой вершины сетки, то есть на сетке из 10000 вершин и наборе начальных значений из 50 баллов, мне пришлось бы вычислить 500 000 геодезических, чтобы получить 10 000 самых коротких)

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

thnx

Примечания:

(LA): Lanthier & al. «Аппроксимация кратчайших взвешенных путей на многогранных поверхностях»

(KS): Киммель, Сетиан «Вычисление геодезических путей на многообразиях»

(NV): Новотни «Вычисление геодезических расстояний на треугольных сетках»

(MI): Mitchell и др. «Дискретная геодезическая задача»

(SU): Суражский, Кирсанов и др. «Быстрые точные и приближенные геодезические на сетках»

(CH): Chen, Han, «Кратчайшие пути на многограннике»

(KP): Kapoor «Эффективное вычисление кратчайших геодезических путей»