包含所有线交点的最小矩形 [英] Minimal rectangle containing all intersections of lines

问题描述

我正在尝试找到一种算法，该算法将找到一组线的所有交点，并在 O(n log n) 时间内计算包含所有交点的最小矩形.到目前为止，我猜测它与对偶性和凸包有关，但我有点坚持它实际上如何帮助我解决这个问题.

I'm trying to find an algorithm that will find all the intersections of a set of lines and compute the minimal rectangle that contains all the intersections in O(n log n) time. So far I'm guessing it has to do with duality and convex hulls, but I'm kinda stuck on how it would actually help me solve this problem.

如果有人对此有任何想法，请告诉我.谢谢:)

If anyone has an idea on this, please let me know. Thanks :)

推荐答案

让我们从一个最小限制三角形中三个交点的框 B[0] 开始.

Let's start from a box B[0] that minimally bounds three intersection points in a triangle.

如果找不到三角形，那么我们有以下特殊情况之一，可以单独处理:

If no triangle can be found, then we have a one of the following special cases which can be handled separately:

1. 所有线都是平行的.
2. 所有交叉点都在一条线上.如果除一条之外的所有线都是平行的，则可能会发生这种情况.
3. 所有线相交于一个点.

所以让我们忽略这些细节，假设可以找到一个三角形并且找到它不会给算法增加太多时间.

So let's ignore these cases as details and assume a triangle can be found and that finding it doesn't add too much time to the algorithm.

第 1 阶段 - 扩大框以包含每条线的一个交点:

Phase 1 - Grow the box to include one intersection from each line:

1. 标记构成初始三角形的三条线.
2. 选择一条未标记的线，并找到与标记线的交点 P.这始终是可能的，因为至少有 3 条标记线不相互平行.
3. 扩大框以包含 P.
4. 从 2 开始重复，直到所有行都被标记，即它们在框中都至少有一个交点.

调用结果框 B[0].

Call the resulting box B[0].

第 2 阶段 - 检测线是否在框外有交叉点:

Phase 2 - Detect if lines have an intersection outside of the box:

这是关键观察:对于在盒子内相交的两条线 A 和 B，顺时针绕盒子走，我们会遇到交替的线:例如A B A B. 对于在框外相交的两条线，顺时针行走不会交替:例如A B B A. 当然也有可能是线在box边界上相交，或者是并发的，但在描述主要算法后，将作为细节处理.

Here's the key observation: for two lines A and B that intersect WITHIN the box, walking around the box clockwise we encounter the lines alternating: e.g. A B A B. For two lines that intersect OUTSIDE the box, a clockwise walk does NOT alternate: e.g. A B B A. Of course there is the possibility that the lines intersect on the box boundary, or are concurrent, but that will be treated as a detail after describing the main algorithm.

1. 选择线条的方向:如果线条不水平，则将线条指向 +y 方向，并让水平线条指向 +x 方向.线作为箭头的一件事，然后箭头都被选择为尽可能多地指向，或者如果它们是水平的，则指向右侧.在这种方向下，每条线都有一个进入盒子的点(定向线指向盒子的地方，还有一个出口点.它们可能是同一个点.
2. 围绕边界顺时针穿过 EXITING 交叉点，从右上角开始，创建线路的退出序列".
3. 从框的右上角开始顺时针穿过 ENTERING 交叉点，创建线条的输入序列".
4. 如果所有的交点都在盒子的内部，则进入和出口的序列将相互循环，B[i] 是交点的最小边界框.
5. 否则，将两个序列对齐到任意元素(通过循环旋转).
6. 在序列中找到它们首先不同的元素.这两条线必须在框外有一个交点 P，因此通过增加 B[i] 以包含 P 来形成 B[i+1].
7. 从 2 开始重复.

这并不完整，因为如果组线在边界上有一个共同的进入点或退出点，则进入和退出序列没有明确定义.对于具有共同进入或退出点的每组线 L，请使用稍大的框对 L 进行排序.

This isn't complete because the entering and exiting sequences aren't well defined if a group lines have a common entering or exiting point on the boundary. For each group of lines L with a common entering or exiting point, use a slightly larger box for ordering L.

请注意，此算法不会发出所有的交叉点，但它确实保证(我希望)盒子包含所有交叉点.

Note that this algorithm doesn't emit all the intersections, but it does guarantee (I hope) that the box contains them all.

这篇关于包含所有线交点的最小矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！