У меня есть область, которая представлена ограниченными триангуляциями Делоне. Я играю с проблемой нахождения пути между двумя точками. Я использую документ, предоставленный Марсело Каллманном, в качестве ориентира для решения этой проблемы. Однако вместо использования алгоритма воронки Шазеля, предложенного Kallmann paper link , я планирую использовать алгоритм поиска A *, который довольно эффективно планирует путь в сеточной среде.
Для функции эвристической стоимости я использую евклидово расстояние от текущего узла до целевого узла, а для выбора соседних узлов я рисую отрезок линии от текущей точки p до средней точки края треугольник. [Эта идея была предложена Каллманном]. Стоимость соседнего узла также определяется евклидовым расстоянием между ними.
Вот рисунок из Kallmann, демонстрирующий использование средней точки техники ребер для создания различных путей к треугольнику, содержащему целевой узел.
Теперь эта техника отлично работает, когда плотность треугольника в области недостаточно велика. Но скажем, выглядит ли сгенерированная триангуляция для множества точек следующим образом 
Мне было интересно, есть ли способ повысить эффективность алгоритма, используя какую-то другую технику, такую как IDA * или ID-DFS? Было предложено сокращение триангуляции A * (TRA *), но я не мог понять его, поскольку оно было слишком формально определено. Подробности метода TRA * можно найти в разделе 5 этой диссертации Демиена.
Буду признателен за некоторые мысли по этому поводу. Если какой-то код необходимо отправить, я отредактирую этот пост.