可以用一条直线交叉的最大可能数量的矩形 [英] Maximum possible number of rectangles that can be crossed with a single straight line

问题描述

我发现这个挑战问题说明了以下几点：

假设在XY平面上有n个矩形。编写一个程序来计算可以在这架飞机上绘制的单个直线上可以穿过的最大可能数量的矩形。

我一直在集思广益一时间却找不到任何解决办法。
也许在某个阶段，我们使用动态编程步骤，但不知道如何开始。

是一个O（n ^ 2 log n）解决方案的草图。

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

那么，我们如何高效地检查所有这些行？
首先，让我们有一个外部循环，修正一个点A，然后考虑所有通过A的线。
有O（n）个A选项。

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

现在，我们有B _{1 ，B 2，...，B 按照围绕点A的极角排序（它们的数量k类似于4n-4，所有矩形除了点A是一个角落）。
首先，查看AB 1 行并计算O（n）中该行所穿过的矩形的数量。
之后，考虑将AB 1 旋转到AB 2 ，然后将AB 2 旋转到AB 3 一直到AB k 。
旋转过程中发生的事件如下：}

• 当我们旋转到AB _i ，并且B _i 是我们的顺序中某个矩形的第一个角点，一旦旋转线点击B _i ，交叉的矩形数就会增加1。当我们旋转到AB _j ，并且B _j 是某个矩形的最后一个角时，

我们的订单，一旦线经过B _j ，交叉的矩形的数量就减少1。 $ b

在排序之后，但在考虑有序事件之前，可以使用一些O（n）预处理来建立哪些角落首先和最后。



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



整个算法运行在O（n *（n log n + n + n））中，它是O（ n ^ 2 log n），就像广告一样。


I found this challenge problem which states the following :

Suppose that there are n rectangles on the XY plane. Write a program to calculate the maximum possible number of rectangles that can be crossed with a single straight line drawn on this plane.

I have been brainstorming for quite a time but couldn't find any solution. Maybe at some stage, we use dynamic programming steps but couldn't figure out how to start.

解决方案

Here is a sketch of an O(n^2 log n) solution.

First, the preliminaries shared with other answers. When we have a line passing through some rectangles, we can translate it to any of the two sides until it passes through a corner of some rectangle. After that, we fix that corner as the center of rotation and rotate the line to any of the two sides until it passes through another corner. During the whole process, all points of intersection between our line and rectangle sides stayed on these sides, so the number of intersections stayed the same, as did the number of rectangles crossed by the line. As a result, we can consider only lines which pass through two rectangle corners, which is capped by O(n^2), and is a welcome improvement compared to the infinite space of arbitrary lines.

So, how do we efficiently check all these lines? First, let us have an outer loop which fixes one point A and then considers all lines passing through A. There are O(n) choices of A.

Now, we have one point A fixed, and want to consider all lines AB passing through all other corners B. In order to do that, first sort all other corners B according to the polar angle of AB, or, in other words, angle between axis Ox and vector AB. Angles are measured from -PI to +PI or from 0 to 2 PI or otherwise, the point in which we cut the circle to sort angles can be arbitrary. The sorting is done in O(n log n).

Now, we have points B₁, B₂, ..., B_k sorted by the polar angle around point A (their number k is something like 4n-4, all corners of all rectangles except the one where point A is a corner). First, look at the line AB₁ and count the number of rectangles crossed by that line in O(n). After that, consider rotating AB₁ to AB₂, then AB₂ to AB₃, all the way to AB_k. The events which happen during the rotation are as follows:

• When we rotate to AB_i, and B_i is the first corner of some rectangle in our order, the number of rectangles crossed increases by 1 as soon as the rotating line hits B_i.

• When we rotate to AB_j, and B_j is the last corner of some rectangle in our order, the number of rectangles crossed decreases by 1 as soon as the line rotates past B_j.

Which corners are first and last can be established with some O(n) preprocessing, after the sort, but before considering the ordered events.

In short, we can rotate to the next such event and update the number of rectangles crossed in O(1). And there are k = O(n) events in total. What's left to do is to track the global maximum of this quantity throughout the whole algorithm. The answer is just this maximum.

The whole algorithm runs in O(n * (n log n + n + n)), which is O(n^2 log n), just as advertised.

这篇关于可以用一条直线交叉的最大可能数量的矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！