Tuesday, March 15, 2011

Intersection of two lines defined in (rho/theta ) parameterization

Have created a c++ implementation of the Hough transform for detecting lines in images. Found lines are represented using rho, theta, as described on wikipedia:

"The parameter r represents the distance between the line and the origin, while θ is the angle of the vector from the origin to this closest point "

How can i find the intersection point in x, y space for two lines described using r, θ?

For reference here are my current functions for converting in and out of hough space:

//get 'r' (length of a line from pole (corner, 0,0, distance from center) perpendicular to a line intersecting point x,y at a given angle) given the point and the angle (in radians)
inline float point2Hough(int x, int y, float theta) {
    return((((float)x)*cosf(theta))+((float)y)*sinf(theta));
}

//get point y for a line at angle theta with a distance from the pole of r intersecting x? bad explanation! >_<
inline float hough2Point(int x, int r, float theta) {
    float y;
    if(theta!=0) {
            y=(-cosf(theta)/sinf(theta))*x+((float)r/sinf(theta));
    } else {
            y=(float)r; //wth theta may == 0?!
    }
    return(y);
}

sorry in advance if this is something obvious..

From stackoverflow
  • Looking at the Wikipedia page, I see that the equation of a straight line corresponding to a given given r, θ pair is

    r = x cosθ + y sinθ 
    Thus, if I understand, given two pairs r1, θ1 and r2, θ2, to find the intersection you must solve for the unknowns x,y the following linear 2x2 system:
    x cos θ1 + y sin θ1 = r1
    x cos θ2 + y sin θ2 = r2
    

    that is AX = b, where

    A = [cos θ1  sin θ1]   b = |r1|   X = |x|
        [cos θ2  sin θ2]       |r2|       |y|
    
  • Had never encountered matrix maths before, so took a bit of research and experimentation to work out the proceedure for Fredrico's answer. Thanks, needed to learn about matrices anyway. ^^

    function to find where two parameterized lines intersect:

    //Find point (x,y) where two parameterized lines intersect :p Returns 0 if lines are parallel 
    int parametricIntersect(float r1, float t1, float r2, float t2, int *x, int *y) {
        float ct1=cosf(t1);     //matrix element a
        float st1=sinf(t1);     //b
        float ct2=cosf(t2);     //c
        float st2=sinf(t2);     //d
        float d=ct1*st2-st1*ct2;        //determinative (rearranged matrix for inverse)
        if(d!=0.0f) {   
                *x=(int)((st2*r1-st1*r2)/d);
                *y=(int)((-ct2*r1+ct1*r2)/d);
                return(1);
        } else { //lines are parallel and will NEVER intersect!
                return(0);
        }
    }
    

0 comments:

Post a Comment