平面内最大共线点
N 点作为输入给出。
假设(x1,y1), (x2,y2)...(xn,yn)。
是否有非组合解决方案来找到最大共线点数？它们可以排列在一个有助于计算的奇特数据结构中吗？
N points are given as input.
Let's say (x1,y1), (x2,y2)... (xn,yn).
Is there a non-combinatorial solution to find the maximum number of collinear points? Can they be arranged in a fancy data structure that would help this computation?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
对于每个点 i，找到到每个其他点 j 的斜率，并且
寻找重复项。可以通过对斜率进行排序来找到重复项
比较相邻值。点 i 与点共线
每组重复项。随时记录最大组数。
对于每个 i，您有 n-1 个斜率需要计算、排序和比较。
因此，使用 (n log n) 排序，算法的复杂度为
O(n^2 log n)。
For each point i, find the slope to every other point j and
look for duplicates. Duplicates can be found by sorting the slopes and
comparing adjacent values. Point i is collinear with the points in
each set of duplicates. Keep track of the maximal set as you go.
For each i, you have n-1 slopes to calculate and sort and compare.
Therefore, using a (n log n) sorting, the complexity of the algorithm is
O(n^2 log n).
请阅读此处对此问题的讨论
Read through discussion on this question here on
以下可能是解决该问题的一种方法：
1) 找到所有选择 C(n,2) 对的斜率
2）将这些斜坡分入多个桶中。
3）在这些桶中找到独立的线（因为它们可能包含平行线族）
4）建立最长的线段
更具体地说：
1) 执行 (n-1) * (n-1) 次计算找出这么多斜率。可以使用地图来保存这些点，并以坡度作为关键点。映射中的值可以使用集合来表示。该集合可以包含代表两个点的对象。像这样的东西：
{斜率1：[(p1，p2)，(p1，p3)，(p1，p2)，(p4，p5)]}
{slope2: ....}
2) 现在，在每组点中找到独立的线。我相信迭代集合中的每个点我们可以得到这个。例如
在访问 (p1, p2)、(p1, p3)、(p1, p2)、(p4, p5) 时，我们可以将其分为形成共线点的 n 组。设置可以从以下内容开始：
[p1，p2]，当我们遇到下一对（p1，p3）时，我们检查它们中的任何一个是否已经在当前运行集中。如果其中至少有一个是，那么我们将新点添加到该集合中，否则创建一个新集合。迭代这组点中的所有点后，我们将得到以下两组，代表 2 个独立的线段：
[p1、p2、p3]
[p4，p5]
现在可以使用这些大小来建立我们发现的最长线段
。从复杂性来看，它应该是 O((n-1)*(n-1) + n) ~ O(n^2)。假设在 Set 中查找对象的时间复杂度为 O(1)
Following could be one way to solve it:
1) Find all the slopes selecting C(n,2) pairs
2) Bin these slopes into multiple buckets.
3) Within these buckets find independent lines (as they might contain family of parallel lines)
4) Establish the longest line segment
More concretely:
1) Perform (n-1) * (n-1) calculations to find so many slopes. A map could be used to save these points with slopes as keys. The value in the map could be a represented using a Set. The Set could contain an object representing two points. Something like this:
{slope1: [(p1, p2), (p1, p3), (p1, p2), (p4, p5)]}
{slope2: ....}
2) Now, within each set of points find independent lines. I believe iterating over each point in the set we can arrive at this. For example
while visiting (p1, p2), (p1, p3), (p1, p2), (p4, p5) we can divide this into n-Sets which form collinear points. Set could start with:
[p1, p2], when we encounter next pair (p1, p3), we check if either of them are already in the current running set. If at least one of them are then we add the new points to this set, otherwise create a new set. After iterating over all the points in this set of points we will have the following two sets, representing 2 independent line segments:
[p1, p2, p3]
[p4, p5]
Size of these could now be used to establish the longest line segment we find
Complexity wise, it should be O((n-1)*(n-1) + n) ~ O(n^2). Assuming looking up objects in Set is O(1)