查找给定集合中的所有共线点

Question

这是面试问题：“查找给定集合中的所有共线点”。

据我了解，他们要求打印出位于同一行的点（并且每两个点始终共线）。我建议如下。

1. 我们来介绍两种类型：Line（双精度值对）和Point（整数对）。
2. 创建一个多重映射：HashMap)
3. 循环遍历所有点对，并为每对：计算连接点的Line 并将线与这些点相加指向多重贴图。

最后，多重映射包含作为键的线和作为其值的每条线的共线点列表。

复杂度为O(N^2)。有道理吗？有更好的解决方案吗？

Answer 1

除非您一开始就确定了两个点，否则共线在这里并没有真正的意义。所以说，“找到给定集合中的所有共线点”在我看来没有多大意义，除非您固定两个点并测试其他点以查看它们是否共线。

也许更好的问题是，给定集合中共线点的最大数量是多少？在这种情况下，您可以固定 2 个点（只需使用 2 个循环），然后循环其他点并检查固定点和其他点之间的斜率是否匹配。您可以使用类似的方法进行检查，假设坐标是整数（否则您可以将参数类型更改为 double）。

// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Returns whether 3 points are collinear
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool collinear(int x1, int y1, int x2, int y2, int x3, int y3) {
  return (y1 - y2) * (x1 - x3) == (y1 - y3) * (x1 - x2);
}

所以逻辑就变成了：

int best = 2;
for (int i = 0; i < number of points; ++i) {
  for (int j = i+1, j < number of points; j++) {
    int count = 2;
    for (int k = 0; i < number of points; ++k) {
      if (k==i || k==j)
        continue;

      check that points i, j and k are collinear (use function above), if so, increment count.
    }
    best = max(best,count); 
  }
}

Answer 2

解决对偶平面中的问题，将所有点转换为线段。然后运行平面扫描以报告所有交叉点。对偶平面中经过同一点的线表示共线点。并且平面扫描可以在 O(nlogn) 时间内完成。

Answer 3

您确定您对运行时的分析是正确的吗？你说要循环遍历所有的点对，其中有n*(n-1)/2，即O(n^2)。然后将线和点对添加到地图上。不过，我不认为添加这样的线+点组合的时间是恒定的。这意味着您的总体时间是 O(n^2 log n)，而不是常数乘以 n^2，这就是 O(n^2) 的含义。

所以真正的问题是，假设它可以在 O(n^2 log n) 时间内完成，它是否可以在 O(n^2) 时间内完成。显然 O(n^2) 给出了一个下界，因为您至少必须打印出每对点，其中有 O(n^2) 。我的感觉是，这是一个完全通用的排序问题，一般来说，人们不能指望比 O(n^2 log n) 更好。然而，要充分证明这一事实可能并非易事。

另一件需要注意的事情是，该集合可能包含零个或一个点，因此您需要检查您的算法是否正确处理这些情况，否则为这些情况编写特殊情况。