Line Segment Intersection

Check Out: https://martin-thoma.com/how-to-check-if-two-line-segments-intersect/

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);
}