相关疑难解决方法(0)

给定一个完全由四边形组成的网格,其中每个顶点都具有效价n(n> = 3),并且不在同一平面上,我需要从一组封闭的种子顶点中找到网格中每个顶点的距离.也就是说,给定一个或多个网格顶点(种子集),我需要构建一个距离图,该距离图存储每个网格顶点距种子集的距离(距离自身的距离为0).

在花了一些时间寻找可能的解决方案之后,我得到了以下图片:

1)这不是微不足道的,并且在过去20年左右的时间里已经开发了不同的方法

2)考虑3d域的每个算法都限于三角域

说,这是我得到的图片:

Dijkstra算法可以用作在网格边缘之后找到2个顶点之间的最短路径的方法,但是它非常不准确并且将导致错误的测地线.Lanthier(洛杉矶)提出了改进,但错误仍然很高.

Kimmel和Sethian(KS)提出了一种快速行进方法-FMM-来解决Eikonal方程,解决计算从种子点开始的波传播并记录波穿过每个顶点的时间的问题.不幸的是,这个算法虽然简单易于实现,但仍然会带来非常不准确的结果,必须注意避免使用钝角三角形,或者以非常特殊的方式处理它们.Novotni(NV)解决了单个种子场景中(KS)精度的问题,但我不清楚是否:

a)它仍然受到钝角问题的困扰

b)当在多种子点场景中使用时,必须为每个种子实施单个FMM,以便从每个种子中找到每个网格顶点的最小距离(即,在10个种子点场景中,FMM将具有每个网格顶点运行10次)

另一方面,Mitchell等人提出了导致0错误的精确算法-MMP-.(MI)在87年,AFAIK从未真正被扼杀(可能是由于所需的计算能力).同样的方法,Surazhsky&al.(SU)提供了基于MMP的替代精确算法,其在速度方面应该优于后者,仍然导致正确的结果.不幸的是,计算所需的计算能力,即使比原始MMP小得多,仍然足够高,因此此时实时交互式实现是不可行的.(SU)也提出了他们的精确算法的近似,他们称之为平精确.它应该花费相同的FMM计算时间,同时只带来1/5的错误,但是:

c)我不清楚它是否可用于多种子方案.

Chen&Han(CH)和Kapoor(KP)已经提出了其他精确的最短路径算法,但是第一种算法绝对慢,第二种算法太复杂而无法在实践中实施.

所以..底线是:我需要一组距离,而不是两点之间的最短路径.

如果我做对了,

要么我使用FMM来获取单个通道中每个顶点的距离,

-要么-

使用另一种算法来计算从每个网格顶点到每个种子点的测地线,并找到最短的一个(如果我把它弄好,这意味着在每个网格顶点的每个种子点上调用该算法,即在10,000个顶点网格上和一个50分的种子集,我将不得不计算500,000测地线,以获得10,000最短的一个)

我错过了什么吗？FMM是一次通过多种种子距离的唯一方法吗？有人知道平面精确算法是否可用于多种子点场景？

日Thnx

笔记:

(洛杉矶):Lanthier等."在多面体表面上逼近加权最短路径"

(KS):Kimmel,Sethian"在流形上计算测地线路径"

(NV):Novotni"计算三角网格上的测地距离"

(MI):米切尔等人."离散测地线问题"

(SU):Surazhsky,Kirsanov等."网格上的快速精确和近似测地线"

(CH):Chen,Han,"多面体的最短路径"

(KP):Kapoor"高效计算geodeisc最短路径"

我试图找到三角形表面上两点之间的距离(测地距离).它看起来像一个基本的操作,并不是微不足道的.所以我想知道是否有任何库可以做到这一点？我的谷歌失败了,所以我非常感谢任何指针.

(我知道CGAL,scipy.spatial,但我在文档中找不到任何内容,如果我错过了某些内容,请告诉我)

我用google搜索"导航网格上的A*算法"只是为了得到错误的估算g值的方法,就像这样

或这个

通过总计蓝线段的长度,我们得到g值,但它被高估了(g值应该被低估).此算法将返回优化路径,但不保证最短路径.

我能想到的唯一方法是根据导航网格绘制可见性图.但这会花费太多内存.

有没有其他方法来计算导航网格中的最短路径？