# Does anyone use the idea of Hough Transform O(N)?

• When I first read the question, the idea of "hough transform" pops out. I wrote my solution using this idea, but I get a TLE. As you may see, the complexity of Hough transform is only O(180N), which is much lower than those O(N^2) solutions in this discussion board.

I expected to see a "wrong answer" error, because "hough transform" has the parameter theta ( in polar coordinates ): you may have to sample the entire theta space and thus get an approximate result instead of an accurate one. Anyway, I guess some of you might be interested in knowing this classic pattern recognition algorithm.

``````#define computeRho( pt, T ) ( ( pt.x * cos( T ) ) + ( pt.y * sin( T ) ) )

class Solution {
public:
int maxPoints(vector<Point> &points) {
if ( points.size() <= 2 ) {
return points.size();
}
int max_points = 0;
for ( int i = 0; i < 180; i++ ) {
double theta = double( i ) / 180.0 * 3.141592657;
map<int,int> accumulator;
for ( int j = 0; j < points.size(); j++ ) {
int rho = round( computeRho( points[j], theta ) );
accumulator[ rho ]++;
if ( accumulator[ rho ] > max_points ) {
max_points = accumulator[ rho ];
}
}
}
return max_points;
}
};``````

• Hough transformation was my first thought as well.
It is true for the complexity of 180N. But as mentioned in a previous post, the largest case is when N=112, which means 180N is more time consuming than N^2 when N is much smaller.

• Hough transform is usually used in image processing, for cases which don't have accuracy request.

• In this case, you can not quantize Hough transform to 180 bins, which is for estimation a line.
For accurate case, you need infinity number of bins.

• This is my first time to know the Hough Transformation,so I'm sorry for that I have a few questions that sound naive：）
The parameter rho represents the algebraic distance between the line and the origin, while theta is the angle of the vector orthogonal to the line.In your solution,it seems that I can control x,y and theta to get p however,I think we cannot control x and y,becasuse the point(x,y) may not be the crossing of the vector orthogonal to the line.So why the parameter rho can represent a line pass a point points[j]?

• This is a pretty approximation, but I think you can't guarantee this stands correct for all cases, especially when rho becomes extremely large.

• Isn't the range of theta have to be [0, 2 * pi]?
If you range i from 0 to 180, the range of theta becomes [0, pi]

• Hi Feb 3, I tried your solution. But it seems failed at the following case:
Input: [(-4,-4),(-8,-582),(-3,3),(-9,-651),(9,591)]
Output: 2
Expected: 3

• The poster is yue2. As they mentioned in their post I expected to see a "wrong answer" error, such result seems make sense.

• Oh buddy, you are right.

• [0,pi] and [pi,2*pi] are the same,you only just get one of them

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.