在球面三角形网格中查找包含点的三角形（Python，球坐标）

Question

主要问题

在Python中，我使用二十面体网格对（单位）球体的曲面进行了三角剖分。我有一个元组列表simplices，包含每个三角形的三个顶点的索引，还有两个描述每个顶点坐标（弧度）的列表：纬度和经度。你知道吗

对于大约一百万个点，我想确定每个点所在的三角形。我正在寻找一种高效的算法，返回每个三角形的列表索引（对应于listsimplices的索引）。你知道吗

我愿意牺牲内存来提高效率，所以我可以构建一棵树或者使用一些查找方法。你知道吗

注意事项

三角形的大小大致相等，但并不完全相同，因此我怀疑简单的最近邻KDTree实现是不精确的。你知道吗

额外信息

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

Answer 1

1. 计算每个三角形的纬度/经度边界框。请记住，最大震级纬度可能位于边缘（通过考虑包括每个边缘在内的大圆的法线很容易找到）或（如果极点是封闭的）内部。你知道吗
2. 将所有穿过周期性经度边界的三角形分成两部分，或者，便宜一点，仅仅是它们的边界框。你知道吗
3. 在三角形上建立一个extended-object k-d tree（以及上面的三角形片段）。这仍然只使用纬度/经度值。你知道吗
4. 运行明显的递归、保守的包含搜索来找到候选三角形。（不管你找到哪一块分割的三角形。）
5. 仔细测试三角形夹杂：对于每个三角形边，判断哪个半球（由包含线段的大圆定义）包含查询点的方式（可能只是三维向量上的叉积）不取决于顶点的呈现顺序，并且永远不会产生“在分界线上”。然后保证每个点正好在一个三角形中。你知道吗