我发现 CareerCup

给定一个二维平面，假设有在它周围6000点。查找线，传递了最点数。

Given a 2D plane, suppose that there are around 6000 points on it. Find a line which passes the most number of points.

很多答案的说，这个问题是很难，涉及某种特殊的算法。

Many answers there say this question is hard and involving some kind of special algorithms.

但我的看法是不同的，也许我是错的。

But my view is different and maybe I am wrong.

这是我的想法：

首先，我会给一个轴系统，以2D平面。因此，每一个点都会有其独特的x和y，即 {X，Y} 。为了简单，我们可以把轴系统的 {0,0} 作为整个平面的左下角，因此每个x和y大于0。

First I will give a axis system to the 2D plane. Hence, every point will have its unique x and y, i.e., {x, y}. For simplicity, we can put the axis system's {0, 0} as the left bottom of the whole plane and therefore every x and y are bigger than 0.

然后，我有一个理论：

如果几个点是在同一直线上，则它必须是在以下3情况之一：

If several points are on the same line, then it must be in one of the following 3 cases:

的 X 值相同 的 是 值相同 的 X / Y 或 Y / X 值是相同的。但 X / Y 的情况是一样的 Y / X 的情况下，所以我们只专注于 X / Y their x values are the same their y values are the same their x/y or y/x values are the same. But x/y case is the same as y/x case, so let's just focus on x/y.

然后，我将有3个哈希表。

Then I will have 3 hashtables.

第一个（哈希表-X ）是与键X ，该值是具有相同点的列表中移除x ;

The first one (hashtable-x) is with key of x, the value is the list of points which have the same x;

第二个（哈希表-Y ）是 y的关键和值具有相同Ÿ点列表;

the second one (hashtable-y) is with the key of y and the value is the list of points which have the same y;

然后我扫描整个6000点，每一个点，我会得到它的 X 从哈希表-X ，并把点成槽的值（名单）;然后，我会做同样的事情哈希表-Y 和哈希表-XY 。

Then I scan the whole 6000 points, for each point, I will get its x from hashtable-x, and put the point into the value (a list) of that slot; then I will do similar things to hashtable-y and hashtable-x-y.

最后，我会扫描所有列出了3哈希表，找到最长的列表将包含所需行的点。

Finally, i will scan all lists in the 3 hashtables and find the longest list will contains the points of the desired line.

您如何看待我的算法？

好吧，这里是重复的，抱歉，我没有发现这个问题了。

Ok, here is the duplicate, sorry that I didn't find that question before.

What是目前最有效的算法来找到一个直线经过最高分？

推荐答案

您算法将无法按说明正常工作。考虑多点落在直线y = 2X + 1，这意味着你得到（1,3），（2,5），（3,7），（4,9）和（5,11）。

Your algorithm won't work as stated. Consider many points fall on the line y=2x + 1, meaning that you get (1,3),(2,5), (3,7), (4,9), and (5,11).

我不认为你预计，除非你有在计算几何研究生水平的课程，以解决这个问题。该协议是对所有的点转换为线在对偶空间，使用点线二重性和找到的点最线相交。天真，你可以经历每对线和评估他们的分析形式相交于为O（n ^ 2）做到这一点。我也认为你能做到为O（n log n）的使用平面扫描式的算法，但我不知道的细节。

I don't think you're expected to solve this unless you have a graduate level course in computational geometry. The deal is to convert all the points to lines in the dual space, using point-line duality and find the point at which most lines intersect. Naively you can do this in O(n^2) by going through every pair of lines and evaluating where they intersect in analytic form. I also think you can do O(n log n) by using plane sweep style algorithms but I'm not sure of the details.