19

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..

2 Answers 2

20

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|
1
  • Careful, this solution is incomplete. There is no solution for lines that are parallel or coincident. The answer by @eirsu (below) works better.
    – David
    Aug 18, 2020 at 3:43
16

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);
    }
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.