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

Question

这是一个采访问题:"查找给定集合中的所有共线点".

据我所知,他们要求打印出位于同一行的点(并且每两个点总是共线的).我建议如下.

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

最后,multimap包含作为键的行和每行的列表共线点作为其值.

复杂度为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); 
  }
}

Answer 2

解决双平面问题,将所有点转换为线段.然后运行平面扫描报告所有交叉点.双平面中的线将通过相同的点表示共线点.平面扫描可以在O(nlogn)时间内完成.