我正在尝试以一种在以下情况下有效的方式编写光线转换算法 ( http://en.wikipedia.org/wiki/Point_in_polygon):
- 该算法将使用相同的多边形多次调用，但 不同点
- 多边形有很多顶点
多边形很简单但不一定是凸的。
我将使用从点 (xp,yp) 向右移动的水平射线:xr = xp + a, a>=0, yr = yp。
我不想遍历多边形的所有边并检查点是否在边的 y 范围内，而是想使用一些二进制空间分区树技术(http://en.wikipedia.org/wiki/Binary_space_partitioning)来快速找到这样的边。
我想象一个盒子的二叉树:
struct Box {
float min, max;
Box *leftChild; // [min,mid]
Box *rightChild; // [mid,max]
std::vector<int> edgeIndices; // edges that are completely within the box
};
- 所有的边都被放置在具有 min = min y(polygon) 和 max = max y(polygon) 的根框中。这成为当前框。
- 当前框 (min,max) 被拆分为:左:(min,mid) 和右:(mid,max)。完全位于左侧或右侧的边缘将移入该子框。
对左右子节点重复第 2 步，直到每个框包含的边数少于预定义数量或该子节点的深度超过预定义的最大深度。
现在为了找到哪些边与值 yp 相交:从根框开始向下遍历，将路径上的所有边加在一起。
如何找到最佳中间值？我希望树尽可能平坦和平衡。即左右 child 的边数应该大致相同。
我可以，例如对最小 y 或最大 y 上的边进行排序，并使用中间边的平均 y 作为分割点 (mid)。
最佳答案
如果你有一个非凸多边形，其中大多数边都穿过某个 y 值，那么当你查询一个具有该 y 值的点时，你将在边数上得到基本上线性的时间来解决你在多边形查询中的点.如果你有很多预处理时间和预处理空间，那么你可以根据 y 坐标对顶点进行排序，并在每对相邻的 y 坐标顶点之间定义一条水平切割线，并根据它们所在的 x 值对边进行排序穿过水平切割线。这将给出最坏情况下大小为 O(n^2) 但可能更小的数据结构。然后，给定一个查询点，可以通过二分查找找到y坐标在查询点y坐标上下最近的两个顶点，然后在这些边上进行二分查找找到查询点的x-坐标位于边列表中，然后根据点的x位置是偶数还是奇数报告内部或外部。在排序的边列表中。查询时间为 O(log n)
关于c++ - 使用二进制空间划分树的多边形测试中的快速点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25313878/