intersection between two lines.

I have a problem in finding the intersection between two lines. The intersecting points are not correct.

Intersection points are computed by solving the equations of the lines. Before solving the equation, I construct the equation of line (of the form y = mx + c) and then use slide rule for solving the equations for finding the intersection points.

I know there are better methods for finding the intersection between two lines. But I want to know whether my approach can be used for finding the intersection and if so, where is my code going wrong.

Following is the code.

 text 

#include <GL/glut.h>
#include "stdlib.h"
#include <stdio.h>

typedef struct line
{
	float x1;
	float y1;
	float x2;
	float y2;
}Lines; 

Lines straight_line[2];

float* FormEquation(Lines lin)
{
	// y = mx + c; 
	// y- y1 = m(x-x1);
	// mx - y - mx1 + y1 = 0; 

	float* coeff = new float[3];
	float slope =  (lin.y2 - lin.y1)/(lin.x2 - lin.x1);
	coeff[0] = slope * lin.x1;
	coeff[1] = 1;
	coeff[2] = -slope * lin.x1 + lin.y1;
	return coeff;

}
bool  Test_Intersection(Lines line1,Lines line2,float* point)
{
	float* coeff1 = FormEquation(line1);
	float* coeff2 = FormEquation(line2);
	float d = (coeff2[0]*coeff1[1] - coeff1[0]*coeff2[1]);
	point[0] = (coeff1[2] * coeff2[0] - coeff2[2] * coeff1[0])/d;  
	if(d==0)
		return false;
	point[1] = (coeff1[2] - coeff1[1] * point[0]) / coeff1[0];
	return true;
}



void setpoints()
{

	straight_line[0].x1 =	1.0;
	straight_line[0].y1 =	2.0;
	straight_line[0].x2 =	7.0;
	straight_line[0].y2 =	6.0;

	straight_line[1].x1 =	2.0;
	straight_line[1].y1 =	3.0;
	straight_line[1].x2 =	6.0;
	straight_line[1].y2 =	5.0;

	float* point = new float[2];
	bool intersection = Test_Intersection(straight_line[0],straight_line[1],point);
	if(intersection)
	{
		printf("Line are intersecting = %f,%f
",point[0],point[1]);
	}
	else
	{
		printf("Not intersecting
");
	}

}



What’s coeff? y=mx + c has two coefficients, does it not? I’ve never heard of the slide rule unless you’re talking about a physical slide rule.

Your two lines…

y = m1x + c1
y = m2
x + c2

m1x + c1 = m2x + c2
(m1 - m2) * x = c2 - c1
x = (c2 - c1) / (m1 - m2)

This your final equation is this…

x = (c2 - c1) / (m1 - m2)

which makes sense since the line will be zero if they have the same slope (m1 and m2 are equal). Then you just plug x back in to one of the two slope-intercept line equations.

What’s your method trying to do? I’m not sure but in your FormEquation you set coeff[1] to be 1, so why do you even need it? Where does this third coefficient come from?

See this: http://en.wikipedia.org/wiki/Line-line_intersection

  • Do not try to make linear equation in form y = mx+c. Vertical lines cannot be expressed.
  • If you want to make line equation, always use general form Ax + By + C = 0 and then compute intersection.
  • You have memory leak in your code. new float[3] is never released

Given two points(x1,y1) and (x2,y2), how can we express the line joined by two points in AX+BY+C = 0 form.

Google “vector form of a line” for tips. The vector is the difference of the points, and just pick one of them for the base point.

I know there are tons of websites with various math info. An especially good one and my favorite, by far, for geometry, is Exploring Analytic Geometry with Mathematica. The entire text of that book is available online for free, in both pdf form and in HTML form.

Here’s the home page:
http://www.descarta2d.com/

Here’s the table of contents to the HTML version:
http://www.descarta2d.com/BookHTML/Table_of_Contents.html

Check out Chapter 5, Lines and Line Segments, for a complete discussion about your original question.