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

问题描述

我试图找到一种算法来查找一组线的所有交点，并计算包含O（n log n）时间内所有交点的最小矩形。到目前为止，我猜它与双重性和凸包有关，但我有点卡在它将如何帮助我解决这个问题。

如果有人有一个想法，请让我知道。感谢：）

解决方案

我们从一个框B [0]开始，该框限定三角形中三个交点的最小边界。 >

如果找不到三角形，则可以分别处理以下特殊情况之一：

1. 所有线都是平行的。


2. 所有交叉点都沿着一条线。如果所有行都是平行的，则可能发生这种情况。


3. 所有行相交于一个点。
   

第一阶段 - 第二阶段 - 增加框以在每一行中包含一个交叉点：

1. 标记形成初始三角形的三条线。


2. 选择一个未标记的线，并找到带有标记的线的交点P.由于至少有三条不相互平行的标记行，所以始终可以这样做。


3. 增加包含P的框。


4. 重复2，直到所有行被标记为止，即它们在框中至少有一个交点。 调用结果框B [0 ]。
   
   

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

   以下是关键观察：对于在盒子内部相交的两条线A和B，在顺时针方向绕着盒子行走，我们交替地看到这些线：例如A B A B.对于与盒子外部相交的两条线，顺时针走线不交替：例如， ABB A.当然，这些线条有可能与盒子边界相交，也可能是并发的，但在描述主算法之后将被视为细节。
   
   

   
   
   1. 选择线的方向：如果线不是水平线，则让线指向+ y方向，并让水平线以​​+ x直线定向。这些线条中的一个是箭头，然后箭头都选择为尽可能多地指向，或者如果它们是水平的，则向右。通过这种定位，每条线都有一个入口点（方向线指向方框和出口点），这些点可能是相同点。 创建一个通过沿EXRING交叉点顺时针方向绕着边界行走，例如从右上角开始，线条的退出顺序。
   
   
   2. 通过步行来创建线条的输入顺序
      
   3. 如果所有交点都位于方框的内部，则输入和退出序列将相互循环，B [ i]是交叉点的最小边界框。
   
   
   4. 否则，将两个序列对齐到任意元素（通过循环旋转）。这两行在框外必须有一个交点P，所以通过增长B [i]来包含P来形成B [i + 1]。
      
   5. 从2开始重复。
   
   

   这是不完整的，因为如果一组线在边界上具有共同的进入点或退出点，则进入和退出序列没有被很好地定义。对于每组具有共同进入点或退出点的线L，使用一个稍大的方框来排序L.注意，该算法不会发射所有的交点，但它确实保证（我希望）这个盒子包含了所有这些。

   
   

   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 :)

   解决方案

   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. All lines are parallel.
   2. All intersections are along one line. This could happen if all lines but one are parallel.
   3. All lines intersect at a single point.

   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.

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

   1. Tag the three lines forming the initial triangle.
   2. Choose one untagged line, and find an intersection P with a tagged line. This is always possible since there are at least three tagged lines that aren't mutually parallel.
   3. Grow the box to include P.
   4. Repeat from 2 until all the lines are tagged, i.e. they all have at least one intersection in the box.

   Call the resulting box B[0].

   Phase 2 - Detect if lines have an intersection outside of the 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. Choose an orientation of the lines: Let the lines be directed toward the +y direction if the lines aren't horizontal, and let horizontal lines be oriented in the +x direct. One things of the lines as arrows, then the arrows are all chosen to point up as much as they can, or to the right if they're horizontal. With this orientation, each line has a point of entry into the box (where the oriented line points into the box, and a point of exit. These may be the same point.
   2. Create an "exit sequence" of the lines by walking the EXITING intersections clockwise around the boundary, starting at, say, the upper right corner.
   3. Create an "enter sequence" of the lines by walking the ENTERING intersections clockwise starting at the upper right corner of the box as well.
   4. If all intersections are interior to the box, the enter and exit sequences will be cyclic with each other, and B[i] is the minimum bounding box of the intersections.
   5. Otherwise, align the two sequences to an arbitrary element (by cyclic rotation).
   6. Find the elements in the sequences where they first differ. Those two lines must have an intersection P outside of the box, so form B[i+1] by growing B[i] to include P.
   7. Repeat from 2.

   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屋！