Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

like image 758
erisu Avatar asked Dec 20 '08 17:12

erisu


People also ask

How do you find the intersection of two lines in Opencv?

You can use for e.g. cv2. kmeans() with theta as your data you want to split. Then, to calculate the intersections, you can use the formula for calculating intersections given two points from each line.

What is Rho and Theta?

The Rho ( ) angle is the angle off the reference axis Z-axis (or X-axis), while the Theta ( ) angle is defined as the rotation around the reference axis starting from the X-axis (or Z-axis). The range is 0° through 180° for the Rho angle, and -180° through +180° for the Theta angle.

What is the intersection of two lines?

When two or more lines cross each other in a plane, they are called intersecting lines. The intersecting lines share a common point, which exists on all the intersecting lines, and is called the point of intersection. Here, lines P and Q intersect at point O, which is the point of intersection.


2 Answers

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|
like image 74
Federico A. Ramponi Avatar answered Sep 23 '22 04:09

Federico A. Ramponi


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);
    }
}
like image 21
erisu Avatar answered Sep 21 '22 04:09

erisu