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

Question

这是一个 interview question : “找到给定集合中的所有共线点”。

据我了解，他们要求打印出位于同一条线上的点(并且每两个点总是共线的)。我会提出以下建议。

1. 让我们介绍两种类型Line (一对 double )和Point (一对整数)。
2. 创建多图:HashMap<Line, List<Point>)
3. 遍历所有点对并为每一对:计算Line连接点并将包含这些点的线添加到多图。

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

复杂度为 O(N^2)。是否有意义 ？有更好的解决方案吗？

Answer 1

除非您首先确定 2 个点，否则这里的共线实际上没有意义。所以说，“找到给定集合中的所有共线点”在我看来没有多大意义，除非你固定 2 个点并测试其他点以查看它们是否共线。

也许更好的问题是，给定集合中共线点的最大数量是多少？在这种情况下，您可以固定 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); 
  }
}