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

Question

主要问题

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

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

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

注意事项

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

额外的信息

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

标签： pythonmeshnearest-neighbor

Answer 1

1. 计算每个三角形的纬度/经度边界框。请记住，最大纬度可能位于边缘（通过考虑包括每个边缘的大圆的法线很容易找到）或（如果极点被封闭）在内部。
2. 将所有穿过周期性经度边界的三角形一分为二——或者，为了便宜，只是它们的边界框。
3. 在三角形（以及上面的三角形块）上构建一个扩展对象k - d树。这仍然只使用纬度/经度值。
4. 运行明显的递归、保守的包含搜索来找到候选三角形。（找到分割三角形的哪一块并不重要。）
5. 仔细测试三角形包含：对于每个三角形边，判断哪个半球（由包含该段的大圆定义）以不依赖于的方式（可能只是三维向量上的叉积）包含查询点顶点呈现的顺序，从不产生“在分界线上”。然后保证每个点都在一个三角形中。