algorithm - 分割二十面体 - 如何找到距离任意点最近的顶点

Question

我有一个应用程序可以通过分割二十面体来创建球体的近似值。笛卡尔顶点坐标被转换为球面坐标，因此所有顶点都位于单位球体的表面上。

接下来我需要做的是找到离球体表面任意点最近的顶点。我提出了两个简单的算法...

1. 蛮力搜索 - 对于少量顶点来说是可行的，但对于更精细的分割来说会过多。

2. 排序/索引搜索 - 按方位角和倾角将顶点排序为某种形式的顺序，然后创建粗略索引以通过限制其范围来加速暴力搜索。

我想知道是否有一种更微妙、希望性能更高的算法可以代替上述两种算法之一使用。

更新 1: 我刚刚回想起应用程序的另一部分，顶点存储有关其邻居的信息。我的新算法是

1. 选择一个任意的起始顶点。找到它的哪个邻居到要定位的点的距离更小。使用此邻居作为新的起始顶点。重复直到没有顶点的邻居与该点的距离更小。这个顶点离点最近。

Answer 1

浏览所有回复，我想我可能有失偏颇，但您所追求的很简单。我想。

因为你只处理位于球体上的点，你可以只从顶点到球体的中心放置一条线，从任意点到中心放置另一条线并求解之间创建的角度他们。越小越好。我认为最简单和最便宜的方法是点积。角度基本上不在其中。这是关于它的链接:http://www.kynd.info/library/mathandphysics/dotProduct_01/为了测试它们，我建议选择一个顶点，测试它，然后测试它的邻居。它应该总是在最小邻居的方向上(当你靠近你之后的顶点时，角度应该总是减小)

无论如何，我希望这就是您所追求的。哦，我在寻找您的分割算法时偶然发现了这个页面。很难找到;如果您可以发布指向它的链接，我认为这不仅对我自己有帮助。