查找一组给定的所有共线点 [英] Find all collinear points in a given set

问题描述

这是一个<一个href="http://www.glassdoor.com/Interview/Phone-Interview-i-Find-the-number-of-inversions-in-an-array-describe-and-$c$c-ii-Find-collinear-points-in-a-given-set-QTN_129352.htm">interview问题：查找一组给定的所有共线点

This is an interview question: "Find all collinear points in a given set".

据我了解，他们要求打印出来的点，它处于同一行（每两点始终是共线）。我建议以下几点。

As I understand, they ask to print out the points, which lie in the same line (and every two points are always collinear). I would suggest the following.

1. 让我们介绍两种行（对双打）和点（对整数）。
2. 创建一个多重映射：的HashMap＆LT;线名单，其中;点＆GT;）
3. 在遍历所有的点对与每对：计算行连接点，这些点的multimap中添加行

1. Let's introduce two types Line (pair of doubles) and Point (pair of integers).
2. Create a multimap : HashMap<Line, List<Point>)
3. Loop over all pairs of points and for each pair: calculate the Line connecting the points and add the line with those points to the multimap.

最后，多重映射包含线路作为键和一个列表共线点，每个线作为其值

Finally, the multimap contains the lines as the keys and a list collinear points for each line as its value.

的复杂度为O（N ^ 2）。是否有意义 ？有没有更好的办法呢？

The complexity is O(N^2). Does it make sense ? Are there better solutions ?

推荐答案

共线在这里并没有真正意义，除非你在2点固定到开始。这么说来，发现在一个给定的所有共线点并没有多大意义，在我看来，除非你在2点固定并测试其他人，看看他们是共线的。

Collinear here doesn't really make sense unless you fix on 2 points to begin with. So to say, "find all collinear points in a given set" doesn't make much sense in my opinion, unless you fix on 2 points and test the others to see if they're collinear.

也许一个更好的问题是，什么是共线的点，在给定的最大值是多少？在这种情况下，你可以在2个固定（只使用2个循环），然后循环比其他点，检查坡度的固定点和其他点之间的匹配。你可以使用类似这样的查收，假设坐标是整数（你可以改变参数类型一倍其他方式）。

Maybe a better question is, what is the maximum number of collinear points in the given set? In that case, you could fix on 2 points (just use 2 loops), then loop over the other points and check that the slope matches between the fixed points and the other points. You could use something like this for that check, assuming the coordinates are integer (you could change parameter types to double otherwise).

// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// 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);
}

所以，逻辑就变成了：

So the logic becomes:

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); 
  }
}

这篇关于查找一组给定的所有共线点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！