computational-geometry - 查找区域内的格点数

Question

给定二维平面中的一组点，如何找到位于任意三角形上或内部的点数。
一种方法是检查所有点是否位于给定三角形内。
但我读到 Kd-tree 可用于在 O(log n) 时间内找到位于区域内的点数，其中“n”是点数。但我不明白如何实现。
有没有其他更简单的方法可以做到这一点？
或者 kd-tree 会起作用吗？如果是这样，有人可以解释一下吗？

Answer 1

可以通过递归检查三角形的子分区位置来完成。要查看树节点的哪些点在三角形中，请检查每个节点分区（kd 树中有 2 个）是否完整在三角形中，是否在三角形之外或是否与三角形相交。如果分区在三角形中，则将该分区中的点数添加到结果中，如果分区不在三角形中，则对该分区不执行任何操作，如果分区与三角形相交，则对该分区的子分区进行相同的检查。

为此，每个树节点都必须在其子树中存储点数，这在树的创建中很容易做到。

运行时间取决于三角形边与分区边界相交的数量。我不确定是不是O(log n)最坏的情况。