geometry - 如何找到与 2D 视口相交的线段

Question

在无限的二维空间中，有一组线，每条线都有一个起点和终点，以及一个创建时间：Line(p0, p1, t).

我想找到应该在这个 2D 空间的自上而下视图中渲染的线条（更高的 t 值显示更接近视口，而不是它应该是相关的。）

直观的答案是“检查任一点是否在视口坐标内”，但是当这些点与视口区域覆盖的距离更远时，它就会下降。

我的另一个想法是使用类似geohash的东西，这会限制精度，即视口的最大缩放级别。这个想法是枚举相交的单元格的哈希值并存储它们。这种查询方式就是提出正确的问题。

有没有理想的解决方案？这个问题以前解决过吗？

Answer 1

我认为您需要检查两个条件：一个是视口矩形与带角的矩形重叠 (p0,p1)，第二个是视口矩形的某些角位于包含线段 (p0, p1)。

使用 R-tree ( http://en.wikipedia.org/wiki/R-tree )可以非常有效地解决大量矩形的查找矩形重叠的任务。

第二个任务可以简化为检查 (p1-p0) x (corner_coordinate-p0) 的叉积的符号（所有三个量都被视为第三个坐标等于 0 的 3-d 向量，结果将是沿垂线的向量方向）。应该有与此叉积相反符号的角。