Calculation of intersection points of two lines returns -1.#IND in CSV-file

Question

In my software I try to calculate the intersection points of two lines. I start with four double variables for the first line (two for x/two for y), and four double variables for the second line. The math is clear to me, and on paper it's working. For further processing I have to save the intersection points in a CSV file. But when I open the file, all I have is -1.#IND, which as I understand means negative infinite or Not A Number. So here's my code:

double A_x=boundingbox[i][0];
double A_y=boundingbox[i][1];
double B_x=boundingbox[i+1][0];
double B_y=boundingbox[i+1][0];
double C_x = matrix[j][0];
double C_y = matrix[j][1];
double D_x = matrix[j+1][0];
double D_y = matrix[j+1][1];

So first I get the coordinates of the four points from two vectors.

double AB_x=B_x - A_x;
double AB_y=B_y - A_y;
double m1 = AB_y / AB_x;
double c1 = A_y - m1*A_x;

double CD_x = D_x-C_x;
double CD_y = D_y-C_y;
double m2 = CD_y/CD_x;
double c2 = C_y-m1*C_x;

With the coordinates I'm able to set up the equations for the two lines. In the next step I have a look at the variables m1 and m2. If m1minus m2is 0 there's no intersection point.

if( (m1-m2) != 0) {
    double point_x = (c2 - c1) / (m1 - m2);
    double point_y = m1 * point_x + c1;

    intersects.push_back(std::array<double, 3>());
    int q = intersects.size()-1;
    intersects[q][0]=point_x;
    intersects[q][1]=point_y;
    intersects[q][2]=i;
}

In the end I just use a for-loop to save the vector intersects in a CSV-file.

for(int i=0; i<intersects.size(); i++)
{
    file << "Intersects" << ";" << intersects[i][0] << ";" << intersects[i][1] << ";" << intersects[i][2] << endl;
}

But when I open the file I just had the mentioned error. I already tried a different kind of datatype like float, but nothing change. I know the first and the last part of the code is working, because I already used it with a different kind of math, in this my mathematical approach was, however, incorrectly selected, so I had to change it. So I think the problem has to be in the condition for the if-statement.

Edit: With the help of the comments, I've now adapted my code. So this is my new code:

for(int a=fillingStart; a<boundingbox.size()-1; a += 2)
{
    double Ax=boundingbox[a][0];
    double Ay=boundingbox[a][1];
    double Bx=boundingbox[a+1][0];
    double By=boundingbox[a+1][1];

    double B1=Bx-Ax;
    double A1=By-Ay;

    for(size_t j=0; j<(matrix.size()-1); j++)
    {
        double Cx=matrix[j][0];
        double Cy=matrix[j][1];
        double Dx=matrix[j+1][0];
        double Dy=matrix[j+1][1];

        double B2=Dx-Cx;
        double A2=Dy-Cy;

        double det=A1*B2-A2*B1;

        if(det!=0) { // det == 0 -> Lines are parallel
            double C1=A1*Ax+B1*Ay;                          
            double C2=A2*Cx + B2*Cy;

            double point_x=(B2*C1-B1*C2)/det;
            double point_y=(A1*C2-A2*C1)/det;

            if(IsPointInBoundingBox(Ax, Ay, Bx, By, point_x, point_y) == 1 && IsPointInBoundingBox(Cx, Cy, Dx, Dy, point_x, point_y) == 1)
            {
                intersects.push_back(std::array<double, 3>());
                int q = intersects.size()-1;
                intersects[q][0]=point_x;
                intersects[q][1]=point_y;
                intersects[q][2]=matrix[j][2];
            }   
        }
    }   
}

int IsPointInBoundingBox(double x1, double y1, double x2, double y2, double px, double py)
{
    if(min(x1, x2) <= px && px <= max(x1,x2) && min(y1,y2) <= py  && py <= max(y1,y2) )
    {
         return 1;
    }
    else
         return 0;
}

When I run the program, no intersections are written into the file. The only way to get intersections to the file is by modefying the IsPointInBoundingBox function. To get it to working I have to use this code:

if( (px+0.01) >= min(x1,x2) && (px-0.01) <= max(x1,x2) && 
        (py+0.01) >= min(y1,y2) && (py-0.01) <= max(y1,y2) )
{
    return 1;
}
else
    return 0;

My big problem is now that I have to use different inputs. And by adding the +-0.1 to my code I would have to calculate if the bounderies are to small, or could be smaller. But I don not get, why I lose all intersections, with my original function. I already calculated the intersections manually and always found a point in the set bounderies.

Use vector-math (note the gradient(slope) of a line might be infinite) — , Jun 22 '16 at 12:31
Do what you ask us to do: take 2 lines, ensure they are secant and manually compute the intersection point. Then in an interactive Python shell (IDLE or PyCharm or...) execute your algorythm. It should be enough to find where an error could be... — Serge Ballesta, Jun 22 '16 at 12:51
I'm not asking anyone to do my task. I already calculate the intersect points of my two vectors manually and always found the correct intersection points. But when I tried to convert my mathematical approach in code, I had the mentioned error. — user3794592, Jun 22 '16 at 12:55

score 1 · Accepted Answer · answered Jun 22 '16 at 12:34

1

Check for division by zero. AB_x, CD_x can be 0.

answered Jun 22 '16 at 12:34

prashkr

398
2
10

I see that, but how can I avoid that. I mean if AB_x or CD_x are 0 I just can't add some number to it, so I avoid a division by zero – user3794592 Jun 22 '16 at 12:40
You might want to look at this [how-do-you-detect-where-two-line-segments-intersect](http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect) – prashkr Jun 22 '16 at 12:50
Another good explanation: [Line Intersection](https://www.topcoder.com/community/data-science/data-science-tutorials/geometry-concepts-line-intersection-and-its-applications/) – prashkr Jun 22 '16 at 12:55
It means the lines are parallel. – Jun 22 '16 at 13:30

Calculation of intersection points of two lines returns -1.#IND in CSV-file

1 Answers1