# Line Segment Intersection

Idea:
- Find the intersection, if it exists at all.
- There is an intersection between two line segments if the point of intersection is within the bounding box for both lines.
- For edge cases, I make sure to check every permutational type of line (line, hori, vert)

struct Point {
double x, y;
};

enum type {
hori, vert, line
};

struct Line {
double slope, y_int;
type type;

static void print_info(Line &l)
{
cout << setw(9) << "Slope: " << l.slope << endl;
cout << setw(9) << "y_int: " << l.y_int << endl;
cout << setw(9) << "Type: " << l.type << endl << endl;
}

static void def_type(const Point &one, const Point &one1, Line &l)
{
double delta_y = (one1.y - one.y);
double delta_x = (one1.x - one.x);

if      (delta_y == 0) l.type = hori;
else if (delta_x == 0) l.type = vert;
else                   l.type = line;
}
};

bool isInBoundingBox(const Point &a, const Point &a1,
const Point &b, const Point &b1)
{
return a.x <= b.x
&& a1.x >= b.x
&& a.y <= b1.y
&& a1.y >= b.y;
}

bool point_in_boundingbox(const Point &p,
const Point &b1, const Point &b2)
{
double epsilon = .0001;
double one = max(b1.x, b2.x) + epsilon;
double two = min(b1.x, b2.x) - epsilon;
double three = max(b1.y, b2.y) + epsilon;
double four = min(b1.y, b2.y) - epsilon;

bool one1 = p.x <= one;
bool two1 = p.x >= two ;
bool three1 = p.y <= three;
bool four1 = p.y >= four;

return ((p.x <= max(b1.x, b2.x) + epsilon) && (p.x >= min(b1.x, b2.x) - epsilon)
&& (p.y <= max(b1.y, b2.y) + epsilon) && (p.y >= min(b1.y, b2.y) - epsilon));
}

bool intersection(const Point &one, const Point &one1,
const Point &two, const Point &two1) {

Line line1, line2;

// m = y2-y1/x2-x1
line1.slope = (one1.y - one.y) / (one1.x - one.x);
line2.slope = (two1.y - two.y) / (two1.x - two.x);

line1.def_type(one, one1, line1);
line2.def_type(two, two1, line2);

// y = mx + (-mx_1 + y_1)
if (line1.type != vert) line1.y_int = (-line1.slope * one.x) + one.y;
if (line2.type != vert) line2.y_int = (-line2.slope * two.x) + two.y;

line1.print_info(line1);
line2.print_info(line2);

Point intersection;

if (line1.type == line && line2.type == line) {
// m1x_1 + b_1 = m1x_2 + b_2
// 0 = (m2x_2 - m1x_1) + (b_2 - b_1)
// 0 = (m2 - m1)x + (b_2 - b1)
intersection.x = (-(line2.y_int - line1.y_int)) / (line2.slope - line1.slope);
intersection.y = (line1.slope * intersection.x) + line1.y_int;

// colinear
if (line1.slope == line2.slope &&
line1.y_int == line2.y_int && isInBoundingBox(one, one1, two, two1)) return true;
else if (line1.slope == line2.slope && line1.y_int == line2.y_int && !isInBoundingBox(one, one1, two, two1)) return false;
}
else if ((line1.type == hori && line2.type == line)
|| (line1.type == hori && line2.type == line)) {
// y = mx + b
// x = (y - b) / m
if (line2.type == line) {
intersection.x = (line1.y_int - line2.y_int) / line2.slope;
intersection.y = line1.y_int;
}
else {
intersection.x = (line2.y_int - line1.y_int) / line1.slope;
intersection.y = line2.y_int;
}
}
else if ((line1.type == hori && line2.type == vert)
|| (line1.type == vert && line2.type == hori)) {
if (line1.type == hori) {
intersection.x = two.x;
intersection.y = line1.y_int;
}
else {
intersection.x = one.x;
intersection.y = line2.y_int;
}
}
else if ((line1.type == vert && line2.type == line)
|| (line1.type == line && line2.type == vert)) {
if (line2.type == line) {
// y = mx + b
intersection.x = one.x;
intersection.y = (line2.slope * one.x) + line2.y_int;
}
else {
intersection.x = two.x;
intersection.y = (line1.slope * two.x) + line1.y_int;
}
}
else if ((line1.type == hori && line2.type == hori)
|| (line1.type == vert && line2.type == vert)) {
return (isInBoundingBox(one, one1, two, two1));
}

return ( (point_in_boundingbox(intersection, one, one1))
&& (point_in_boundingbox(intersection, two, two1)) );
}

void test_intersection(const Point &one, const Point &one1,
const Point &two, const Point &two1,
int test_num) {
if (intersection(one, one1, two, two1))
cout << "Test Case " << setw(2) << test_num << " - true" << endl;
else cout << "Test Case " << setw(2) << test_num << " - false" << endl;
}

int main() {
// Testcase T1 => (0, 5.5)(0,-5.5) - (7, 0)(-7, 0)
Point point1, point2, point3, point4;
point1.x = 0;
point1.y = 5.5;

point2.x = 0;
point2.y = -5.5;

point3.x = 7;
point3.y = 0;

point4.x = -7;
point4.y = 0;
test_intersection(point1, point2, point3, point4, 1);

// Testcase T2 => (0, 0), (10, 10) - (5, 5)(10, 2)
point1.x = 0;
point1.y = 0;

point2.x = 10;
point2.y = 10;

point3.x = 5;
point3.y = 5;

point4.x = 10;
point4.y = 2;
test_intersection(point1, point2, point3, point4, 2);

// Testcase T3 => (0, 7)(0, 0) - (0, 3.5)(6, 3.5)
point1.x = 0;
point1.y = 7;

point2.x = 0;
point2.y = 0;

point3.x = 0;
point3.y = 3.5;

point4.x = 6;
point4.y = 3.5;
test_intersection(point1, point2, point3, point4, 3);

// Testcase T4 => (10, 9.87)(10, 1.5) - (10, 3.3)(5, 3.3)
point1.x = 10;
point1.y = 9.87;

point2.x = 10;
point2.y = 1.5;

point3.x = 10;
point3.y = 3.3;

point4.x = 5;
point4.y = 3.3;
test_intersection(point1, point2, point3, point4, 4);

// Testcase T5 => (2.75, 2.75)(13.7, 13.7) - (10.63, 10.63)(19.84, 19.84)
point1.x = 2.75;
point1.y = 2.75;

point2.x = 13.7;
point2.y = 13.7;

point3.x = 10.63;
point3.y = 10.63;

point4.x = 19.84;
point4.y = 19.84;
test_intersection(point1, point2, point3, point4, 5);

// Testcase T6  => (3, 4)(4, 5) - (3, 4)(4, 5)
point1.x = 3;
point1.y = 4;

point2.x = 4;
point2.y = 5;

point3.x = 3;
point3.y = 4;

point4.x = 4;
point4.y = 5;
test_intersection(point1, point2, point3, point4, 6);

// Testcase F1 => (4, 6)(10, 9) - (4, -2)(8, 0)
point1.x = 4;
point1.y = 6;

point2.x = 10;
point2.y = 9;

point3.x = 4;
point3.y = -2;

point4.x = 8;
point4.y = 0;
test_intersection(point1, point2, point3, point4, 7);

// Testcase F2 =>(-3.3, 2.6) (-2, 0) - (0, -4)(2, -8)
point1.x = -3.3;
point1.y = 2.6;

point2.x = -2;
point2.y = 0;

point3.x = 0;
point3.y = -4;

point4.x = 2;
point4.y = -8;
test_intersection(point1, point2, point3, point4, 8);

// Testcase F3 =>(-4,4, 9.86)(-4.4, 1.35) - (6.21, -5.1)(6.21, 10.51)
point1.x = -4.4;
point1.y = 9.86;

point2.x = -4.4;
point2.y = 1.35;

point3.x = 6.21;
point3.y = -5.1;

point4.x = 6.21;
point4.y = 10.51;
test_intersection(point1, point2, point3, point4, 9);

// Testcase F4 =>(0, 0)(0, 5) - (10, 18)(15, 18)
point1.x = 0;
point1.y = 0;

point2.x = 0;
point2.y = 5;

point3.x = 10;
point3.y = 18;

point4.x = 15;
point4.y = 18;
test_intersection(point1, point2, point3, point4, 10);

//Testcase F5 => (-7.7, -7.7)(0.5, 0.5) - (5, 5) (6.15, 6.15)
point1.x = -7.7;
point1.y = -7.7;

point2.x = 0.5;
point2.y = 0.5;

point3.x = 5;
point3.y = 5;

point4.x = 6.15;
point4.y = 6.15;
test_intersection(point1, point2, point3, point4, 11);

//Testcase F6 =>(1.1, 1.1)(2.75, 2.75) - (0, 10)(10, 0)
point1.x = -1.1;
point1.y = -1.1;

point2.x = 2.75;
point2.y = 2.75;

point3.x = 0;
point3.y = 10;

point4.x = 10;
point4.y = 0;
test_intersection(point1, point2, point3, point4, 12);

// Testcase F7=> (2,2)(8,2) - (4, 5)(6, 5)
point1.x = 2;
point1.y = 2;

point2.x = 8;
point2.y = 2;

point3.x = 4;
point3.y = 5;

point4.x = 6;
point4.y = 5;
test_intersection(point1, point2, point3, point4, 13);

//Testcase F8=>(0, 8)(10, 0) - (4, 2)(4, 4)
point1.x = 0;
point1.y = 8;

point2.x = 10;
point2.y = 0;

point3.x = 4;
point3.y = 2;

point4.x = 4;
point4.y = 4;
test_intersection(point1, point2, point3, point4, 14);
}

Last updated