1 // Copyright 2023 Google LLC
2 // Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
3
4 #include "modules/bentleyottmann/include/SweepLine.h"
5
6 #include "modules/bentleyottmann/include/EventQueueInterface.h"
7 #include "modules/bentleyottmann/include/Point.h"
8 #include "tests/Test.h"
9
10 #include <iterator>
11
12 using namespace bentleyottmann;
13
14 namespace bentleyottmann {
15 struct SweepLineTestingPeer {
SweepLineTestingPeerbentleyottmann::SweepLineTestingPeer16 SweepLineTestingPeer(SweepLine* sl) : fSL{sl} {}
verifySweepLinebentleyottmann::SweepLineTestingPeer17 void verifySweepLine(int32_t y) const {
18 fSL->verify(y);
19 }
insertSegmentbentleyottmann::SweepLineTestingPeer20 void insertSegment(int i, const Segment& s) {
21 auto& v = fSL->fSweepLine;
22 v.insert(v.begin() + i, s);
23 }
sizebentleyottmann::SweepLineTestingPeer24 size_t size() const {
25 return fSL->fSweepLine.size();
26 }
27
sweepLinebentleyottmann::SweepLineTestingPeer28 const std::vector<Segment>& sweepLine() const {
29 return fSL->fSweepLine;
30 }
31
32 SweepLine* const fSL;
33 };
34 } // namespace bentleyottmann
35
36 using TP = SweepLineTestingPeer;
37
DEF_TEST(BO_SweepLineSearch,reporter)38 DEF_TEST(BO_SweepLineSearch, reporter) {
39 {
40 SweepLine sweepLine;
41 TP tp{&sweepLine};
42
43 Point p0 = {-100, -100},
44 p1 = { 100, 100},
45 p2 = { 100, -100},
46 p3 = {-100, 100};
47 Segment s0 = {p0, p1},
48 s1 = {p2, p3};
49 tp.insertSegment(1, s0);
50 tp.insertSegment(2, s1);
51
52 auto& sl = tp.sweepLine();
53
54 const Point crossing = {0, 0};
55
56 const auto l = std::lower_bound(sl.begin(), sl.end(), crossing,
57 rounded_point_less_than_segment_in_x_lower);
58
59 const auto r = std::lower_bound(l, sl.end(), crossing,
60 rounded_point_less_than_segment_in_x_upper);
61
62 // Remember that the index is off by 1 because of the left sentinel.
63 REPORTER_ASSERT(reporter, std::distance(sl.begin(), l) == 1);
64 REPORTER_ASSERT(reporter, std::distance(sl.begin(), r) == 3);
65 }
66 {
67 SweepLine sweepLine;
68 TP tp{&sweepLine};
69
70 // No longer cross at {0, 0}, but still round to {0, 0}.
71 Point p0 = {-100, -100},
72 p1 = { 99, 100},
73 p2 = { 100, -100},
74 p3 = {-101, 100};
75 Segment s0 = {p0, p1},
76 s1 = {p2, p3};
77 tp.insertSegment(1, s0);
78 tp.insertSegment(2, s1);
79
80 auto& sl = tp.sweepLine();
81
82 const Point crossing = {0, 0};
83
84 const auto l = std::lower_bound(sl.begin(), sl.end(), crossing,
85 rounded_point_less_than_segment_in_x_lower);
86
87 const auto r = std::lower_bound(l, sl.end(), crossing,
88 rounded_point_less_than_segment_in_x_upper);
89
90 // Remember that the index is off by 1 because of the left sentinel.
91 REPORTER_ASSERT(reporter, std::distance(sl.begin(), l) == 1);
92 REPORTER_ASSERT(reporter, std::distance(sl.begin(), r) == 3);
93 }
94 }
95
DEF_TEST(BO_SweepLineInsert,reporter)96 DEF_TEST(BO_SweepLineInsert, reporter) {
97 {
98 SweepLine sweepLine;
99 TP tp{&sweepLine};
100 tp.verifySweepLine(0);
101 }
102 { // Handle insert
103 SweepLine sweepLine;
104 TP tp{&sweepLine};
105
106 class FailIfEventQueueAdd : public EventQueueInterface {
107 public:
108 void addCrossing(Point crossingPoint, const Segment& s0, const Segment& s1) override {
109 SK_ABORT("There should be no crossings.");
110 }
111 } eventQueue;
112 InsertionSegmentSet insertions;
113 Segment s = {{0, -100}, {0, 100}};
114
115 insertions.insert(s);
116
117 tp.verifySweepLine(-99);
118
119 sweepLine.handleInsertionsAndCheckForNewCrossings(
120 Point{0, -100}, insertions, &eventQueue);
121 REPORTER_ASSERT(reporter, tp.size() == 3);
122
123 tp.verifySweepLine(-99);
124 }
125
126 { // Handle 3 segments where removing middle segment introduces crossing
127 SweepLine sweepLine;
128 TP tp{&sweepLine};
129
130 Point p0 = {-100, -100},
131 p1 = { 100, 100},
132 p2 = { 100, -100},
133 p3 = {-100, 100},
134 p4 = { 0, -100},
135 p5 = { 0, -50};
136 Segment s0 = {p0, p1},
137 s1 = {p2, p3},
138 s2 = {p4, p5};
139
140 class CollectCrossings : public EventQueueInterface {
141 public:
142 void addCrossing(Point crossingPoint, const Segment& s0, const Segment& s1) override {
143 fCrossing.push_back({s0, s1, crossingPoint});
144 }
145 std::vector<Crossing> fCrossing;
146 } eventQueue;
147
148 { // Simulate handling Upper s0
149 InsertionSegmentSet insertions;
150 insertions.insert(s0);
151 tp.verifySweepLine(-99);
152 sweepLine.handleInsertionsAndCheckForNewCrossings(
153 p0, insertions, &eventQueue);
154 REPORTER_ASSERT(reporter, tp.size() == 3);
155 REPORTER_ASSERT(reporter, eventQueue.fCrossing.size() == 0);
156 tp.verifySweepLine(-99);
157 }
158 { // Simulate handling Upper s2
159 InsertionSegmentSet insertions;
160 insertions.insert(s2);
161 tp.verifySweepLine(-99);
162 sweepLine.handleInsertionsAndCheckForNewCrossings(
163 p4, insertions, &eventQueue);
164 REPORTER_ASSERT(reporter, tp.size() == 4);
165 REPORTER_ASSERT(reporter, eventQueue.fCrossing.size() == 0);
166 tp.verifySweepLine(-99);
167 }
168 { // Simulate handling Upper s1
169 InsertionSegmentSet insertions;
170 insertions.insert(s1);
171 tp.verifySweepLine(-99);
172 sweepLine.handleInsertionsAndCheckForNewCrossings(
173 p2, insertions, &eventQueue);
174 REPORTER_ASSERT(reporter, tp.size() == 5);
175 REPORTER_ASSERT(reporter, eventQueue.fCrossing.size() == 0);
176 tp.verifySweepLine(-99);
177 }
178 { // Simulate handling Lower s2 which introduces a crossing
179 DeletionSegmentSet deletions; // empty set because this will be a lower event
180 InsertionSegmentSet insertions;
181 tp.verifySweepLine(-51);
182 sweepLine.handleDeletions(p5, deletions);
183 REPORTER_ASSERT(reporter, tp.size() == 4);
184 sweepLine.handleInsertionsAndCheckForNewCrossings(
185 p5, insertions, &eventQueue);
186 REPORTER_ASSERT(reporter, eventQueue.fCrossing.size() == 1);
187 tp.verifySweepLine(-51);
188 }
189 { // Handle crossing
190 DeletionSegmentSet deletions{s0, s1}; // empty set because this will be a lower event
191 InsertionSegmentSet insertions{s0, s1};
192 tp.verifySweepLine(-1); // Check above the crossing
193 sweepLine.handleDeletions({0,0}, deletions);
194 sweepLine.handleInsertionsAndCheckForNewCrossings(
195 {0,0}, insertions, &eventQueue);
196 REPORTER_ASSERT(reporter, tp.size() == 4);
197 REPORTER_ASSERT(reporter, eventQueue.fCrossing.size() == 1);
198 tp.verifySweepLine(1); // Make sure things are correct after deletion
199 }
200 { // Handle deletion s1
201 DeletionSegmentSet deletions{}; // empty set because this will be a lower event
202 InsertionSegmentSet insertions{};
203 tp.verifySweepLine(99); // Check above the crossing
204 sweepLine.handleDeletions(p3, deletions);
205 sweepLine.handleInsertionsAndCheckForNewCrossings(
206 p3, insertions, &eventQueue);
207 REPORTER_ASSERT(reporter, tp.size() == 3);
208 REPORTER_ASSERT(reporter, eventQueue.fCrossing.size() == 1);
209 tp.verifySweepLine(99); // Make sure sentinels are correct.
210 }
211 { // Handle deletion s0
212 DeletionSegmentSet deletions{}; // empty set because this will be a lower event
213 InsertionSegmentSet insertions{};
214 tp.verifySweepLine(99); // Check above the crossing
215 sweepLine.handleDeletions(p1, deletions);
216 sweepLine.handleInsertionsAndCheckForNewCrossings(
217 p1, insertions, &eventQueue);
218 REPORTER_ASSERT(reporter, tp.size() == 2);
219 REPORTER_ASSERT(reporter, eventQueue.fCrossing.size() == 1);
220 tp.verifySweepLine(99); // Make sure sentinels are correct.
221 }
222 }
223 }
224