主要问题
在python中，我使用二十面体网格对（单位）球体的曲面进行了三角剖分。我有一个包含每个三角形三个顶点索引的元组列表simplices，还有两个描述每个顶点坐标（弧度）的列表：纬度和经度。
对于大约一百万个点，我想确定每个点在哪个三角形中。我正在寻找一个有效的算法，返回每个三角形的列表索引（对应于listsimplices的索引）。
我愿意牺牲内存而不是效率，所以我可以构建一个树或使用一些查找方法。
注意事项
三角形的大小大致相等，但并不完全相同，因此我怀疑一个简单的最近邻KDTree实现并不精确。
额外信息
使用stripy包获得了二十面体网格。它将二十面体的顶点投影到单位球体上，然后将三角形平分，这样每条边都被分成两半，或者相反，每条三角形被分成四个stripy有一个内置的方法来计算包含一个点的三角形，但是对于6个（即6个平分）和大约一百万个点的网格细化，这需要几个小时我怀疑这个方法没有使用树/查找方法，我希望有一个方法在这个基础上有显著的改进。
最佳答案
计算每个三角形的纬度/经度边界框。记住，最大的震级纬度可能在一个边缘（考虑到包括每个边缘在内的大圆的法向很容易找到），或者（如果极点是封闭的）在内部。
将所有穿过周期性经度边界的三角形分成两个，或者，更便宜的是，只划分它们的边界框。
在三角形（和上面的三角形部分）上建立一个extended-object k-d tree这仍然只使用纬度/经度值。
运行明显的递归、保守的包含搜索以查找候选三角形（不管你找到的是哪个分割的三角形。）
仔细测试三角形是否包含：对于每个三角形边，判断哪个半球（由包含段的大圆定义）以某种方式（可能只是三维向量上的叉积）包含查询点，这种方式不取决于顶点的显示顺序，并且永远不会产生“在分界线上”。然后保证每个点都在一个三角形中。
关于python - 在球形三角形网格中查找包含点的三角形(Python，球形坐标)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58526585/