Algorithms/geometry/segments_intersection.cc at master · anikolaienko/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// Task 16.3 from Cracking Coding Interview

#include <limits>
#include <utility>
#include <algorithm>

#include "point.cc"
#include "line.cc"

namespace Algorithms {
    Point* segmentsIntersection(const Point& line1_a, const Point& line1_b,
        const Point& line2_a, const Point& line2_b) {
        Line l1(line1_a, line1_b);
        Line l2(line2_a, line2_b);

        if (l1.parallelTo(l2)) return nullptr; // TODO: not always

        Point* point = nullptr;
        if (l1.isVertical() || l2.isVertical()) {
            if (l2.isVertical()) std::swap(l1, l2);

            double x = l1.start.x;
            double y = l2.slope * x + l2.offset;

            point = new Point(x, y);
        } else {
            double x = (l2.offset - l1.offset) / (l1.slope - l2.slope);
            double y = l1.slope * x + l1.offset;

            point = new Point(x, y);
        }

        if (l1.withinBounds(*point) && l2.withinBounds(*point)) return point;

        return nullptr;
    }
}