一条直线最多能穿过多少个矩形？

Question

一条直线最多能穿过多少个矩形？

algorithmgeometrydynamic-programmingcomputational-geometry

33

我发现了这个挑战问题，其陈述如下：

假设在XY平面上有n个矩形。编写一个程序来计算可以用一条直线穿过的最大矩形数量。

see image for an example

我已经思考了相当长的时间，但是找不到任何解决方案。也许在某个阶段，我们使用动态规划步骤，但是无法确定如何开始。

- Tapan Vaishnav

从每个矩形的角落开始绘制到其他每个矩形的角落，然后选择最大值，这个怎么样？ - Andriy Berestovskyy

1

为了使动态规划相关，您需要以这样的方式构建问题，使其可以分解为重叠的子问题，并且这些子问题的最优解可用于生成整个问题的最优解。我不知道这是否满足该要求。 - avigil

1

@גלעדברקן 如果一条线段没有经过两个角落，我们总是可以稍微晃动它而不改变交点的数量。 - n. m.

@n.m. 很好的观点。 - גלעד ברקן

我会提出一些想法：1.通过盒子中心运行主成分分析是否足够好的近似？2.那么以线段中心和角度为表现型，最大交叉盒数为适应性规则的遗传算法是否可行（猜测从盒群集的中心开始旋转可能更快地收敛？）？ - George Profenza

显示剩余5条评论

6个回答

4

解决方案

在图中的所有线条中，那些穿过一个角落的线条恰好是交点数量即将减少的线条。换句话说，它们每个都形成了一个局部最大值。

对于每一条至少经过一个角的线，都存在一条关联线经过两个角，且具有相同数量的交点。

结论是，我们只需要检查由两个矩形角落组成的线条，因为它们组成了完全代表问题的局部最大值集合。从这些线条中选择具有最多交点的线条。

时间复杂度

此解决方案首先需要恢复所有经过两个角的线条。这样的线条数量为O(n^2)。

然后，我们需要计算给定线条与矩形之间的交点数。通过与每个矩形进行比较，这显然可以在O(n)中完成。

可能有更有效的方法来处理，但我们知道该算法最多为O(n^3)。

Python3 实现

以下是此算法的 Python 实现。我将其定位更多地向可读性而非效率，但它确切地执行了上述定义。

def get_best_line(rectangles):
    """
    Given a set of rectangles, return a line which intersects the most rectangles.
    """

    # Recover all corners from all rectangles
    corners = set()
    for rectangle in rectangles:
        corners |= set(rectangle.corners)

    corners = list(corners)

    # Recover all lines passing by two corners
    lines = get_all_lines(corners)

    # Return the one which has the highest number of intersections with rectangles
    return max(
        ((line, count_intersections(rectangles, line)) for line in lines),
        key=lambda x: x[1])

该实现使用以下辅助程序。

def get_all_lines(points):
    """
    Return a generator providing all lines generated
    by a combination of two points out of 'points'
    """
    for i in range(len(points)):
        for j in range(i, len(points)):
            yield Line(points[i], points[j])

def count_intersections(rectangles, line):
    """
    Return the number of intersections with rectangles
    """
    count = 0

    for rectangle in rectangles:
        if line in rectangle:
           count += 1

    return count

以下是用作矩形和直线数据结构的类定义。

import itertools
from decimal import Decimal

class Rectangle:
    def __init__(self, x_range, y_range):
        """
        a rectangle is defined as a range in x and a range in y.
        By example, the rectangle (0, 0), (0, 1), (1, 0), (1, 1) is given by
        Rectangle((0, 1), (0, 1))
        """
        self.x_range = sorted(x_range)
        self.y_range = sorted(y_range)

    def __contains__(self, line):
        """
        Return whether 'line' intersects the rectangle.
        To do so we check if the line intersects one of the diagonals of the rectangle
        """
        c1, c2, c3, c4 = self.corners

        x1 = line.intersect(Line(c1, c4))
        x2 = line.intersect(Line(c2, c3))

        if x1 is True or x2 is True \
                or x1 is not None and self.x_range[0] <= x1 <= self.x_range[1] \
                or x2 is not None and self.x_range[0] <= x2 <= self.x_range[1]:

            return True

        else:
            return False

    @property
    def corners(self):
        """Return the corners of the rectangle sorted in dictionary order"""
        return sorted(itertools.product(self.x_range, self.y_range))


class Line:
    def __init__(self, point1, point2):
        """A line is defined by two points in the graph"""
        x1, y1 = Decimal(point1[0]), Decimal(point1[1])
        x2, y2 = Decimal(point2[0]), Decimal(point2[1])
        self.point1 = (x1, y1)
        self.point2 = (x2, y2)

    def __str__(self):
        """Allows to print the equation of the line"""
        if self.slope == float('inf'):
            return "y = {}".format(self.point1[0])

        else:
            return "y = {} * x + {}".format(round(self.slope, 2), round(self.origin, 2))

    @property
    def slope(self):
        """Return the slope of the line, returning inf if it is a vertical line"""
        x1, y1, x2, y2 = *self.point1, *self.point2

        return (y2 - y1) / (x2 - x1) if x1 != x2 else float('inf')

    @property
    def origin(self):
        """Return the origin of the line, returning None if it is a vertical line"""
        x, y = self.point1

        return y - x * self.slope if self.slope != float('inf') else None

    def intersect(self, other):
        """
        Checks if two lines intersect.
        Case where they intersect: return the x coordinate of the intersection
        Case where they do not intersect: return None
        Case where they are superposed: return True
        """

        if self.slope == other.slope:

            if self.origin != other.origin:
                return None

            else:
                return True

        elif self.slope == float('inf'):
            return self.point1[0]

        elif other.slope == float('inf'):
            return other.point1[0]

        elif self.slope == 0:
            return other.slope * self.origin + other.origin

        elif other.slope == 0:
            return self.slope * other.origin + self.origin

        else:
            return (other.origin - self.origin) / (self.slope - other.slope)

例子

这是上述代码的一个可行示例。

rectangles = [
    Rectangle([0.5, 1], [0, 1]),
    Rectangle([0, 1], [1, 2]),
    Rectangle([0, 1], [2, 3]),
    Rectangle([2, 4], [2, 3]),
]

# Which represents the following rectangles (not quite to scale)
#
#  *
#  *   
#
# **     **
# **     **
#
# **
# **

我们可以清楚地看到，最佳解决方案应该找到一条穿过三个矩形的线，这确实是它的输出结果。

print('{} with {} intersections'.format(*get_best_line(rectangles)))
# prints: y = 0.50 * x + -5.00 with 3 intersections

- Olivier Melançon

1

这是一个直接的暴力解决方案。如果这是可以接受的，那么这个问题可能就不会被称为挑战了。 - n. m.

1

如果我找到更好的方法，我会改进它，只是目前还没有。有什么建议吗？另外，这并不是暴力枚举，因为它将问题真正降低到线性函数空间的子集。 - Olivier Melançon

我已经尝试过了。结果发现找到投影等同于以给定角度投影线上的每个点。然后你想要做的是找到关键角度并在那里计算投影，但实际上这些关键角度由角落之间的角度定义。因此，这个解决方案等效于我提供的解决方案，但我认为不够可读。此外，我不相信您可以在不重新计算邻近投影的情况下进行投影，因为投影不是单射的。在投影中丢失信息。 - Olivier Melançon

投影法可以通过将矩形折叠到形成给定角度下的“轮廓”的外角来受益。这形成了一个投影间隔，我们需要计算与其他矩形相交的次数。 - Reblochon Masque

1

@n.m. 和 Olivier，我添加了一个 O(n^2 (log n + m)) 的答案。你们觉得怎么样？ - גלעד ברקן

显示剩余2条评论

4

（对早期考虑旋转平面的答案进行编辑。）

这里是一个 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的下部边缘，并沿着边缘向上移动以在顶点(5/3，2/3)处分割x - 1的右半部分。每次插入都需要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)在经过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)

- גלעד ברקן

2

在我看来，这种方法并不能保证我们能找到所有的交点。我们可以尝试360个不同的角度，或者每隔1/10个角度尝试一次，或者每隔1/100个角度尝试一次等等。因此，该算法将给出一个预定义精度的结果，但答案永远不会是确切的最大值... - Andriy Berestovskyy

我认为需要检查投影方向与相邻点对之间连接线的角度，并旋转最小的角度。 - n. m.

@n.m. 你能解释一下吗？我不确定你所说的“投影方向”和“相邻的成对”是什么意思。也许你可以发表一个答案？ - גלעד ברקן

@AndriyBerestovskyy 我完全同意。 - גלעד ברקן

我还不完全相信这是完全正确的，但赏金即将到期，这看起来非常有希望在O(n^2)的时间复杂度内找到解决方案。我真的希望它能够奏效。但无论如何，这种使用双重空间的方法非常有趣。 - Olivier Melançon

显示剩余4条评论

3

以下算法怎么样：

RES = 0 // maximum number of intersections
CORNERS[] // all rectangles corners listed as (x, y) points

for A in CORNERS
    for B in CORNERS // optimization: starting from corner next to A
        RES = max(RES, CountIntersectionsWithLine(A.x, A.y, B.x, B.y))

return RES

换言之，从每个矩形角落开始画线，连接到其他矩形的角落，并找到最大交点数。正如@weston所建议的那样，我们可以通过从紧挨着A的角落开始内部循环来避免重复计算同一条线。

- Andriy Berestovskyy

1

你至少可以避免重复计算同一行。A-B B-A。你也可以通过在进行过程中仅保留最大值来避免内存复杂度。 - weston

2

@mnistic，您的示例仅在两个矩形的角之间绘制线条。答案中的建议是检查所有矩形角之间的线条。 - גלעד ברקן

所以，O(N^3) 复杂度？ - Shihab Shahriar Khan

2

如果你考虑一个角度为Θ的旋转线，并将所有矩形投影到该线上，则会得到N条线段。通过按横坐标递增的顺序排序端点并从左到右计算遇到的间隔数（记录端点是起点还是终点），可以轻松地获得垂直于该线的最大交叉矩形数。如图所示，用绿色表示。

现在，两个矩形被所有角度介于两个内切线之间的直线相交，因此要考虑的所有“事件”角度（即可以观察到计数变化的所有角度）是这些N(N-1)个角度。

然后，暴力解决方案是：

- 对于所有限制角度（有O(N²)个角度）， - 将矩形投影到旋转线上（需要O(N)次操作）， - 计算重叠并保留最大值（需要O(N Log N)进行排序，然后O(N)进行计数）。

总共需要O(N³Log N)次操作。

假设如果我们可以增量地进行排序，而不需要为每个角度重新完成排序，则我们可以希望将复杂度降低到O（N³）。这需要进行检查。

注意：

限制直线穿过一个矩形角落的解决方案是错误的。如果您从一个矩形的四个角落画出楔形图形，延伸到另一个矩形的整个范围，将会留下空白的空间，可以放置一个完整的矩形，而不会被触及，即使存在一条通过它们三个的线。

- user1196549

添加了一个 O(n^2 (log n + m)) 的答案。你觉得呢？ - גלעד ברקן

1

首先，（我们不考虑线条，而是考虑弧线和）任何一条解决方案的直线，只要它不经过任何一个角落，就可以稍微旋转一下以接触到一个角落。其次，复杂度也要考虑进去，在区间树中进行每次搜索和插入时，需要计算4个角落* n个矩形* 2 *（log n + m）。 - גלעד ברקן

1

你能想到一个解决方案线的例子，它不能旋转以触碰角落吗？这是没有意义的。如果一条线没有接触任何角落，请将其旋转直到第一个角落接触为止。根据定义，这样的移动将保持所有当前的交点。 - גלעד ברקן

如果你阅读过任何区间树查找复杂度的资料，你就会知道m代表什么。你的负评并不合理。 - גלעד ברקן

不确定区分在这里有何意义 :) 你是什么意思？ - גלעד ברקן

显示剩余4条评论

1

我们可以通过调整Andriy Berestovskyy的想法，稍微迭代角度以将当前角与所有其他矩形的关系插入到每个迭代周期的区间树中，从而使用O(n^2(log n + m))的动态规划方法。4n次迭代周期将创建一个新的角。对于每个矩形的四个角，我们将迭代每个其他矩形。我们要插入的是标记配对矩形最远角相对于当前固定角所创建的弧的角度。例如，在下面的示例中，对于固定下方矩形的角R，当插入中间矩形的记录时，我们将插入标记从p2到p1相对于R所创建的弧的角度（约为(37 deg, 58 deg)）。然后当我们检查相对于R的高矩形时，我们将插入标记从p4到p3相对于R所创建的弧的角度的区间（约为(50 deg, 62 deg)）。

当我们插入下一个弧记录时，我们将检查它与所有相交间隔的关系，并记录最多相交记录。

（请注意，由于任何在360度圆上的弧都有一个旋转了180度的对应物，因此我们可能需要进行任意截断（欢迎提供任何其他见解）。例如，这意味着从45度到315度的一段弧将分为两段：[0, 45]和[135, 180]。任何非分裂的弧只能与其中一个相交，但无论如何，我们都可能需要额外的哈希来确保不会重复计算矩形。）

- גלעד ברקן

你能提供伪代码吗？这个算法有一个我可以搜索的名称吗？ - Olivier Melançon

1

@OlivierMelançon 当然，我明天或周末会添加一些伪代码。我不知道它是否有可搜索的名称。 - גלעד ברקן

很高兴听到这个消息，我相信我已经了解你在做什么，但我想看到它的运行情况。谢谢！ - Olivier Melançon

@OlivierMelançon 我想我可能不会添加伪代码，因为Gassa提供了一个更优雅的解决方案，它有一些相似之处。 - גלעד ברקן

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Gassa · Accepted Answer

这是一个O(n^2 log n)解法的草图。

首先，跟其他答案一样，我们需要进行一些前置工作。当我们有一条直线穿过一些矩形时，我们可以将其平移至任何两侧，直到它穿过某个矩形的一个角落。然后，我们以该角落为旋转中心，旋转直线至任何一侧，直到它穿过另一个角落。在整个过程中，我们线与矩形边缘的所有交点都停留在这些边缘上，因此交点的数量和被线穿过的矩形数量保持不变。因此，我们只考虑穿过两个矩形角落的线，这个数量被限制在O(n^2)，相对于任意线的无限空间来说，这是一个很好的改进。

那么，我们如何高效地检查所有这些线呢？首先，让我们有一个外部循环，固定一个点A，然后考虑所有穿过A的线。A有O(n)种选择。

现在，我们固定了一个点A，想要考虑穿过所有其他角落B的所有线AB。为了做到这一点，首先将所有其他角落B按照AB的极角排序，换句话说，就是轴Ox和向量AB之间的夹角。角度从-PI到+PI或从0到2PI等等，所以我们可以任意切割圆来排序角度。排序时间复杂度是O(n log n)。

现在，我们有按极角围绕点A排序的点B1、B2、...、Bk（它们的数量k大约是4n-4，除了包含点A的一个矩形之外，所有矩形的所有角落）。首先，看一下线AB1，计算通过该线的矩形数量，时间复杂度为O(n)。然后，考虑将AB1旋转至AB2，然后再旋转至AB3，一直到ABk。旋转期间发生的事件如下：

当我们旋转到ABi，并且Bi是我们顺序中某个矩形的第一个角落时，一旦旋转线碰到Bi，穿过的矩形数量就会增加1。

当我们旋转到ABj，并且Bj是我们顺序中某个矩形的最后一个角落时，一旦旋转线超过Bj，穿过的矩形数量就会减少1。

哪些角落是第一个和最后一个，可以在排序之后，在考虑顺序事件之前进行一些O(n)预处理来确定。

简而言之，我们可以旋转到下一个这样的事件并以O(1)更新穿过的矩形数量。总共有k = O(n)个事件。剩下的事情就是在整个算法中跟踪该数量的全局最大值。答案就是这个最大值。

整个算法运行的时间复杂度为O(n * (n log n + n + n)), 这就是宣传的O(n^2 log n)。