可以与单条直线交叉的最大可能矩形数

Question

我发现这个挑战问题说明如下:

假设XY平面上有n个矩形.编写一个程序来计算可以与在该平面上绘制的单条直线交叉的最大可能矩形数.

我一直在集思广益,但找不到任何解决方案.也许在某个阶段,我们使用动态编程步骤,但无法弄清楚如何开始.

Answer 1

这是O(n ^ 2 log n)解的草图.

首先,预赛与其他答案共享.当我们有一条线穿过某些矩形时,我们可以将它转换为两边中的任何一条,直到它穿过某个矩形的一角.之后,我们将该角固定为旋转中心,并将线旋转到两侧中的任何一侧,直到它穿过另一个角.在整个过程中,我们的线和矩形边之间的所有交点都停留在这些边上,因此交叉点的数量保持不变,线的交叉数量也是如此.因此,我们只能考虑通过两个矩形角的线,它们被O(n ^ 2)限制,与任意线的无限空间相比是一个值得欢迎的改进.

那么,我们如何有效地检查所有这些线？首先,让我们有一个外环,它固定一个点A,然后考虑所有通过A的线.有O(n)选择A.

现在,我们有一个点A固定,并且想要考虑通过所有其他角B的所有线AB.为了做到这一点,首先根据AB的极角对所有其他角B进行排序,或者换句话说,角度在轴Ox和矢量AB之间.角度是从-PI到+ PI或从0到2 PI测量的,否则,我们将圆切割成分类角度的点可以是任意的.排序在O(n log n)中完成.

现在,我们有点B ₁,B ₂,...,B _k按照A点周围的极角排序(它们的数字k类似于4n-4,所有矩形的所有角都除了A点是角的那个角).首先,查看AB ₁行,并计算O(n)中该行越过的矩形数.在此之后,考虑旋转AB ₁至AB ₂,AB然后₂至AB ₃,一路AB _ķ.轮换期间发生的事件如下:

• 当我们旋转到AB _i,并且B _i是我们顺序中某个矩形的第一个角时,一旦旋转线撞击B _i,交叉的矩形数量就会增加1 .

• 当我们旋转到AB _j时,B _j是我们顺序中某个矩形的最后一个角,一旦线旋转经过B _j,交叉的矩形数减少1 .

在排序之后但在考虑有序事件之前,可以使用一些O(n)预处理来建立第一个和最后一个角.

简而言之,我们可以旋转到下一个这样的事件并更新O(1)中交叉的矩形数.并且总共有k = O(n)个事件.剩下要做的是在整个算法中跟踪此数量的全局最大值.答案就是这个最大值.

整个算法运行在O(n*(n log n + n + n)),即O(n ^ 2 log n),正如所宣传的那样.

Answer 2

（编辑我之前考虑旋转飞机的答案。）

下面是算法的草图O(n^2)，它将 Gassa 的想法与 Evgeny Kluev 的双线排列参考作为排序的角序列相结合。

我们从双重连接的边列表或类似的结构开始，允许我们及时分割边O(1)，以及一种遍历我们在填充二维平面时创建的面的方法。为了简单起见，我们只使用下面矩形的十二个角中的三个：

9|     (5,9)___(7,9)
8|         |   |
7|    (4,6)|   |
6|    ___C |   |
5|   |   | |   |
4|   |___| |   |
3|  ___    |___|(7,3)
2| |   |  B (5,3)
1|A|___|(1,1)
 |_ _ _ _ _ _ _ _
   1 2 3 4 5 6 7

我们根据以下变换在对偶平面中插入三个点（角点）：

point p => line p* as a*p_x - p_y
line l as ax + b => point l* as (a, -b)

让我们按顺序输入点A, B, C。我们首先进入A => y = x - 1。由于到目前为止只有一条边，因此我们插入B => y = 5x - 3，这将创建顶点(1/2, -1/2)并分割我们的边。（这个解决方案的一个优雅的方面是，对偶平面中的每个顶点（点）实际上是穿过矩形角的线的对偶点。观察1 = 1/2*1 + 1/2和3 = 1/2*5 + 1/2，点(1,1)和(5,3)。）

输入最后一点 ，C => y = 4x - 6我们现在寻找将相交的最左边的面（可能是不完整的面）。这个搜索是O(n)时候了，因为我们必须尝试每张脸。我们找到并创建顶点(-3, -18)，分割 的下边缘5x - 3并向上遍历边缘以分割x - 1顶点的右半部分(5/3, 2/3)。每次插入都有O(n)时间，因为我们必须首先找到最左边的面，然后遍历每个面以分割边并标记顶点（线的交点）。

在双平面中我们现在有：

构建线排列后，我们开始对三个示例点（矩形角）进行迭代。重建与一个点相关的排序角度序列的部分神奇之处在于将角度（每个角度对应于对偶平面中的有序线交点）划分为与右侧点（具有更大的 x 坐标）对应的角度，并且左侧的序列并将两个序列连接起来以获得从 -90 度到 -270 度的有序序列。（右侧的点转换为相对于固定点具有正斜率的线；左侧的点具有负斜率。顺时针旋转您的服务/屏幕，直到线变为(C*) 4x - 6水平，您会看到B*现在具有正斜率斜率和A*负值。）

为什么它有效？如果将原始平面中的点p变换为对p*偶平面中的一条线，则从左到右穿过该双线相当于p在原始平面中旋转一条也穿过 的线p。双线通过 x 坐标标记该旋转线的所有斜率，从负无穷大（垂直）到零（水平）到无穷大（再次垂直）。

（让我们总结一下矩形计数逻辑，在迭代角度序列时更新当前矩形的 count_array：如果它是 1，则增加当前交叉点计数；如果它是 4 并且该线不直接位于角上，请将其设置为0 并减少当前交叉点计数。）

Pick A, lookup A*
=> x - 1.

Obtain the concatenated sequence by traversing the edges in O(n)
=> [(B*) 5x - 3, (C*) 4x - 6] ++ [No points left of A]

Initialise an empty counter array, count_array of length n-1

Initialise a pointer, ptr, to track rectangle corners passed in
the opposite direction of the current vector.

Iterate:
  vertex (1/2, -1/2)
  => line y = 1/2x + 1/2 (AB)

  perform rectangle-count-logic

  if the slope is positive (1/2 is positive):
    while the point at ptr is higher than the line:
      perform rectangle-count-logic

  else if the slope is negative:
    while the point at ptr is lower than the line:
      perform rectangle-count-logic

  => ptr passes through the rest of the points up to the corner
     across from C, so intersection count is unchanged

  vertex (5/3, 2/3)
  => line y = 5/3x - 2/3 (AC)

我们可以看到(5,9)位于 through 线上方AC (y = 5/3x - 2/3)，这意味着此时我们已经计算了与最右边矩形的交点，但尚未重置其计数，该线总共有 3 个矩形。

我们还可以在对偶平面的图中看到其他角序列：

for point B => B* => 5x - 3: [No points right of B] ++ [(C*) 4x - 6, (A*) x - 1]

for point C => C* => 4x - 6: [(B*) 5x - 3] ++ [(A*) x - 1]
(note that we start at -90 deg up to -270 deg)