给定一个二维平面，其中有 n 个点。我需要生成分割平面的直线方程，使得一侧有 n/2 个点，另一侧有 n/2 个点。
问问题
16247 次
10 回答
27
我假设这些点是不同的，否则甚至可能没有这样的线。
如果点是不同的，那么这样一条线总是存在的，并且可以使用确定性O(nlogn) 时间算法找到。
假设点是 P1，P2，...，P2n。假设它们并不都在同一条线上。如果它们是，那么我们可以很容易地形成分割线。
首先平移这些点，使所有坐标（x 和 y）都是正的。
现在假设我们神奇地在 y 轴上有一个点 Q，这样由这些点形成的线（即任何无限线 Pi-Pj）都不会通过 Q。
现在，由于 Q 不在点的凸包内，我们可以很容易地看到，我们可以通过穿过 Q 的旋转线对点进行排序。对于某个旋转角度，一半的点将位于一侧，另一半位于另一侧将位于这条旋转线的另一条线上，或者换句话说，如果我们考虑按 Pi-Q 线的斜率对点进行排序，我们可以选择第 (median)th 和 (median+1) 之间的斜率点。这种选择可以通过任何线性时间选择算法在 O(n) 时间内完成，而无需实际对点进行排序。
现在选择点Q。
假设 Q 是 (0,b)。
假设 Q 与 P1 (x1,y1) 和 P2 (x2,y2) 共线。
然后我们有
(y1-b)/x1 = (y2-b)/x2（注意我们平移了点，使得 xi > 0）。
求解 b 给出
b = (x1y2 - y1x2)/(x1-x2)
（注意，如果 x1 = x2，则 P1 和 P2 不能与 Y 轴上的一点共线）。
考虑|b|。
|b| = |x1y2 - y1x2| / |x1 -x2|
现在让 xmax 是最右边点的 x 坐标，ymax 是最顶部的坐标。
还让 D 是两点之间的最小非零 x 坐标差（这存在，因为并非所有 xi 都相同，因为并非所有点都是共线的）。
然后我们有 |b| <= xmax*ymax/D。
因此，选择我们的点 Q (0,b) 使得 |b| > b_0 = xmax*ymax/D
D 可以在 O(nlogn) 时间内找到。
b_0 的大小可能会变得非常大，我们可能不得不处理精度问题。
当然，更好的选择是随机选择 Q！在概率为 1 的情况下，您会找到所需的点，从而使预期的运行时间为 O(n)。
如果我们能找到一种在 O(n) 时间内选择 Q 的方法（通过找到其他标准），那么我们可以让这个算法在 O(n) 时间内运行。
于 2010-06-24T02:17:50.297 回答
12
在该平面上创建一条任意线。将每个点投影到该线上，也就是每个点，获取该线上最接近该点的点。
沿任一方向沿线排列这些点，并在该线上选择一个点，以使该线上任一方向上的点数相等。
得到垂直于通过该点的第一条线的线。这条线的两边将有一半的原始点。
执行此操作时需要避免某些情况。最重要的是，如果所有点本身都在一条线上，请不要选择穿过它的垂直线。事实上，选择那条线本身，这样您就不必担心投影点。就这背后的实际数学而言，矢量投影将非常有用。
于 2010-06-23T23:45:46.550 回答
5
这是对将点平面分成相等的两半的修改，它允许存在重叠点的情况（在这种情况下，它将说明答案是否存在）。
If number of points is odd, return "impossible".
Pick a random line (two random points)
Project all points onto this line (`O(N)` operation)
(i.e. we pretend this line is our new X'-axis, and write down the
X'-coordinate of each point)
Perform any median-finding algorithm on the X'-coordinates
(`O(N)` or faster-if-desired operation)
(returns 2 medians if no overlapping points)
Return the line perpendicular to original random line that splits the medians
In rare case of overlapping points, repeat a few times (it would take
a pathological case to prevent a solution from existing).
这O(N)与其他提出的解决方案不同。
假设存在解决方案，上述方法可能会终止，尽管我没有证据。
尝试上述算法几次，除非您检测到重叠点。如果您检测到大量重叠点，您可能会遇到困难，但是有一个非常低效的蛮力解决方案，涉及检查所有可能的角度：
For every "critical slope range", perform the above algorithm
by choosing a line with a slope within the range.
If all critical slope ranges fail, the solution is impossible.
临界角被定义为可能会改变结果的角度（想象先前答案的解决方案，旋转整个点集，直到一个或多个点与一个或多个其他点交换位置，越过分界线。有只有有限的很多，我认为它们受点数的限制，所以O(N^2)-O(N^2 log(N))如果你有重叠的点，你可能正在查看范围内的某些东西，这是一种蛮力方法。
于 2011-05-10T10:47:19.080 回答
1
我猜想一个好方法是对点进行排序/排序/排序（例如从左到右），然后选择一条穿过（或在）序列中的中间点[s]的线。
于 2010-06-23T23:40:42.210 回答
1
有明显的情况是无法解决的。例如，当你有三堆点时。位置 A 一个点，位置 B 两个点，位置 C 五个点。
如果您期望一些不错的分布，您可能会使用 tlayton 的算法获得良好的结果。要选择初始线倾斜，可以确定整个点集的范围，并选择最大对角线的角度。
于 2010-06-23T23:53:25.260 回答
1
中位数以类似于您尝试完成的方式平均划分一组数字，并且可以使用选择算法在 O(n) 时间内计算（Cormen 等人的文章更好，所以您可能想要而是看那里）。因此，找到您的 x 值 M x（或您的 y 值 M y如果您愿意）并设置 x = M x（或 y = M y），该线将轴向对齐并平均分割您的点。
如果您的问题的性质要求在线上不得超过一个点（如果您的集合中有奇数个点，则至少有一个点在线上）并且您发现这就是发生的事情（或者您只是想防止这种可能性），将所有点旋转某个随机角度 θ，并计算旋转点的中值。然后旋转通过 -θ 计算的中线，它将均匀地划分点。
随机选择 θ 以使问题再次出现的可能性非常小，点数有限，但如果确实如此，请使用不同的 θ 重试。
于 2010-06-24T02:18:44.073 回答
1
这是我解决这个问题的方法（假设 n 是偶数并且没有三个点是共线的）：
1) 选取 Y 值最小的点。我们称它为 P 点。
2) 以此点为新的原点，这样变换后其他所有点的Y值都为正。
3）每隔一个点（剩下n - 1个点），认为它在极坐标系下。每个其他点都可以用半径和角度表示。您可以忽略半径而只关注角度。
4）你怎么能找到一条平均分割点的线？求 (n - 1) 个角度的中位数。从点 P 到具有该中间角的点的线将均匀地分割这些点。
该算法的时间复杂度为 O(n)。
于 2013-08-03T13:27:17.583 回答
0
我不知道这有多大用我看到了类似的问题......
如果你已经有了方向向量（也就是你的飞机尺寸的系数）。
然后，您可以在该平面内找到两个点，只需使用中点公式，您就可以找到该平面的中点。
然后使用该平面的系数和中点，您可以使用平面的一般方程找到与两个点距离相等的平面。
然后，一条线将构成用另一个变量来表达一个变量，因此您会找到一条在两个平面之间距离相等的线。
有不同的方法可以做到这一点，例如使用距离平面的距离方程进行投影，但我相信这会使你的数学复杂化很多。
于 2010-06-24T00:08:29.610 回答
0
我从 Moron 和 andand 那里得到了这个想法，并继续形成一个确定性 O(n) 算法。
我还假设这些点是不同的并且 n 是偶数（认为可以更改算法，以便也支持在分界线上有一个点的不均匀 n）。
该算法试图用它们之间的垂直线来划分这些点。仅当中间的点具有相同的 x 值时，这才会失败。在这种情况下，算法确定有多少具有相同 x 值的点必须位于左侧和下部站点，并相应地旋转线。
我将尝试用一个例子来解释。假设我们在一个平面上有 16 个点。首先，我们需要得到具有第 8 个最大 x 值的点和具有第 9 个最大 x 值的点。正如另一个答案所指出的，使用选择算法，这在 O(n) 中是可能的。如果这些点的 x 值不同，我们就完成了。我们在这两点之间创建一条垂直线，并将两点分开。
现在有问题的是x值是否相等。所以我们有3组点。左侧（x < x a），中间（x = x a）和右侧（x > x a）。现在的想法是计算左侧的点，然后计算从中间到那里需要多少点，这样一半的点就在那一边。我们可以在这里忽略右侧，因为如果我们在左侧有一半的点，那么超过一半的点肯定在右侧。
所以让我们假设我们在左侧有 3 个点 (c=3)，在中间有 6 个，在右侧有 7 个（算法不知道中间或右侧的计数，因为它不知道需要它，但我们也可以在 O(n)) 中确定它。我们需要从中间得到 8-3=5 个点才能从左侧走。我们在第一步中已经得到的点现在已经没有用了，因为它们只由 x 值决定，可以是中间的任何点。
We want the 5 points from the middle with the lowest y-value on the left side and the point with the highest y-value on the right side. Again using the selection algorithm, we get the point with the 5th greatest y-value and the point with the 6th greatest y-value. Both points will have the x-value equal to xa, else we wouldn't get to this step, because there would be a vertical line.
现在我们可以在这两个点的中间创建点 Q。那是结果线的一点。需要另一个点，这样左侧或右侧的点就不会被分割。为了得到那个点，我们需要左侧的点，它在 x a处的垂直线与由该点和 Q 确定的线之间具有最小角度 (b h ) 。我们还需要右侧的那个点 (角度 a g )。新点 R 位于具有下角的点和垂直线上的一点之间（如果下角在左侧，则在 Q 上方的点，如果下角在右侧，则在 Q 下方的点）。
由 Q 和 R 确定的线将中间的点分开，使两边的点数为偶数。它不会划分左侧或右侧的任何点，因为如果这样，该点将具有较小的角度并且会被选择来计算 R。
从数学家的角度来看，应该在 O(n) 中运行良好。对于计算机程序，很容易找到精度成为问题的情况。一个有 4 个点的例子是 A(0, 100000000), B(0, 100000001), C(0, 0), D(0.0000001, 0)。在此示例中，Q 将是 (0, 100000000.5) 和 R (0.00000005, 0)。它在左侧给出 B 和 C，在右侧给出 A 和 D。但有可能因为舍入误差，A 和 B 都在分界线上。或者也许只有其中之一。因此，如果该算法符合要求，则属于输入值。
- 得到两个点 P a (x a , y a ) 和 P b (x b , y b )
，它们是基于 x 值的中位数> O(n) - 如果 x a != x b你可以停在这里，
因为这两个点之间的 y 轴平行线是结果> O(1) - 获取 x 值等于 x a 的所有点
> O(n) - 将 x 值小于 x a 的点计数为 c
> O(n) - 根据来自 3 的点的 y 值 获得最低点 Pc 。
> O(n) - 根据来自 3 的点的 y 值 获得最大点 Pd 。
> O(n) - 根据来自 3 的点的 y 值 获得第 (n/2-c) 个最大点 P e 。
> O(n) - 还可以根据来自 3 的点的 y 值 获得下一个最大点 P f 。
> O(n) - 在 P e和 P f之间创建一个新点 Q (x a , (y e +y f )/2)
> O(1) - 对于所有点 P i计算P c、 Q 和 P i
之间的 角度a i以及 P d、 Q 和 P i之间 的角度 b i
> O(n) - 获得具有最小角度 a g的点 P g ( g >0° 和g <180°)
> O(n) - 得到具有最小角度 b h的点 P h (b h >0° 和 b h <180°)
> O(n) - 如果没有任何 P g或 P h（所有点具有相同的 x 值） ，则在任何地方
创建一个新点 R (x a +1, 0)，但 x 值与 x a
不同， 否则如果 a g低于 b h在 P c和 P g
之间 创建一个新点 R ((x c +x g )/2, (y c +y g )/2) 否则 创建一个新点 R ((x d +x h )/2, (y d +y h )/2) 在 P d和 P h之间
> O(1) - 由 Q 和 R 确定的线划分点
> O(1)
于 2010-06-24T16:13:33.557 回答
0
添加到 M 的答案：一种在O(n log n).
首先，让 Q 是y 轴上的任意点，即。Q = (0,b)- 一些不错的选择可能是 (0,0) 或 (0, (y max -y min )/2)。
现在检查是否有两个点 (x 1 , y 1 ), (x 2 , y 2 ) 与 Q 共线。任何点和 Q 之间的线是y = mx + b; m由于 b 是常数，这意味着如果两个点的斜率相等，则它们与 Q 共线。因此，确定所有点的斜率 m i并检查是否有任何重复：（ 使用O(n)哈希表进行分析）
如果所有的 m 都是不同的，我们就完成了；我们找到了Q，上面M的算法O(n)逐步生成了这条线。
如果两个点与 Q 共线，我们将 Q 上移一点ε，Q new = (0, b + ε)，并证明 Q new不会与其他两个点共线。
下面推导出的 ε 标准是：
ε < m minΔ *x min
首先，我们的 m 看起来像这样：
m i = y i /x i - b/x i
让我们找到任何两个不同的m i之间的最小差异并将其称为 m minΔ （O(n log n) 例如，通过排序然后比较所有 i 的 m i和i+1之间的差异）
如果我们将 b 加 ε，则 m 的新方程变为：
m i,新= y i /x i - b/x i - ε/x i
= m i,旧- ε/x i
由于 ε > 0 且 x i > 0，所有 m 都减少了，并且都减少了 ε/x min的最大值。因此，如果
ε/x min < m minΔ，即 ε < m minΔ *x min
为真，那么之前不相等的两个 m i将保证保持不相等。
剩下的就是证明如果 m 1,old = m 2,old，则 m 1,new =/= m 2,new。由于两个 m i都减少了 ε/x i，这相当于显示 x 1 =/= x 2。如果它们相等，那么：
y 1 = m 1,旧x 1 + b = m 2,旧x 2 + b = y 2
与我们认为所有点都是不同的假设相矛盾。因此，m 1, new =/= m 2, new并且没有两个点与 Q 共线。
于 2010-06-24T21:12:53.790 回答