write a c program to check line segment intersection. we have already discussed the line segment intersection theory on our previous post  http://wikistack.com/line-segment-intersection/. Now we know how to make a generic line equation ax+ by = c from given line segment.

To check whether two line segments intersect or not

  • From given line segment , extract generic line equation A1x + B1y = C1, where A1,B and C1 define the line. How to get A1,B1 and C1 from given line segment , has been discussed at http://wikistack.com/line-segment-intersection/
  • If the two lines are not parallel , they will intersect somewhere else. Say it is (x,y).
  • It is obvious that intersection point would be common for both the lines.
  • Check whether intersection point (x,y) is on both the line segments, or not.

c program to check line segment intersection

cpp program to check line segment intersection

Let us assume we have been given two line segment AB (0,2 2,0) and CD (0,0,2,2). Another input is EF(1,-3,2,-2)  and GH(3,-1,4,-2). The below program will check whether AB and CD intersect or not and same as for EF and GH.

#include<iostream>
#include<algorithm>
using namespace std;

// data structure for storing line

typedef struct point_ {
	double x;
	double y;
} point;

// data structure for line

typedef struct line_ {
	point p;
	point q;
} line;

bool doIntersect(line A, line B);
bool inRange(double x, long double y, line AB, line CD);

int main() {
	// store line segment AB
	line AB;
	AB.p.x = 0;
	AB.p.y = 2;
	AB.q.x = 2;
	AB.q.y = 0;

	// store line segment CD
	line CD;
	CD.p.x = 0;
	CD.p.y = 0;
	CD.q.x = 2;
	CD.q.y = 2;

	if (doIntersect(AB, CD))
		printf("AB and CD intersect \n");
	else
		printf("AB and CD donot intersect \n");

	// store line segment EF
	line EF;
	EF.p.x = 1;
	EF.p.y = -3;
	EF.q.x = 2;
	EF.q.y = -2;

	// store line segment GH
	line GH;
	GH.p.x = 3;
	GH.p.y = -1;
	GH.q.x = 4;
	GH.q.y = -2;

	if (doIntersect(EF, GH))
		printf("EF and GH intersect \n");
	else
		printf("EF and GH donot intersect \n");

	return 0;
}

bool doIntersect(line AB, line CD) {
	int x;
	int y;
	double A1 = AB.q.y - AB.p.y; // y2 -y1
	double B1 = AB.p.x - AB.q.x; // x2 -x1
	double C1 = A1 * AB.p.x + B1 * AB.p.y; //Ax1 + By1

	double A2 = CD.q.y - CD.p.y; // y2 -y1
	double B2 = CD.p.x - CD.q.x; // x2 -x1
	double C2 = A2 * CD.p.x + B2 * CD.p.y; //Ax1 + By1

	// detterminant
	double det = A1 * B2 - A2 * B1;
	if (det == 0) {
		printf("line segments are parallel \n");
		return false;
	} else { // find intersection point

		x = (B2 * C1 - B1 * C2) / det;
		y = (A1 * C2 - A2 * C1) / det;
		// check whether x and y lies on AB and CD both

		if (inRange(x, y, AB, CD))
			return true;
		else
			return false;
	}

	return false;
}

bool inRange(double x, long double y, line AB, line CD) {
	if (min(AB.p.x, AB.q.x) <= x <= max(AB.p.x, AB.q.x) && min(AB.p.y, AB.q.y)
			<= y <= max(AB.p.y, AB.q.y) && min(CD.p.x, CD.q.x) <= x <= max(
			CD.p.x, CD.q.x) && min(CD.p.y, CD.q.y) <= y <= max(CD.p.y, CD.q.y))
		return true;
	else
		return false;
}

 



Related Contents to follow