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

### 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;
}
```