我有一个应用程序，它通过细分二十面体来创建球体的近似值。笛卡尔顶点坐标转换为球坐标，因此所有顶点都位于单位球体的表面上。
接下来我需要做的是找到离球体表面任意点最近的顶点。我想出了两个简单的算法......
蛮力搜索 - 对于少数顶点来说可以，但对于更精细的细分来说会过度。
排序/索引搜索 - 通过方位角和倾角将顶点排序为某种形式的顺序，然后创建一个粗略的索引以通过限制其范围来加速蛮力搜索。
我想知道是否有一种更微妙、希望性能更高的算法可以用来代替上述两种算法中的一种。
更新 1：我刚刚回忆起，对于应用程序的另一部分，顶点存储有关其邻居的信息。我的新算法是
浏览回复，我想我可能不正确，但你所追求的很简单。我认为。
由于您只处理球体上的点，因此您可以从顶点到球体中心放下一条线，从任意点到中心放下另一条线并求解它们之间创建的角度。越小越好。我认为最简单和最便宜的方法是点积。角度基本上掉出来了。这是一个关于它的链接：http ://www.kynd.info/library/mathandphysics/dotProduct_01/ 为了测试它们，我建议选择一个顶点，测试它，然后测试它的邻居。它应该总是在最小邻居的方向上（随着你接近你所追求的顶点，角度应该总是减小）
无论如何，我希望这就是你所追求的。哦，我在寻找你的细分算法时遇到了这个页面。很难找到; 如果您可以发布指向它的链接，我认为这将比我自己提供更多帮助。
一种可能的解决方案是为顶点构建 BSP 树：http ://en.wikipedia.org/wiki/Binary_space_partitioning
如果二十面体在北极有一个顶点，在南极有一个顶点，则在平行于赤道的平面上，每组 5 个顶点有 2 组。通过一点几何，我认为这些平面位于 N/S 57.3056°（小数，而不是 dd.mmss）。这将您的二十面体分为 4 个纬度区域；
我正在像导航员一样工作，弧线以度数测量并表示南北；如果您更喜欢数学惯例，您可以很容易地将这一切转换为您的球坐标版本。
我怀疑，虽然我没有编码，但检查到 5 个顶点的距离并选择最近的将比基于将球体表面划分为二十面体面的投影或投影的更复杂的方法更快球体上的点回到二十面体并在该坐标系中解决问题。
例如，您在更新 1 中建议的方法将需要至少计算到 6 个顶点（第一个，任意选择的一个及其 5 个邻居）的距离。
用笛卡尔坐标还是球坐标计算距离都没有关系（如果您只想知道哪个顶点最近）。但是，笛卡尔坐标中的计算避免了对三角函数的大量调用。
另一方面，如果你没有在你的球体的两极安排你的二十面体，那么，你应该有！