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

Question

我有一个应用程序，通过细分正二十面体来创建球面的近似形状。笛卡尔顶点坐标被转换为球面坐标，以使所有顶点都位于单位球面上。

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

1.暴力搜索-对于少量的顶点可以，但对于更精细的细分会过度。

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

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

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

1.选择任意一个起始顶点。找到与该点距离更近的邻居。使用该邻居作为新的起始顶点。重复此过程，直到顶点的邻居中没有比该点更近的。这个顶点就是距离该点最近的顶点。

- Andy C

---

一种不太困难的方法来找到一个好的起始顶点：在你的球体上覆盖一个100x100x100的网格，对于每个网格单元，预先计算距离该单元中心最近的顶点。现在，给定一个任意点，查找该点所在的单元格，并使用预先计算的最近顶点作为起始点。 - Tom Sirgedas

Answer 1

浏览回复后，我认为我可能有些偏离主题，但你所需要的很简单。因为你只处理位于球面上的点，所以你可以从顶点向球心下一条线，从任意点向球心下另一条线，并解决它们之间形成的角度。越小越好。我认为最简单和最便宜的方法是点积。这个角度基本上就是它的结果。这里有一个相关链接：http://www.kynd.info/library/mathandphysics/dotProduct_01/。对于测试它们，我建议选择一个顶点进行测试，然后测试其邻居。它应该总是指向最小的邻居（随着你接近你想要的顶点，角度应该始终减小）。无论如何，我希望这就是你想要的。哦，我在寻找你的细分算法时发现了这个页面。很难找到；如果你能发布一个链接，我认为它会帮助更多人。

- Jon

Answer 2

其中一种可能的解决方案是为顶点构建BSP树：http://en.wikipedia.org/wiki/Binary_space_partitioning

- maxim1000

Answer 3

如果二十面体有一个顶点在北极，另一个顶点在南极，那么就会有两组每组5个顶点，它们在赤道平行的平面上。通过一些几何计算，我发现这些平面位于N/S 57.3056°（小数，而非dd.mmss）。这将你的二十面体分成4个纬度区域：

• 任何在28.6528°北（南）以北（南）的地方都最接近更近极点的顶点；
• 任何在赤道和28.6528°北（南）之间的地方都更接近该区域内的5个顶点之一。

我像导航员一样处理这个问题，用度数表示弧长，并标注为北和南；如果您更喜欢数学约定，您可以很容易地将所有内容转换为您版本的球面坐标。

我猜想，虽然我还没有编写代码，但检查到5个顶点的距离并选择最近的顶点将比基于将球面表面划分为二十面体面的投影或将球面上的点投影回二十面体并在该坐标系中解决问题的更复杂的方法更快。

例如，您在更新1中提出的方法至少需要计算到6个顶点（第一个任意选择的顶点及其5个邻居）的距离。

如果您只想知道哪个顶点最近，那么无论您是在笛卡尔坐标系还是球面坐标系中计算距离都没有关系。然而，在笛卡尔坐标系中计算可以避免很多三角函数调用。

另一方面，如果您没有将正二十面体的顶点排列在球体的极点上，那么您应该这样做！

- High Performance Mark

---

我觉得我的问题可能没有表述清楚——正是将二十面体细分以逼近球体。一旦我对算法满意，我计划增加节点数目至60万以上，并将数量级的计算转移到GPU上。但是，我在极点处有顶点！ - Andy C

在这种情况下，看一看http://www.geog.ucsb.edu/~good/papers/162.pdf，并在谷歌上搜索类似的想法。 - High Performance Mark