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

  • 9

    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 {
        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;

  • 3

    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.

  • 0

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

  • 2

    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.

  • 0

    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]?

  • 0

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

  • 0

    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]

  • 0

    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

  • 0

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

  • 0

    Oh buddy, you are right.

  • 0

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

Log in to reply

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