modules/bentleyottmann/tests/SegmentTest.cpp

// Copyright 2023 Google LLC
// Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

#include "modules/bentleyottmann/include/Segment.h"
#include "tests/Test.h"

using namespace bentleyottmann;

DEF_TEST(BO_SegmentBasic, reporter) {
    {
        Segment s = {{0, 0}, {1, 1}};
        REPORTER_ASSERT(reporter, s.upper() == s.p0);
        REPORTER_ASSERT(reporter, s.lower() == s.p1);
    }

    {
        Segment s = {{1, 0}, {0, 1}};
        REPORTER_ASSERT(reporter, s.upper() == s.p0);
        REPORTER_ASSERT(reporter, s.lower() == s.p1);
    }

    {
        Segment s = {{1, 1}, {0, 0}};
        REPORTER_ASSERT(reporter, s.upper() == s.p1);
        REPORTER_ASSERT(reporter, s.lower() == s.p0);
    }

    {
        Segment s = {{0, 1}, {1, 0}};
        REPORTER_ASSERT(reporter, s.upper() == s.p1);
        REPORTER_ASSERT(reporter, s.lower() == s.p0);
    }
}

static Segment swap_ends(const Segment& s) {
    return {s.p1, s.p0};
}

DEF_TEST(BO_no_intersection_bounding_box, reporter) {
    Segment interesting[] = {{Point::Smallest(),  Point::Smallest()+ Point{10, 5}},
                             {Point::Largest(), Point::Largest() - Point{10, 5}},
                             {{-10, -5}, {10, 5}}};

    // Intersection
    for (auto& s0 : interesting) {
        auto [l, t, r, b] = s0.bounds();

        // Points in the interior of interesting rectangles
        for(Point p : {Point {l + 1, t + 1},
                       Point {r - 1, t + 1},
                       Point {r - 1, b - 1},
                       Point {l + 1, b - 1}}) {
            Segment s1 = {p, {0, 0}};
            REPORTER_ASSERT(reporter, !no_intersection_by_bounding_box(s0, s1));
            REPORTER_ASSERT(reporter, !no_intersection_by_bounding_box(s1, s0));
            REPORTER_ASSERT(reporter,
            !no_intersection_by_bounding_box(swap_ends(s0), swap_ends(s1)));
            REPORTER_ASSERT(reporter,
            !no_intersection_by_bounding_box(swap_ends(s0), swap_ends(s1)));
        }
    }

    int32_t small = Point::Smallest().x,
            big = Point::Largest().x;

    // No Intersection
    for (auto& s0 : interesting) {
        auto [l, t, r, b] = s0.bounds();

        Segment outside[] = {{{r, t}, {big, b}},
                             {{r, b}, {big, big}},
                             {{l, b}, {r, big}},
                             {{l, b}, {small, big}},
                             {{l, t}, {small, b}},
                             {{l, t}, {small, small}},
                             {{l, t}, {r, small}},
                             {{r, t}, {small, small}}};

        for (auto& s1 : outside) {
            REPORTER_ASSERT(reporter, no_intersection_by_bounding_box(s0, s1));
            REPORTER_ASSERT(reporter, no_intersection_by_bounding_box(s1, s0));
            REPORTER_ASSERT(reporter,
                    no_intersection_by_bounding_box(swap_ends(s0), swap_ends(s1)));
            REPORTER_ASSERT(reporter,
                    no_intersection_by_bounding_box(swap_ends(s0), swap_ends(s1)));
        }
    }
}

DEF_TEST(BO_intersectBasic, reporter) {

    auto checkIntersection = [reporter](Segment s0, Segment s1, Point expected) {
        {
            auto answer = intersect(s0, s1);
            REPORTER_ASSERT(reporter, answer.has_value());
            REPORTER_ASSERT(reporter, answer.value() == expected);
        }
        {
            auto answer = intersect(s1, s0);
            REPORTER_ASSERT(reporter, answer.has_value());
            REPORTER_ASSERT(reporter, answer.value() == expected);
        }
        {
            auto answer = intersect(swap_ends(s0), swap_ends(s1));
            REPORTER_ASSERT(reporter, answer.has_value());
            REPORTER_ASSERT(reporter, answer.value() == expected);
        }
        {
            auto answer = intersect(swap_ends(s1), swap_ends(s0));
            REPORTER_ASSERT(reporter, answer.has_value());
            REPORTER_ASSERT(reporter, answer.value() == expected);
        }
    };

    {
        Segment s0 = {{-1, 0}, {1,  0}},
                s1 = {{ 0, 1}, {0, -1}};

        checkIntersection(s0, s1, Point{0, 0});
    }
    {
        Segment s0 = {{-1, 0}, {5,  0}},
                s1 = {{ 0, 1}, {0, -1}};

        checkIntersection(s0, s1, Point{0, 0});
    }

    {
        Segment s0 = {{5, 0}, {-1,  0}},
                s1 = {{ 0, -1}, {0, 1}};

        checkIntersection(s0, s1, Point{0, 0});
    }

    {
        Segment s0 = {{-5, -5}, {5, 5}},
                s1 = {{-5, 5}, {5, -5}};

        checkIntersection(s0, s1, Point{0, 0});
    }

    // Test very close segments (x0, 0) -> (x1, 1) & (x2, 0) -> (x3, 1)
    for (int32_t x0 = -10; x0 <= 10; x0++) {
        for (int32_t x1 = -10; x1 <= 10; x1++) {
            for (int32_t x2 = -10; x2 <= 10; x2++) {
                for (int32_t x3 = -10; x3 <= 10; x3++) {
                    Point P0 = {x0, 0},
                          P1 = {x1, 1},
                          P2 = {x2, 0},
                          P3 = {x3, 1};
                    auto actual = intersect({P0, P1}, {P2, P3});
                    bool expected = (x0 < x2 && x3 < x1) || (x2 < x0 && x1 < x3);
                    REPORTER_ASSERT(reporter, actual.has_value() == expected);
                    if (actual) {
                        int32_t y = std::abs(x2 - x0) >= std::abs(x3 - x1);
                        REPORTER_ASSERT(reporter, actual.value().y == y);
                    }
                }
            }
        }
    }

    {
        Segment s0 = {{0, -100}, {0, -50}},
                s1 = {{100, -100}, {-100, 100}};  // goes through (0,0)
        auto answer = intersect(s0, s1);
        REPORTER_ASSERT(reporter, !answer.has_value());
        answer = intersect(s1, s0);
        REPORTER_ASSERT(reporter, !answer.has_value());
    }
    {
        Segment s0 = {{0, 100}, {0, 50}},
                s1 = {{100, -100}, {-100, 100}};  // goes through (0,0)
        auto answer = intersect(s0, s1);
        REPORTER_ASSERT(reporter, !answer.has_value());
        answer = intersect(s1, s0);
        REPORTER_ASSERT(reporter, !answer.has_value());
    }
}

DEF_TEST(BO_lessAtBasic, reporter) {
    { // Parallel lines
        Segment s0 = {{-1, 1}, {-1, -1}},
                s1 = {{1, 1}, {1, -1}};

        REPORTER_ASSERT(reporter, less_than_at(s0, s1, -1));
        REPORTER_ASSERT(reporter, !less_than_at(s1, s0, -1));
        REPORTER_ASSERT(reporter, less_than_at(s0, s1, 0));
        REPORTER_ASSERT(reporter, !less_than_at(s1, s0, 0));
        REPORTER_ASSERT(reporter, less_than_at(s0, s1, 1));
        REPORTER_ASSERT(reporter, !less_than_at(s1, s0, 1));
    }
    { // Crossed lines
        Segment s0 = {{-1, -1}, {1, 1}},
                s1 = {{1, -1}, {-1, 1}};

        REPORTER_ASSERT(reporter, less_than_at(s0, s1, -1));
        REPORTER_ASSERT(reporter, !less_than_at(s1, s0, -1));

        // When they are == neither is less.
        REPORTER_ASSERT(reporter, !less_than_at(s0, s1, 0));
        REPORTER_ASSERT(reporter, !less_than_at(s1, s0, 0));

        REPORTER_ASSERT(reporter, !less_than_at(s0, s1, 1));
        REPORTER_ASSERT(reporter, less_than_at(s1, s0, 1));
    }
    { // Near crossing
        Segment s0 = {{0, -100}, {0, 100}},
                s1 = {{-3, 98}, {3, 104}};

        REPORTER_ASSERT(reporter, !less_than_at(s0, s1, 98));
        REPORTER_ASSERT(reporter, less_than_at(s1, s0, 98));

        REPORTER_ASSERT(reporter, !less_than_at(s0, s1, 99));
        REPORTER_ASSERT(reporter, less_than_at(s1, s0, 99));

        REPORTER_ASSERT(reporter, !less_than_at(s0, s1, 100));
        REPORTER_ASSERT(reporter, less_than_at(s1, s0, 100));
    }
}

DEF_TEST(BO_compareSlopesBasic, reporter) {
    { // Both horizontal
        Segment s0 = {{-1, 1}, {0, 1}},
                s1 = {{-2, 1}, {1, 1}};
        REPORTER_ASSERT(reporter, compare_slopes(s0, s1) == 0);
        REPORTER_ASSERT(reporter, compare_slopes(s1, s0) == 0);
    }
    { // One horizontal
        Segment s0 = {{-1, 1}, {0, 0}},
                s1 = {{-2, 1}, {1, 1}};
        REPORTER_ASSERT(reporter, compare_slopes(s0, s1) == -1);
        REPORTER_ASSERT(reporter, compare_slopes(s1, s0) == 1);
    }
    { // One vertical
        Segment s0 = {{-1, 1}, {-1, 0}}, // Vertical
                s1 = {{-2, 1}, {-1, 0}},
                s2 = {{2, 1}, {-1, 0}};
        REPORTER_ASSERT(reporter, compare_slopes(s0, s1) == 1);
        REPORTER_ASSERT(reporter, compare_slopes(s1, s0) == -1);
        REPORTER_ASSERT(reporter, compare_slopes(s0, s2) == -1);
        REPORTER_ASSERT(reporter, compare_slopes(s2, s0) == 1);
    }

    { // Equal slope
        Segment s0 = {{-2, 1}, {0, 0}},
                s1 = {{-4, 2}, {0, 0}};
        REPORTER_ASSERT(reporter, compare_slopes(s0, s1) == 0);
        REPORTER_ASSERT(reporter, compare_slopes(s1, s0) == 0);
    }

    { // Equal slope
        Segment s0 = {{2, 1}, {0, 0}},
                s1 = {{4, 2}, {0, 0}};
        REPORTER_ASSERT(reporter, compare_slopes(s0, s1) == 0);
        REPORTER_ASSERT(reporter, compare_slopes(s1, s0) == 0);
    }

    {
        Segment s0 = {{-2, 1}, {0, 0}},
                s1 = {{4, 2}, {0, 0}};
        REPORTER_ASSERT(reporter, compare_slopes(s0, s1) == -1);
        REPORTER_ASSERT(reporter, compare_slopes(s1, s0) == 1);
    }

    {
        Segment s0 = {{-2, 1}, {0, 0}},
                s1 = {{-3, 1}, {0, 0}};
        REPORTER_ASSERT(reporter, compare_slopes(s0, s1) == 1);
        REPORTER_ASSERT(reporter, compare_slopes(s1, s0) == -1);
    }
}

DEF_TEST(BO_rounded_point_less_than_segment_in_x_lower, reporter) {
    { // Vertical segment
        Segment s = {{3, -50}, {3, 50}};
        REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_lower(s, {4, 7}));
        REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {3, 7}));
        REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {2, 7}));
    }
    { // Horizontal segment
        Segment s = {{-10, 3}, {10, 3}};
        REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_lower(s, {11, 3}));
        REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {10, 3}));
        REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {4, 3}));
        REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {-10, 3}));
        REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {-11, 3}));
    }
    { // Pass through {0, 0}
        Segment s = {{-100, -100}, {100, 100}};
        REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_lower(s, {1, 0}));
        REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {0, 0}));
        REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {-1, 0}));
    }
    { // Just left of {0, 0}, but still rounds to {0, 0}
        Segment s = {{-100, -100}, {199, 200}};
        REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_lower(s, {1, 0}));
        REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {0, 0}));
        REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {-1, 0}));
    }
    { // Just right of {0, 0}, but still rounds to {0, 0}
        Segment s = {{-100, -100}, {201, 200}};
        REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_lower(s, {1, 0}));
        REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {0, 0}));
        REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {-1, 0}));
    }
}

DEF_TEST(BO_rounded_point_less_than_segment_in_x_upper, reporter) {
    { // Vertical segment
        Segment s = {{3, -50}, {3, 50}};
        REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_upper(s, {4, 7}));
        REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_upper(s, {3, 7}));
        REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_upper(s, {2, 7}));
    }
    { // Horizontal segment
        Segment s = {{-10, 3}, {10, 3}};
        REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_upper(s, {11, 3}));
        REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_upper(s, {10, 3}));
        REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_upper(s, {4, 3}));
        REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_upper(s, {-10, 3}));
        REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_upper(s, {-11, 3}));
    }
    { // Pass through {0, 0}
        Segment s = {{-100, -100}, {100, 100}};
        REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_upper(s, {1, 0}));
        REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_upper(s, {0, 0}));
        REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_upper(s, {-1, 0}));
    }
    { // Just left of {0, 0}, but still rounds to {0, 0}
        Segment s = {{-100, -100}, {199, 200}};
        REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_upper(s, {1, 0}));
        REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_upper(s, {0, 0}));
        REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_upper(s, {-1, 0}));
    }
    { // Just right of {0, 0}, but still rounds to {0, 0}
        Segment s = {{-100, -100}, {201, 200}};
        REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_upper(s, {1, 0}));
        REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_upper(s, {0, 0}));
        REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_upper(s, {-1, 0}));
    }
}