最短路径和放大器;测地线 [英] shortest paths & geodesics

问题描述

给出完全由四边形的网格，在每一个顶点有n价（其中n> = 3），并且不在同一平面上，我需要找到从封闭集合每个顶点的网格中距离种子顶点。也就是说，给出一个或多个网格顶点（种子集），我需要建立一个距离图存储在结实每个网格顶点（其中将有来自自己距离0）的距离。

given a mesh made entirely of quads, where every vertex has valence n (with n >= 3), and does not lie on the same plane, I need to find the distance of every vertex in the mesh from a closed set of seed vertices. That is, given one or more mesh vertices (a seed set), I need to build a distance map that stores the distance of each mesh vertex from the seed set (which will have distance 0 from themselves).

花一些时间来寻找可能的解决方案后，我得到了如下图：

after spending some time searching for possible solutions, I got the following picture:

1）它是不平凡的，并且在过去20年左右的时间不同的方法已经被开发

1) it is not trivial, and different approaches have been developed during the last 20 years or so

2）每一个算法，考虑到三维域限制到三角域

2) every algorithm that takes into account a 3d domain is restricted to a triangular domain

说，这是我得到的画面：

said that, this is the picture I got:

Dijkstra算法可以用作一个方法来找到2个顶点之间的最短路径，以下的网状物的边缘，但它是非常不准确的，并会导致错误的短程线。 Lanthier（LA）提出了一个改进，但错误还是相当高的。

Dijkstra algorithm may be used as a way to find the shortest path between 2 vertices, following the edges of the mesh, but it is very inaccurate and will lead to an erroneous geodesic. Lanthier (LA) proposed an improvement, but the error is still quite high.

金梅尔和Sethian（KS）提出了一个快速行进方法-FMM-解决了程函方程，解决这一问题计算波的传播开始于种子点和记录波穿过每个顶点的时间。不幸的是，该算法，而足以实现简单，仍然带来了相当不准确的结果，和护理，必须注意避免钝角三角形，或把它们中的一个非常特殊的方式。 Novotni（NV）讨论了（KS）precision在一个单一的种子方案的问题，但目前还不清楚，我如果：

Kimmel and Sethian (KS) proposed a Fast Marching Method -FMM- to solve the Eikonal equation, addressing the issue calculating the propagation of a wave starting at the seed points and recording the time the wave crosses every vertex. Unfortunately this algorithm, while simple enough to implement, still brings a quite inaccurate result, and care has to be taken to avoid obtuse triangles, or treat them in a very special way. Novotni (NV) addressed the problem of (KS) precision in a single seed scenario, but it is unclear to me if:

一）它仍然从钝角问题遭受

a) it still suffers from the obtuse angle problem

b）以多个种子点方案中使用时，一个单一的FMM已被用于每一个种子，以便找到用于从每个种子每个网格顶点的最小距离来实现（即，在一个10种子点的情况下， FMM将具有每每个网格顶点要运行10次）

b) when used in a multiple seed points scenario, a single FMM has to be implemented for every single seed in order to find the minimum distance for each mesh vertex from each seed (that is, in a 10 seed points scenario, FMM would have to be run 10 times per each mesh vertex)

在另一边，一个确切的算法-MMP-，导致0错误已经由米歇尔＆放psented $ P $;人。 （MI）在87和AFAIK从未真正implmeneted（可能是由于所需的计算功率）。在完全相同的方式，Surazhsky和放大器;人。 （SU）提供了一种基于对MMP的替代精确算法应该优于后者在速度方面，仍然导致一个正确的结果。不幸的是计算所需的计算能力，即使比原来的MMP少得多，是仍然足够高，使得实时交互式实现并不在此时是可行的。 （SU）也提出了自己的具体算法，他们所谓的平确切的近似值。它应该采取FMM的相同的计算时间，而带来的误差只有1/5，但是：

On the other side, an exact algorithm -MMP- that leads to 0 error has been presented by Mitchell & al. (MI) in 87, and AFAIK has never been really implmeneted (probably due to the computing power required). On the same exact approach, Surazhsky & al. (SU) provided an alternative exact algorithm based on MMP that should outperform the latter in terms of speed, still leading to a correct result. Unfortunately the computing power required for the calculation, even if much less than the original MMP, is still high enough so that realtime interactive implementation is not feasible at this time. (SU) also proposed an approximation of their exact algorithm, what they called flat-exact. It should take the same computational time of FMM, while bringing only 1/5th of the error, but:

C）这我不清楚，如果它可以在一个多种子的情况下使用。

c) it is unclear to me if it can be used in a multiple seeds scenario.

其它精确最短路径算法已经提出由陈和放大器;汉（CH）和卡普尔（KP），但在第一个绝对速度慢，二是太复杂，在实践中实现的。

Other exact shortest path algorithms have been proposed by Chen & Han (CH) and Kapoor (KP), but while the first is absolutely slow, the second is just too complicated to be implemented in practice.

所以..底线是：我需要一个集合，而不是2点之间的最短路径的距离

so.. the bottom line is: I need a distance from a set, not the shortest path between 2 points.

如果我是正确的，

无论我用FMM获得在一个单一的通行证从一组距离的每一个顶点，

either I use FMM to get a distance of each vertex from a set in a single pass,

- 或 -

使用另一种算法，从每一个网格顶点到每一个种子点calulate测地，找到最短的一个（如果我这样做是正确，这将意味着，呼吁每一个种子点为每个网格顶点的算法，即，在万顶网和结实的50分，我将不得不计算，以获得50万测地线10,000最短的一个）

use another algorithm to calulate the geodesic from every mesh vertex to every seed point and find the shortest one (and If I got it right that would mean calling that algorithm on every seed point for every mesh vertex, that is, on a 10,000 vertex mesh and a seed set of 50 points, I would have to calculate 500,000 geodesics in order to get the 10,000 shortest one)

我缺少的东西？是FMM处理在一个单一的行程多种子距离的唯一途径？有人知道，如果平精确算法可以在多个种子点的情况可以用吗？

Am I missing something? is FMM the only way to deal with multiple seeds distances in a single pass? Someone knows if the flat-exact algorithm may be used in a multiple seed points scenario?

日Thnx

注：

（LA）：Lanthier和放大器;人。 逼近加权最短路径多面体表面

(LA): Lanthier & al. "Approximating weighted shortest paths on polyhedral surfaces"

（KS）：金梅尔，Sethian计算流形上的测地线路径

(KS): Kimmel, Sethian "Computing geodesic paths on manifolds"

（NV）：Novotni计算三角网格测量距离

(NV): Novotni "Computing geodesic distances on triangular meshes"

（MI）：米切尔和放大器;人。 离散测地问题

(MI): Mitchell & al. "The discrete geodesic problem"

（SU）：Surazhsky，基尔萨诺夫和放大器;人。 快速精确的和近似的测地线的网格

(SU): Surazhsky, Kirsanov & al. "Fast exact and approximate geodesics on meshes"

（CH）：陈涵，正多面体的最短路径

(CH): Chen, Han, "Shortest paths on polyhedron"

（KP）：卡普尔的geodeisc最短路径有效的计算

(KP): Kapoor "Efficient computation of geodeisc shortest paths"

推荐答案

有一个新的文章，讨论究竟如何解决你的问题：的热测地线。 （刚发现它，它提醒你的问题我）的想法是，热传导方程可以被认为是描述一些中心点颗粒的扩散。虽然模型的随机扩散，如果您运行很短的时间足够热方程那么获得从A到B的任何颗粒必须遵循的最短路径，数学，你可以得到距离的估计。

There is a new paper that discusses exactly how to solve your problem: Geodesics in Heat. (Just spotted it and it reminded me of your question.) The idea is that the heat equation can be thought of as describing the diffusion of particles from some central point. Although it models random diffusion, if you run the heat equation for a short enough time then any particles that get from A to B must have followed the shortest path so mathematically you can get an estimate of distance.

美中不足的是，遵循路径接近最短路径是微小颗粒的比例，所以你必须要解决，在某些地区开始大，并迅速结束了其他地方的小差分方程。这是不可能得到很好的表现数字。诀窍是，对于较大吨，即使它不能正确地测量距离，它确实给的距离函数的梯度，这可与其它方法一起使用，以获得距离

The catch is that the proportion of particles that follow a path close to the shortest path is tiny so you have to solve a differential equation that starts large at some region and rapidly ends up small elsewhere. That's not likely to be well behaved numerically. The trick is that for larger t, even though it doesn't measure distance correctly, it does give the gradient of the distance function and this can be used with other methods to get the distance.

TL; DR链接的文件解决了网格从每一个点的距离，以任何的子域，包括有限套种子点

TL;DR The linked paper solves distance from every point in a mesh to any subdomain, including finite sets of seed points.

呵呵......我还没有测试它自己。

Oh...and I haven't tested it myself.

这篇关于最短路径和放大器;测地线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！