将一个点平面分成两个相等的部分

Question

将一个点平面分成两个相等的部分

algorithmmathgeometrycomputational-geometry

35

给定一个二维平面，其中有n个点。我需要生成一条方程式，将平面分成两部分，使得一侧有n/2个点，另一侧也有n/2个点。

- mousey

@chrisW 这并不重要。 - mousey

你只使用整数，还是浮点数也可以？ - Nicolas Viennot

很抱歉，为什么我们不能只按照x排序并在中间画一条竖线呢？我看到这里有许多复杂的答案来解决一个看起来微不足道的问题...一定是我漏掉了什么... - agentp

@george 假设所有点都在y轴上，或者更一般地说，许多x或y坐标是共享的。 - Glenn

3

我正在投票关闭这个问题，因为它不是关于编程的。数学问题可能在我们的姊妹站点[math.se]上被接受，但在发布之前，请检查他们的指南（也要）。 - tripleee

显示剩余5条评论

10个回答

14

在该平面上创建任意一条直线。对于每个点，将其投影到该直线上，即找到距离该点最近的直线上的点。
按照任意方向将这些点沿着该直线排序，并选择直线上的一个点，使得直线两侧的点数相等。
获得垂直于第一条直线并通过该点的直线。该直线的两侧将各有原始点数的一半。

在执行此过程时要避免某些情况。最重要的是，如果所有点都位于单条直线上，则不要选择通过它的垂直线。实际上，选择该直线本身，这样您就不需要担心投影点的问题。在实际的数学计算中，向量投影会非常有用。

- tlayton

1

与Chris的解决方案相同，多个点可能具有相同的投影。 - BlueRaja - Danny Pflughoeft

那么你的建议是“选择一行随机数据，看看能否将其拆分为两个集合，如果不能，则选择另一行随机数据？” - BlueRaja - Danny Pflughoeft

1

有一种确定性的方法（尽管目前为O(nlogn)）可以在不猜测的情况下找到（请参见我的答案）。不过猜测更实用，因为得到错误猜测的机会几乎为零。 - Aryabhatta

这是最容易编码的。只要选择一条随机线，你几乎没有机会（确切地说，你有0%的机会，尽管数值精度可能是一个问题）遇到共线性问题，除非一些点重叠（没有重叠点也是所选答案中做出的假设）。此外，这是一个O(n log(n))的解决方案，而不像“白痴”所暗示的那样。因此，我会选择这个解决方案而不是所选的答案。 - ninjagecko

然而，O(N)的解决方案是可能的，可以看看我的解决方案。 - ninjagecko

显示剩余2条评论

6

这是对将点平面分成两个相等部分的修改，可以处理存在重叠点的情况（此时会说明答案是否存在）。

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)) 的范围内进行处理。

- ninjagecko

1

我猜一个好的方法是对点进行排序/序列化/排列（例如从左到右），然后选择一条通过（或在）序列中间点之间的直线。

- ChrisW

如果所有点都在一条垂直线上，则它无法工作。 - mousey

如果所有点都具有相同的x值怎么办？此外，如果正好一半在一侧，另一半在另一侧，则该直线无法通过任何一个点（如果n为奇数，则可能通过一个点）。 - BlueRaja - Danny Pflughoeft

1

有些情况显然是无解的。例如，当您有三堆点时。一个点位于位置A，两个点位于位置B，五个点位于位置C。

如果您期望一些合理的分布，您可能可以使用tlayton算法获得良好的结果。为了选择初始线斜率，您可以确定整个点集的范围，并选择最大对角线的角度。

- relet

我并不认为这很明显 - 实际上，我认为这是不正确的。我无法想象出一种情况，在这种情况下，您无法将C划分成两半，使得A和来自C的三个点在其中一半中，B和来自C的两个点在另一半中。 - BlueRaja - Danny Pflughoeft

你不能将C分成两半。五个点要么都在这条线上，要么都不在。 - relet

哦，我明白你的意思了 - 我原以为所有的n个点都是不同的。 - BlueRaja - Danny Pflughoeft

嘿，确实需要澄清一下。我想的是n个点作为列表中不同的对象，它们可能指向相同的坐标。 :) - relet

1

中位数等分一组数字的方式类似于您正在尝试实现的方式，并且可以使用选择算法以O(n)时间计算（Cormen等人的写作更好，因此您可能希望在那里查找）。因此，找到您的x值M_x（或者如果您愿意，您的y值M_y）的中位数并将x = M_x（或y = M_y），该线将轴向对齐并平均分割点。

如果您的问题的性质要求线上不超过一个点（如果您的集合中有奇数个点，则至少有一个点将在该线上），并且您发现已经发生了这种情况（或者您只是想防止此可能性），请将所有点旋转一些随机角度θ，并计算旋转点的中位数。然后，您将通过-θ旋转计算出的中位线旋转，并将其均匀地分割点。

在有限数量的点中随机选择θ，导致问题再次出现的可能性非常小，但如果出现了，请尝试使用不同的θ再次尝试。

- andand

1

以下是我处理这个问题的方法（假设n是偶数且NO三点共线）：

1）选择Y值最小的点。我们称之为点P。

2）以此点为新原点，使所有其他点在此变换后都有正的Y值。

3）对于每个其他点（剩下n-1个点），将其视为极坐标系下的点。每个其他点可以用半径和角度表示。您可以忽略半径，只关注角度。

4）如何找到一条平均分割点的线？找到(n-1)角度的中位数。从点P到具有该中位数角度的点的线将平均分割点。

此算法的时间复杂度为O(n)。

- nybon

0

我不知道这有多有用，我见过类似的问题...

如果您已经拥有方向向量（也称为平面维度的系数）。

然后，您可以在该平面内找到两个点，并且仅使用中点公式即可找到该平面的中点。

然后，使用该平面的系数和中点，您可以使用平面的一般方程找到一个与两个点距离相等的平面。

因此，表示另一个变量的表达式将构成线路，以便您可以找到两个平面之间距离相等的线路。

有不同的方法来完成这项任务，例如使用从平面到距离方程的投影，但我认为这会使您的数学变得复杂。

- user342219

0

我从Moron和andand那里得到了灵感，并继续形成一个确定性的O(n)算法。

我还假设点是不同的，n是偶数（尽管可以更改算法以支持具有一个点在分界线上的奇数n）。

该算法尝试使用垂直线将点分开。只有当中间的点具有相同的x值时，才会失败。在这种情况下，算法确定左侧和下侧必须有多少个具有相同x值的点，并相应地旋转该线。

我将尝试用一个例子来解释。假设我们在平面上有16个点。首先，我们需要获取第8个最大x值的点和第9个最大x值的点。通过选择算法，这在O(n)内是可能的，正如另一个答案所指出的那样。如果那些点的x值不同，我们就完成了。我们在那两个点之间创建一条垂直线，这样就可以平均分割点。

问题现在是如果x值相等。所以我们有3组点。左侧的点（x < xa），中间的点（x = xa）和右侧的点（x > xa）。现在的想法是计算左侧的点数，计算出需要多少个点从中间移到那边，使得一半的点在那一侧。我们可以忽略右侧这里因为如果左侧有一半的点，那么剩下的一半必然在右侧。

假设我们左侧有3个点（c=3），中间有6个点，右侧有7个点（算法不知道中间或者右侧的数量，因为它不需要知道，但是我们也可以在O(n)时间内确定它）。我们需要从中间取5个点放到左侧。第一步得到的点现在是无用的，因为它们只由x值决定，可以是中间的任意一个点。

我们想要从中间取出y值最低的5个点放在左边，并将y值最高的点放在右边。再次使用选择算法，我们得到了第5大和第6大的y值点。这两个点的x值都等于x_a，否则我们就无法进行下一步，因为会有一条垂直线。

现在我们可以创建一个点Q，它位于这两个点的中间。这是结果线上的一个点。还需要另一个点，以便不分割左侧或右侧的任何点。为了获得该点，我们需要从左侧获取具有最小角度(b_h)的点，该角度是由该点和Q确定的线与x_a处的垂直线之间的夹角。我们还需要从右侧获取该点(带有角度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值获取最低点P_c > O(n)
从3.中的点根据y值获取最高点P_d > 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（a_g>0°且a_g<180°）的点P_g > O(n)
获取具有最小角度b_h（b_h>0°且b_h<180°）的点P_h > 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)
否则
则在P_d和P_h之间创建一个新点R ((x_d+x_h)/2, (y_d+y_h)/2) > O(1)
由Q和R确定的线将分割点 > O(1)

- rudi-moore

1

@Rudi-moore：您能否解释一下您想要做什么，而不仅仅是给出步骤？这有点难以理解。另外，有几个问题，如果a_g = b_h会发生什么？此外，在第3步中，QR线是否可能将点分割到右侧的点之间（即x坐标>x_a）？在这种情况下，您可能无法获得n/2-n/2的分割？ - Aryabhatta

@Rudi-moore：围绕Q旋转线可能行不通。我相信（虽然不完全确定）我们可以为您提供一组点的配置，使得通过Q的任何直线都不会产生均匀分割。您似乎完全忽略了垂直线右侧的点。此外，当a_h = b_h且c=0时的情况尚未讨论。 - Aryabhatta

@M 抱歉，我不是母语人士，可能这让理解起来有点困难。我编辑了帖子，并希望通过一个例子使其更清晰。对于你的问题：如果 a_g = b_h，则可以选择 P_g 或 P_h。这没有关系。两者都会生成相同的线。如果 QR将右侧的点分开，那么另一个R将被选择。我并不完全忽略右侧的点。只是在最初的步骤中。如果中间有超过n/2个点，c=0就会有问题，在这种情况下，中间的n/2个点会移到左侧。 - rudi-moore

@Rudi-moore：干得好！这看起来对我来说是正确的。它比我想象的要简单。+1。 - Aryabhatta

@mousey，@BlueRaja：我建议你们看一下这个答案。我相信这个可以用！我认为这应该是被接受的答案。 - Aryabhatta

0

补充M的答案：一种在O(n log n)时间内生成一个Q（不远）的方法。

首先，让Q成为y轴上的任何点，即Q = (0,b) - 一些好的选择可能是(0,0)或(0，(y_max-y_min)/2)。

现在检查是否有两个点(x₁, y₁)，(x₂, y₂)与Q共线。任何点和Q之间的线是y = mx + b；由于b是常数，这意味着如果它们的斜率m相等，则两个点与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Δ （例如，通过对所有i排序，然后比较m_i和i+1之间的差异）

如果我们将b增加ε，那么m的新方程变为：

m_i,new = y_i/x_i - b/x_i - ε/x_i
       = m_i,old - ε/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₁ =/= x₂。如果它们相等，则：

y₁ = m_1,oldx₁ + b = m_2,oldx₂ + b = y₂

这与我们假设的所有点都不同矛盾。因此，m_1,new =/= m_2,new，且没有两个点与 Q 共线。

- BlueRaja - Danny Pflughoeft

我们可以假设x1 = / = x2，因为那么该线将与y轴平行。 - Aryabhatta

@M：是的，这本质上是相同的事情（如果点不是不同的话，这并不一定成立）。 - BlueRaja - Danny Pflughoeft

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

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

- Aryabhatta · Accepted Answer

我假设这些点是不同的，否则可能根本不存在这样的线。

如果这些点是不同的，则总是存在这样一条线，并且可以使用确定性O(nlogn)时间算法找到它。

假设这些点是P1、P2、...、P2n。假设它们不都在同一条直线上。如果是这样的话，我们可以很容易地形成分割线。

首先将这些点转换为所有坐标（x和y）都为正数。

现在假设我们有一个神奇的点Q在y轴上，使得由这些点形成的任何直线（即任何无限直线Pi-Pj）都不经过Q。

既然Q不在这些点的凸包内，我们可以很容易地看出，我们可以通过通过Q的旋转线对这些点进行排序。对于某个旋转角度，一半的点将位于这条旋转线的一侧，另一半将位于另一侧，或者换句话说，如果我们按照线段Pi-Q的斜率对这些点进行排序，我们可以选择第(median)个和第(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

可以在O（nlogn）时间内找到D。

b_0的大小可能会变得非常大，我们可能需要处理精度问题。

当然，更好的选择是随机选择Q！概率为1，您将找到所需的点，从而使期望运行时间为O（n）。

如果我们能够找到一种以O（n）时间选择Q的方法（通过找到其他标准），那么我们可以使该算法在O（n）时间内运行。