python - 在球形三角网格中查找包含点的三角形(Python，球坐标)

Question

主要问题

在 Python 中，我使用二十面体网格对(单位)球体的表面进行了三角剖分。我有一个 simplices 元组列表，其中包含每个三角形的三个顶点的索引，并且我有两个列表描述每个顶点的坐标(以弧度为单位):它的纬度和经度。

对于大约一百万个点，我想确定每个点在哪个三角形中。我正在寻找一种有效的算法来返回每个三角形的列表索引(索引对应于列表 simplices)。

我愿意牺牲内存而不是效率，所以我可以构造一棵树或使用一些查找方法。

注意事项

三角形的大小大致相等，但不完全相等，所以我怀疑简单的最近邻 KDTree 实现并不精确。

额外信息

已使用 stripy 包获得二十面体网格。它将二十面体的顶点投影到单位球体上，然后平分三角形，这样每条边都被分成两半，或者相反，每个三角形被分成四份。 stripy 有一个内置的方法来计算一个点所在的三角形，但是对于 6(即 6 个二等分)和大约一百万个点的网格细化，这需要几个小时。我怀疑这种方法没有使用树/查找方法，我希望有一种方法可以显着改进这一点。

Answer 1

1. 计算每个三角形的纬度/经度边界框。请记住，最大纬度可能位于边缘(通过考虑包括每条边缘在内的大圆的法线很容易找到)或(如果极点被封闭)在内部。
2. 将穿过周期性经度边界的所有三角形一分为二——或者，为了省事，只将它们的边界框一分为二。
3. 构建一个 extended-object k-d tree在三角形上(和上面的三角形部分)。这仍然仅使用纬度/经度值。
4. 运行明显的递归保守包含搜索以找到候选三角形。 (找到分割三角形中的哪一 block 并不重要。)
5. 仔细测试三角形包含:对于每个三角形边，判断哪个半球(由包含线段的大圆定义)包含查询点的方式(可能只是三维向量的叉积)不t 取决于顶点出现的顺序，永远不会在“分界线上”产生。然后保证每个点正好在一个三角形中。