logo标签列表

在平面上给定两条直线，如何找到最接近它们交点的整数点？

algorithmmath
31
我无法解决它：
给你8个整数：
A，B，C表示平面上的一条线，其方程为Ax + By = C
a，b，c表示另一条线
x，y表示平面上的一个点
这两条直线不是平行的，因此将平面分成4个部分。点（x，y）位于其中一个部分内。
问题：
编写快速算法，找到与给定点（x，y）处于同一块中且最接近两条给定直线交点的整数坐标点。
注意：
这不是作业，而是我完全不知道如何处理的旧Euler类型任务。
更新：
您可以假设输入的8个数字是32位有符号整数。但是您不能假设解决方案将是32位的。
更新2：
困难情况-当线条几乎平行时-是问题的核心
更新3：
问题的作者表示，解决方案是具有线性O（n）算法的。其中n是输入的大小（以位为单位）。即：n = log（A）+ log（B）+ ... + log（y）
但我仍然无法解决它。
请说明已发布算法的复杂度（即使它们是指数级的）。
5
这不是来自欧拉计划（Project Euler）的问题，而是类似欧拉问题（Euler-type problem）。 - Łukasz Lew
2
@Pavel：我的解决方案需要计算每条线的两个任意点和两个3x3行列式，这为什么会慢？ - XenF
4
很遗憾没有好的答案。大多数编程问题会迅速得到许多答案，而且大多数都是正确的。我不知道为什么算法问题不能得到同样的待遇。至少如果人们不发帖，除非他们有一个真正的解决方案... - IVlad
2
以下是一个可能比较复杂的案例： 第一行 10000019 X - 10000015 Y + 909093 = 0。 第二行 -10000022 X + 10000018 Y + 1428574 = 0。 点 (x,y) 是坐标原点。 - Eric Bainville
3
在相同的精神上，这里有另一个更简单的例子：100003 X - 99999 Y + 9092 = 0 ; -100006 X + 100002 Y + 14286 = 0 ; (x,y) = (0,0)。在这个例子中，解似乎是 (-194800325,-194808117)。 - Eric Bainville
显示剩余16条评论
18个回答
-1

我以前也曾经做过类似的事情，需要找到一个多边形的标记点。

最终的结果是在Autocad上的Pentium 3处理器中5秒内完成了70000个多边形。如果不算Autocad大约只需要3秒钟。

首先你需要找到一个交点。 接下来，你需要找到你的点（x，y）所在的位置并通过它画一条水平或垂直线，以便你的两条线（A，B，C）和（a，b，c）以及一个新的水平/垂直线形成一个三角形。 如何确定是垂直还是水平线： 通过（x，y）点绘制水平线和垂直线，然后检查以下内容： - 对于水平线： - 如果A、B、C线和你的水平线以及a、b、c线的交点使得此方程成立（与A、B、C相交）。x < x < （与a、b、c相交）。x，那么你就知道你在里面了。（你可以交换A、B、C和a、b、c，只要x在内部即可。 - 对于y，类似地进行检查，只需检查y而不是x。

现在你有一个三角形并且知道它在哪里（左、右、上、下）。例如，如果它是一个右三角形（就像上面的图表），您需要取交点的x值并对其进行向上取整（如果在左侧，则向下取整），对于y坐标也同理。然后，您要通过它绘制一条扫描线，该扫描线与您的（x，y）点扫描线平行，并检查是否有点位于交点内（类似于上面的 x
当您找到一个点时，可能不是最接近的点。因此，在增加步幅时，您必须对最后一个不好的点和最后一个点（在那里找到整数）进行二等分。
复杂度会是什么？你找到的点可能非常远。 - Łukasz Lew
如果你想优化最后一部分并且去除二分法，从而降低复杂度，可以使用三角形相似性质。在第一个可能的点上画一条水平/垂直线，使得该线长度大于1个整数单位。该线上应该有一个整数。将另一个轴上的数字向下取整/向上取整（取决于象限）并找到交点。可能存在更靠近该点的另一个点，但该点不应该远离该方向指向交点的距离太远。 - dmonlord
-1

我怀疑这是一个数学优化问题，可以用拉格朗日乘数法来解决...

-1

我认为这个问题有三个部分。

  1. 计算两条线的交点，并保存该点的X和Y坐标

  2. 找到给定点所在的区域。这应该很容易，因为您有两条线的斜率以及由给定点和交点形成的线的斜率。将它们称为m_line1、m_line2和m_intersect。如果m_intersect存在，则有一个公式可以使用这些值和给定点的位置来确定区域。

  3. 找到最接近的整数。一旦您知道上述第1步的值和第2步的斜率，就可以进行直接的计算。您可以使用蛮力法，但是也有一种优雅的数学解决方案。

至少这是我采取的步骤。

更新以添加更多内容

好的，我将从讨论第2步开始。

如果你计算给定点和交点的斜率，那么你就会得到 m_intersection。这是一条通过交点的直线的斜率。假设 m_line1 是两个斜率中较大的一个，因此在交点之后 x 增加时，line1 在 line2 的“上方”。这样更容易为部分名称考虑。我们将称 x 大于交点坐标 x 的线1和线2之间的银片所给出的部分为A，然后按顺时针方向命名其他3个部分，使A和C相对。

如果 m_intersection 在 m_line1 和 m_lin2 之间，则它必须位于两个部分A或C之一中。哪个部分是根据 x 坐标值与交点的 x 坐标进行简单测试。我们定义A为具有较大值的部分。如果斜率在 m_line1 或 m_line2 之外，则可以进行类似的计算。

这将为您提供您所在的部分。您所做的只是计算1个交点（如果按传统方式进行计算，则需要5次乘法，2次除法和一些减法），3个斜率，然后进行几个整数比较。

编辑＃3-受欢迎的需求回来了！

这就是我如何计算＃3，即最接近交点的整数点。它可能不是最好的方法，但它使用二分查找，因此它的时间复杂度为O（log n），其中n与线斜率的差的倒数有关。它们越接近，n就越大。

首先，计算两条直线斜率的差。假设为1/8。这意味着从交点开始，您必须沿x轴向外移动8个单位，才能保证在两条直线之间有一个整数（它可能在其中一条直线上）。现在，如果交点本身不在整数x坐标上，则需要进一步移动以确保您的起始点在整数x坐标上，但是它是有界的。如果交点在x = 1.2处，则在上面的示例中，最坏的情况下，您将从x = 41开始，然后沿y轴向下移动约5个单位。选择所得到的y值的ceil或floor。这并不是非常关键。
现在您有了一个起始点，最接近的点可以通过二分查找来近似。您的新线段位于交点和起始点之间，您的移动单位是该线段斜率的倍数。计算线段的中点，并查看它是否在两条直线之间。如果不是直接命中，请加上或减去1，如果其中任何一个命中，请将剩余距离减半并再次执行。否则搜索该线段的另一半。

如果您没有斜率差小于1，我认为问题可能更简单（暴力搜索交点周围的空间）。但这只是上述搜索的特殊情况，在这种情况下，您不需要走得那么远才能找到起点。

我没有点踩是因为我不知道这种方法是否有潜力，但你的回答并不是很有帮助。仅仅在每个重要步骤上说“有一种方法可以做到这一点”真的没有帮助任何人。 - IVlad
3
@IVlad，这种方法与费马最后定理的证明一样有帮助 :-) - P Shved
1
抱歉语言简洁。我之前不小心泄露了作业答案。而且，我正在做饭，没有时间完全阐述一切。 - Phil
@Phil，我对第三个问题非常感兴趣。请在此处发布优雅的数学解决方案。 - Hamish Grubijan
你寻找解决方案的外部边界的方法似乎是有效的，但我不能同意你关于二分查找逻辑的有效性。只有当发散率非常低时，这个问题才是有趣的，因此线条发散超过1的交点将离交点非常远。任何更接近满足条件的点都不一定与您的起点有任何特殊关系。看起来你的二进制跳跃不会收敛于一个解决方案。 - Alan
显示剩余2条评论
-1

嗯，这取决于什么被认为是足够快。

让我们把点[x,y] P命名为点。我也会称具有整数坐标的点为“整数点”。

我提出的算法：

  1. 找到这两条线相交的点Q。（Q=[x_q, y_q]）

  2. 获取Q和P之间的线的函数，y=f(x)或反向x=g(y)；

  3. 根据其角度确定QP更垂直还是水平。假设它是垂直的，以简化以下解决方案（如果它是水平的，则轴将简单地反转，并且在我写x的地方，它将是y，反之亦然）。

  4. 沿着从Q到P的线路获得我们得到的第一个整数坐标y_1。

  5. 计算该点的第二个坐标：x_1=f(y_1)。该点位于我们的线段中。

  6. 查找具有坐标[floor(x_1);y_1]和[floor(x_1+1);y1]的周围整数点是否在我们感兴趣的线段中。

6.1 如果是，则我们迭代通过水平线x_3=f(y_1)来查找仍在我们线段内且具有(x_3-x_q) -> min的整数点。那个点就是我们的答案。

6.2 如果不是，则将y_1增加一并从步骤5重复。

OP要求编写一个“快速”的算法，而你的算法不符合要求。 - P Shved
1
@Pavel，这是一个编程问题论坛；你的问题不符合要求。我的算法可以在32位精度下在不到2秒的时间内解决最坏情况。 - user283145
2
@~buratinas，使用64位精度将需要20亿秒（60年），这并不是“快速”的。 - P Shved
@~buratinas：这并没有什么意义。你不能选择算法表现良好的案例，然后说算法很好，而忽略它在糟糕案例中的表现。 - IVlad
-1

这里提供一种线性时间（即O（＃A，B，C等位数），假设位数适合O（1）个内存字）的解决方案，使用线侧测试和二分查找：

假设w.l.o.g. B！= 0（否则我们将A与a交换，B与b交换，C与c交换）。执行线侧测试以查看点在线（A，B，C）的哪一侧。假设点在线下方（或在线上）。

请注意，对于任意x坐标x'，我们可以通过y' =（C-A * x'）/ B在O（1）时间内计算最小的y'，使得（x'，y'）在线（A，B，C）上方。

现在，假设输入点（x，y）在（a，b，c）的右侧，在水平线的情况下在下方。然后，我们可以相对于线（a，b，c）执行（x'，y'）的线侧测试，并确定我们需要增加x'还是减少x'以找到最小的x'，使得（x'，y'）落在（a，b，c）的正确一侧。

对于这个点进行二分查找最多需要O(w)时间，其中w是A、B等中位数的位数。请注意，因为输入坐标x和y都适合于一个整数，所以返回值也是如此。即使x和y不一定在这些范围内，而且线条几乎平行，也可以在O(w)时间内找到一个合适的x，因为斜率差是A/B-a/b=(Ab-aB)/Bb<=1/2^(2w)，所以答案的x坐标将适合于O(1)字的内存。我们仍然需要找到答案的y坐标，这也可以通过二分查找找到。

-2
在这四个坐标点中，有一个位于两条线的左侧，有一个位于两条线的右侧，有一个位于一条线的右侧同时位于另一条线的左侧，最后一个则位于一条线的左侧同时位于另一条线的右侧。如果你将其画出来会更容易理解。
一个点相对于一条线的位置取决于以下行列式的结果：
[1 p1x p1y; 1 p2x p2y; 1 p3x p3y]，其中p1和p2是线上的任意两点，p3是给定的点。
如果它等于零，那么这个点在线上，如果它大于或小于零，那么它在一侧，侧面取决于p1和p2在线上的相对位置以及你在平面上如何定义左侧和右侧。
问题在于选择满足两条线的同样条件的两个点，以使结果始终一致，也许p1的x坐标始终比p2小（如果该线是垂直的，则为y坐标）。
当你得到每条线的两个点后，计算两个行列式即可完成。
编辑

哎呀，这部分地解决了问题。不管怎样，您可以使用此方法计算XY点所在的边，计算交点，然后计算所有有效点（floor（x），floor（y）），（floor（x），ciel（y））的相对位置，...

-2

第一条线定义为y1 = m1 * x1 + b1。 第二条线定义为y2 = m2 * x2 + b2。

m1，m2，b1，b2都是已知的值[常数]。

确保m1 ≠ m2。

找到交点，即满足y1 == y2且x1 == x2的点，定义为（X，Y）。

Y = ((m1*b2)/m2)/(m1/m2-1)

X = (Y-b1)/m1

最近的点可以通过将X和Y四舍五入到最近的整数来找到。您可以决定如何处理.5。

-2
我的建议是这样的。假设包含我们目标点的平面部分完全跨越左下象限，从两条线的交点望去（其他象限类似，而当平面部分跨越多个象限时将在后面考虑）。
让给定的两条直线为l1和l2（l1比l2“更平缓”）。

  1. 找出X = (a, b)，线l1和线l2的交点。

  2. 令k = 0。

  3. 让vk成为与x坐标xk = floor(a-k)垂直的线。

  4. 找到vk与l1和l2的交点(V1 = (x1, y1), V2 = (x2, y2)点)。

  5. 如果floor(y1) != floor(y2)，则目标点为(x1, floor(y1))。结束。

  6. 如果floor(y1) == floor(y2)，则将k增加并转到步骤3。

由于 l1 和 l2 不平行，abs(y1 - y2) 必须随着 k 而增长。当 abs(y1 - y2) 大于 1 时，算法一定会停止（不过它可能更早地停止）。

现在让我们考虑（容易的）情况，即我们所要处理的平面部分跨越了一个以上象限，从两条线的交点看（它可能跨越两个或三个象限）。

  1. 找到 X = (a, b)，l1 和 l2 的交点。

  2. 找到 A，四个离 X 最近且具有整数坐标的点的集合。

  3. 找到 B，A 中位于目标平面部分中的点的集合。

  4. B 中距离 l1 和 l2 的交点最近的点是目标点。

（此情况运行时间恒定。）

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接