SweepLineTest.cpp File Reference

#include "modules/bentleyottmann/include/SweepLine.h"
#include "modules/bentleyottmann/include/EventQueueInterface.h"
#include "modules/bentleyottmann/include/Point.h"
#include "tests/Test.h"
#include <iterator>

Go to the source code of this file.

Classes
struct	bentleyottmann::SweepLineTestingPeer

Namespaces
namespace	bentleyottmann

Typedefs
using	TP = SweepLineTestingPeer

Functions
	DEF_TEST (BO_SweepLineSearch, reporter)
	DEF_TEST (BO_SweepLineInsert, reporter)

Typedef Documentation

TP

using TP = SweepLineTestingPeer

Definition at line 36 of file SweepLineTest.cpp.

Function Documentation

DEF_TEST() [1/2]

DEF_TEST	(	BO_SweepLineInsert	,
		reporter
	)

Definition at line 96 of file SweepLineTest.cpp.

                                       {
    {
        SweepLine sweepLine;
        TP tp{&sweepLine};
        tp.verifySweepLine(0);
    }
    { // Handle insert
        SweepLine sweepLine;
        TP tp{&sweepLine};
 
        class FailIfEventQueueAdd : public EventQueueInterface {
        public:
            void addCrossing(Point crossingPoint, const Segment& s0, const Segment& s1) override {
                SK_ABORT("There should be no crossings.");
            }
        } eventQueue;
        InsertionSegmentSet insertions;
        Segment s = {{0, -100}, {0, 100}};
 
        insertions.insert(s);
 
        tp.verifySweepLine(-99);
 
        sweepLine.handleInsertionsAndCheckForNewCrossings(
                Point{0, -100}, insertions, &eventQueue);
        REPORTER_ASSERT(reporter, tp.size() == 3);
 
        tp.verifySweepLine(-99);
    }
 
    { // Handle 3 segments where removing middle segment introduces crossing
        SweepLine sweepLine;
        TP tp{&sweepLine};
 
        Point p0 = {-100, -100},
              p1 = { 100,  100},
              p2 = { 100, -100},
              p3 = {-100,  100},
              p4 = {   0, -100},
              p5 = {   0,  -50};
        Segment s0 = {p0, p1},
                s1 = {p2, p3},
                s2 = {p4, p5};
 
        class CollectCrossings : public EventQueueInterface {
        public:
            void addCrossing(Point crossingPoint, const Segment& s0, const Segment& s1) override {
                fCrossing.push_back({s0, s1, crossingPoint});
            }
            std::vector<Crossing> fCrossing;
        } eventQueue;
 
        { // Simulate handling Upper s0
            InsertionSegmentSet insertions;
            insertions.insert(s0);
            tp.verifySweepLine(-99);
            sweepLine.handleInsertionsAndCheckForNewCrossings(
                    p0, insertions, &eventQueue);
            REPORTER_ASSERT(reporter, tp.size() == 3);
            REPORTER_ASSERT(reporter, eventQueue.fCrossing.size() == 0);
            tp.verifySweepLine(-99);
        }
        { // Simulate handling Upper s2
            InsertionSegmentSet insertions;
            insertions.insert(s2);
            tp.verifySweepLine(-99);
            sweepLine.handleInsertionsAndCheckForNewCrossings(
                    p4, insertions, &eventQueue);
            REPORTER_ASSERT(reporter, tp.size() == 4);
            REPORTER_ASSERT(reporter, eventQueue.fCrossing.size() == 0);
            tp.verifySweepLine(-99);
        }
        { // Simulate handling Upper s1
            InsertionSegmentSet insertions;
            insertions.insert(s1);
            tp.verifySweepLine(-99);
            sweepLine.handleInsertionsAndCheckForNewCrossings(
                    p2, insertions, &eventQueue);
            REPORTER_ASSERT(reporter, tp.size() == 5);
            REPORTER_ASSERT(reporter, eventQueue.fCrossing.size() == 0);
            tp.verifySweepLine(-99);
        }
        { // Simulate handling Lower s2 which introduces a crossing
            DeletionSegmentSet deletions;  // empty set because this will be a lower event
            InsertionSegmentSet insertions;
            tp.verifySweepLine(-51);
            sweepLine.handleDeletions(p5, deletions);
            REPORTER_ASSERT(reporter, tp.size() == 4);
            sweepLine.handleInsertionsAndCheckForNewCrossings(
                    p5, insertions, &eventQueue);
            REPORTER_ASSERT(reporter, eventQueue.fCrossing.size() == 1);
            tp.verifySweepLine(-51);
        }
        { // Handle crossing
            DeletionSegmentSet deletions{s0, s1};  // empty set because this will be a lower event
            InsertionSegmentSet insertions{s0, s1};
            tp.verifySweepLine(-1);  // Check above the crossing
            sweepLine.handleDeletions({0,0}, deletions);
            sweepLine.handleInsertionsAndCheckForNewCrossings(
                    {0,0}, insertions, &eventQueue);
            REPORTER_ASSERT(reporter, tp.size() == 4);
            REPORTER_ASSERT(reporter, eventQueue.fCrossing.size() == 1);
            tp.verifySweepLine(1);  // Make sure things are correct after deletion
        }
        { // Handle deletion s1
            DeletionSegmentSet deletions{};  // empty set because this will be a lower event
            InsertionSegmentSet insertions{};
            tp.verifySweepLine(99);  // Check above the crossing
            sweepLine.handleDeletions(p3, deletions);
            sweepLine.handleInsertionsAndCheckForNewCrossings(
                    p3, insertions, &eventQueue);
            REPORTER_ASSERT(reporter, tp.size() == 3);
            REPORTER_ASSERT(reporter, eventQueue.fCrossing.size() == 1);
            tp.verifySweepLine(99);  // Make sure sentinels are correct.
        }
        { // Handle deletion s0
            DeletionSegmentSet deletions{};  // empty set because this will be a lower event
            InsertionSegmentSet insertions{};
            tp.verifySweepLine(99);  // Check above the crossing
            sweepLine.handleDeletions(p1, deletions);
            sweepLine.handleInsertionsAndCheckForNewCrossings(
                    p1, insertions, &eventQueue);
            REPORTER_ASSERT(reporter, tp.size() == 2);
            REPORTER_ASSERT(reporter, eventQueue.fCrossing.size() == 1);
            tp.verifySweepLine(99);  // Make sure sentinels are correct.
        }
    }
}

DEF_TEST() [2/2]

DEF_TEST	(	BO_SweepLineSearch	,
		reporter
	)

Definition at line 38 of file SweepLineTest.cpp.

                                       {
    {
        SweepLine sweepLine;
        TP tp{&sweepLine};
 
        Point p0 = {-100, -100},
              p1 = { 100,  100},
              p2 = { 100, -100},
              p3 = {-100,  100};
        Segment s0 = {p0, p1},
                s1 = {p2, p3};
        tp.insertSegment(1, s0);
        tp.insertSegment(2, s1);
 
        auto& sl = tp.sweepLine();
 
        const Point crossing = {0, 0};
 
        const auto l = std::lower_bound(sl.begin(), sl.end(), crossing,
                                        rounded_point_less_than_segment_in_x_lower);
 
        const auto r = std::lower_bound(l, sl.end(), crossing,
                                        rounded_point_less_than_segment_in_x_upper);
 
        // Remember that the index is off by 1 because of the left sentinel.
        REPORTER_ASSERT(reporter, std::distance(sl.begin(), l) == 1);
        REPORTER_ASSERT(reporter, std::distance(sl.begin(), r) == 3);
    }
    {
        SweepLine sweepLine;
        TP tp{&sweepLine};
 
        // No longer cross at {0, 0}, but still round to {0, 0}.
        Point p0 = {-100, -100},
              p1 = {  99,  100},
              p2 = { 100, -100},
              p3 = {-101,  100};
        Segment s0 = {p0, p1},
                s1 = {p2, p3};
        tp.insertSegment(1, s0);
        tp.insertSegment(2, s1);
 
        auto& sl = tp.sweepLine();
 
        const Point crossing = {0, 0};
 
        const auto l = std::lower_bound(sl.begin(), sl.end(), crossing,
                                        rounded_point_less_than_segment_in_x_lower);
 
        const auto r = std::lower_bound(l, sl.end(), crossing,
                                        rounded_point_less_than_segment_in_x_upper);
 
        // Remember that the index is off by 1 because of the left sentinel.
        REPORTER_ASSERT(reporter, std::distance(sl.begin(), l) == 1);
        REPORTER_ASSERT(reporter, std::distance(sl.begin(), r) == 3);
    }
}