平面上最多的共线点数

Question

给定 N 个坐标点。

假设这些点为 (x1,y1), (x2,y2)... (xn,yn)。

是否有一种非组合的解决方案来找到共线点的最大数量？它们可以被安排在一个高级数据结构中以帮助进行这种计算吗？

- Rohan Monga

---

看一下这个问题及其答案：https://dev59.com/ZW855IYBdhLWcg3wuG6W - brainjam

Answer 1

对于每个点 i，找到它与其他点 j 之间的斜率并查找重复项。可以通过排序斜率并比较相邻值来找到重复项。点 i 与每组重复项中的点共线。在进行操作时要记录最大的重复项集。

对于每个 i，您需要计算、排序和比较 n-1 条斜率。因此，使用 (n log n) 排序，该算法的时间复杂度为 O(n^2 log n)。

- Johan Kotlinski

---

点对可能具有相同的斜率，但是与共线无关而是平行的。您需要查看y截距以及斜率。 - Gareth Rees

这里的斜率是相对于当前被研究的点i而言的。因此不存在平行线的可能性。 - Johan Kotlinski

嗨kotlinski， 您能否添加一些示例代码？我在查找重复行方面遇到了问题。因此，我的结果会因为重复的数量而被乘以。 - CR Sardar

Answer 2

在这个问题上阅读此处的讨论

- Rohit J

Answer 3

以下可能是解决它的一种方法： 1）选择C(n,2)对，找到所有斜率 2）将这些斜率分成多个桶。 3）在这些桶中找到独立的直线（因为它们可能包含平行线族） 4）建立最长的线段

更具体地说： 1）执行(n-1)*(n-1)次计算以找到这么多斜率。可以使用映射来保存这些带有斜率键的点。映射中的值可以使用Set表示。Set可以包含表示两个点的对象。类似于这样： {slope1: [(p1, p2), (p1, p3), (p1, p2), (p4, p5)]} {slope2: ....}

2) 现在，在每组点中找到独立的线路。我相信我们可以通过迭代集合中的每个点来实现这一点。例如，当访问(p1、p2)、(p1、p3)、(p1、p2)、(p4、p5)时，我们可以将其划分为形成共线点的n个集合。当我们遇到下一对(p1、p3)时，集合可以从[p1、p2]开始。如果它们中的至少一个已经在当前运行的集合中，则我们将新点添加到该集合中，否则创建一个新集合。在迭代这个点集后，我们将得到以下两个集合，表示2条独立的线段: [p1、p2、p3] [p4、p5] 现在可以使用它们的大小来确定我们发现的最长线段

就复杂性而言，它应该是O((n-1)*(n-1)+n) ~ O(n^2)。假设在set中查找对象的复杂度为O(1)

- shintu