# Line Segment Intersection

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

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/mathematics/line-segment-intersection.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.