有效地检查点是否在2D中的大量三角形内

Question

我已经实现了一个算法,通过在这个问题中调用第一个算法来检查点是否在2D中的三角形内:如何确定一个点是否在二维三角形内.

这个算法有效,但我认为如果我预处理三角形并使用智能数据结构,我可以使这个效率更高.我使用了大约1000万个三角形.我认为实现这一目标的一种方法是计算三角形的边界矩形并在矩形检查中做一个点,但我觉得通过利用一些数据结构来检查近似的矩形,这种情况可以更快.

这样的数据结构和算法是否存在？

Answer 1

计算几何的经典方法是三角测量然后进行点位置,但是使用kd树要容易得多,将三角形与内部树节点的分区线相交,使得它们可以在一直到树叶.

构造kd树是一个递归过程.给定一个三角形列表和一个要聚焦的坐标(x或y,与每一层交替),找到一个模糊的中间分离线,通过随机抽样,采用中位数,或通过某种组合或采样和采取中位数.收集其点均严格小于分离坐标的三角形,并使用它们构造左子树.收集其点都严格大于分离坐标的三角形,并使用它们构造正确的子树.将剩余的三角形(与坐标线相交的三角形)存储在根中.

要查询,请测试该点是否属于根中的任何三角形.然后,如果该点小于分离坐标,请检查左子树.如果该点更大,请检查右侧.