c++ - 从将形成一条线的一组坐标中确定点

Question

我想制作一个在笛卡尔平面上生成 10 - 100 个随机坐标的程序，它应该找到哪些点将形成一条线。

它应该是至少四个可以形成一条线的点的组合。为此，我可以找到四个选定点之间的斜率，以确定它们是否可以形成一条线。

然而，困难的部分是我怎样才能把所有的点结合起来？我想使用蛮力方法找到至少四个点的所有组合，然后检查它们之间的斜率，看看它们是否可以形成一条线。

任何关于我如何解决这个问题的建议，例如有效地找到组合将不胜感激。

Answer 1

我认为尝试所有 4 点没有任何好处。只需取每一对点，计算它们形成的直线的方程 y = mx + c，然后将每一对 (m, c) 插入到数组中。然后对这个数组进行排序（不管 m 还是 c 是第一个排序键）。属于同一行的所有点对将在排序数组中显示为连续块：如果同一行上有 n 个点，则相应块中将有 n^2 个连续元素，但很容易识别 n不同的点。时间和空间复杂度：O(n^2 log n)。

Answer 2

您不需要所有组合，因为您的 4 元组中有两个不同的失败点：在 3 和 4。显然，如果前 3 个不是线性的，则第 4 个不会使整个元组成为线性的。此外，如果 ABC 不是线性的，那么无论第 4 点是什么，它们都会失败。

因此，考虑到这一点，我将创建一个包含 4 个项目的向量并将其称为我的结果向量，并在结果向量中的索引从 0 到 4，从 0 开始。向量将在您的点数组中保存索引，并且将使用 -1 初始化为 N/A（尚未）。

然后对于算法的每个循环：

• 您在结果向量索引位置增加结果向量项。
• 如果结果向量项不是唯一的，请再次递增它。如果您到达阵列的末尾，您的项目就会用完。您将结果向量索引递减以回溯。如果您也在结果向量的开头，那么您就完成了。不要忘记将您丢弃的项目设置为-1！
• 如果索引为 3，则检查点是否是线性的，如果不是，则什么也不做。
• 如果索引为 4，则检查点是否是线性的，如果是，则有解决方案！耶！如果不是，你什么也不做。
• 如果索引不是 3 或 4，则增加索引以获得新点。

Answer 3

您只需要考虑点对的所有组合。这些定义了由点形成的所有可能的线。

因此，您考虑点 (Pi,Pj)，其中 i 在 1 到 n 的范围内，j 在 i+1 到 n 的范围内。

我们使用形式的线方程，ax+by+c=0因为它很容易确定并且没有退化的情况（它的斜率是无限的）。

对于两个点 (x1,y1) 和 (x2,y2)，该方程为(y2-y1)x+(x2-x1)y+(x1y2-x2y1) = 0。

要测试点 (x3,y3) 是否在这条线上，只需将方程中的 x 替换为 x3 并将 y 替换为 y3 即可。如果结果为 0，则该点在线上。由于我们使用精度有限的浮点数，我们测试abs((y2-y1)*x3+(x2-x1)*y3+(x1y2-x2y1)) < epsilonwhereepsilon是一个非常小的值。

对于每条线（对 (Pi,Pj)），如果它属于该线，则使用 k 在 j+1 到 n 范围内测试所有点 Pk。您跟踪在线上找到的所有点，如果数字大于 2（总计 > 4），则打印结果。

您对所有点对 (Pi,Pj) 执行此操作。

我必须提供代码吗？

Answer 4

您可能需要对您的点集应用PCA 分析。

Answer 5

通常四个随机点由于它们的随机性而不会形成一条线。如果你想做这样的事情，你可以对每四个不同的点集进行线性回归，检查各自的方差，然后选择方差低于阈值的集合，你必须确定这些阈值何时“对齐在一条线上” ”。