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/Myers.h"
5
6 #include "src/base/SkRandom.h"
7 #include "tests/Test.h"
8
9 #include <chrono>
10 #include <cinttypes>
11 #include <cstdint>
12
13 namespace myers {
14 bool slope_s0_less_than_slope_s1(const Segment& s0, const Segment& s1);
15 bool segment_less_than_upper_to_insert(const Segment& segment, const Segment& to_insert);
16 bool s0_less_than_s1_at_y(const Segment& s0, const Segment& s1, int32_t y);
17 bool s0_intersects_s1(const Segment& s0, const Segment& s1);
18 } // namespace myers
19
20 using namespace myers;
21
operator ==(std::pair<const Point &,const Point &> l,std::tuple<Point,Point> r)22 static bool operator==(std::pair<const Point &, const Point &> l, std::tuple<Point, Point> r) {
23 return std::get<0>(l) == std::get<0>(r) && std::get<1>(l) == std::get<1>(r);
24 }
25
DEF_TEST(MFC_order_segment_points,r)26 DEF_TEST(MFC_order_segment_points, r) {
27 {
28 Point p0 = {0, 0},
29 p1 = {1, 1};
30 REPORTER_ASSERT(r, std::minmax(p0, p1) == std::make_tuple(p0, p1));
31 REPORTER_ASSERT(r, std::minmax(p1, p0) == std::make_tuple(p0, p1));
32 }
33 {
34 Point p0 = {0, 0},
35 p1 = {-1, 1};
36 REPORTER_ASSERT(r, std::minmax(p0, p1) == std::make_tuple(p0, p1));
37 REPORTER_ASSERT(r, std::minmax(p1, p0) == std::make_tuple(p0, p1));
38 }
39 {
40 Point p0 = {0, 0},
41 p1 = {0, 1};
42 REPORTER_ASSERT(r, std::minmax(p0, p1) == std::make_tuple(p0, p1));
43 REPORTER_ASSERT(r, std::minmax(p1, p0) == std::make_tuple(p0, p1));
44 }
45 }
46
DEF_TEST(MFC_segment_ctor,r)47 DEF_TEST(MFC_segment_ctor, r) {
48 {
49 Point p0 = {0, 0},
50 p1 = {1, 1};
51 Segment s = {p1, p0};
52 const auto [u, l] = s;
53 REPORTER_ASSERT(r, u == s.upper() && u == p0);
54 REPORTER_ASSERT(r, l == s.lower() && l == p1);
55 }
56
57 {
58 Point p0 = {0, 0},
59 p1 = {0, 1};
60 Segment s = {p1, p0};
61 const auto [u, l] = s;
62 REPORTER_ASSERT(r, u == s.upper() && u == p0);
63 REPORTER_ASSERT(r, l == s.lower() && l == p1);
64 }
65 }
66
DEF_TEST(MFC_slope_less_than,r)67 DEF_TEST(MFC_slope_less_than, r) {
68 {
69 Segment s0 = {{0, 0}, {1, 1}},
70 s1 = {{0, 0}, {-1, 1}};
71 REPORTER_ASSERT(r, !slope_s0_less_than_slope_s1(s0, s1));
72 REPORTER_ASSERT(r, slope_s0_less_than_slope_s1(s1, s0));
73 REPORTER_ASSERT(r, !slope_s0_less_than_slope_s1(s0, s0));
74 }
75 {
76 Segment s = {{0, 0}, {0,1}};
77 REPORTER_ASSERT(r, !slope_s0_less_than_slope_s1(s, s));
78 }
79 { // Check slopes for horizontals.
80 Segment s0 = {{-2, 0}, {1, 0}},
81 s1 = {{-1, 0}, {2, 0}};
82 REPORTER_ASSERT(r, !slope_s0_less_than_slope_s1(s0, s1));
83 REPORTER_ASSERT(r, !slope_s0_less_than_slope_s1(s1, s0));
84 }
85 { // Check slopes for horizontals.
86 Segment s0 = {{-2, 0}, {1, 0}},
87 s1 = {{0, 0}, {1, 1}};
88 REPORTER_ASSERT(r, !slope_s0_less_than_slope_s1(s0, s1));
89 REPORTER_ASSERT(r, slope_s0_less_than_slope_s1(s1, s0));
90 }
91 }
92
DEF_TEST(MFC_segment_less_than_upper_to_insert,r)93 DEF_TEST(MFC_segment_less_than_upper_to_insert, r) {
94 Segment s0 = {{-10, -10}, {10, 10}},
95 s1 = {{10, -10}, {-10, 10}},
96 to_insert = {{0, 0}, {0, 3}};
97
98 // Above y = 0, the sweepLine is {s0, s1}, but at y=0 s1 and s0 swap because of their slopes.
99 std::vector<Segment> sweepLine = {s1, s0};
100
101 auto insertionPoint = std::lower_bound(sweepLine.begin(), sweepLine.end(), to_insert,
102 segment_less_than_upper_to_insert);
103
104 // The insertion point is between s1 and s0.
105 REPORTER_ASSERT(r, *insertionPoint == s0);
106 REPORTER_ASSERT(r, *(insertionPoint-1) == s1);
107 }
108
DEF_TEST(MFC_less_than_at_y,r)109 DEF_TEST(MFC_less_than_at_y, r) {
110 {
111 Segment s0 = {{0, 0}, {2, 2}},
112 s1 = {{0, 0}, {-2, 2}};
113 REPORTER_ASSERT(r, !s0_less_than_s1_at_y(s0, s1, 1));
114 REPORTER_ASSERT(r, s0_less_than_s1_at_y(s1, s0, 1));
115 }
116 { // cross at 0 use slope to break tie.
117 Segment s0 = {{-2, -2}, {2, 2}},
118 s1 = {{2, -2}, {-2, 2}};
119 REPORTER_ASSERT(r, s0_less_than_s1_at_y(s0, s1, -1));
120 REPORTER_ASSERT(r, !s0_less_than_s1_at_y(s1, s0, -1));
121 REPORTER_ASSERT(r, !s0_less_than_s1_at_y(s0, s1, 0));
122 REPORTER_ASSERT(r, s0_less_than_s1_at_y(s1, s0, 0));
123 REPORTER_ASSERT(r, !s0_less_than_s1_at_y(s0, s1, 1));
124 REPORTER_ASSERT(r, s0_less_than_s1_at_y(s1, s0, 1));
125 }
126 {
127 Segment s0 = {{-2, -100}, {-2, 89}},
128 s1 = {{6, -70}, {-2, 72}};
129
130 REPORTER_ASSERT(r, !s0_less_than_s1_at_y(s0, s1, 72));
131 }
132 }
133
swap_ends(const Segment & s)134 static Segment swap_ends(const Segment& s) {
135 return {s.lower(), s.upper()};
136 }
137
DEF_TEST(MFC_has_inner_intersection,r)138 DEF_TEST(MFC_has_inner_intersection, r) {
139 auto checkIntersection = [&](Segment s0, Segment s1) {
140 REPORTER_ASSERT(r, s0_intersects_s1(s0, s1));
141 REPORTER_ASSERT(r, s0_intersects_s1(s1, s0));
142 REPORTER_ASSERT(r, s0_intersects_s1(swap_ends(s0), swap_ends(s1)));
143 REPORTER_ASSERT(r, s0_intersects_s1(swap_ends(s1), swap_ends(s0)));
144 };
145
146 {
147 Segment s0 = {{-1, 0}, {1, 0}},
148 s1 = {{ 0, 1}, {0, -1}};
149
150 checkIntersection(s0, s1);
151 }
152 {
153 Segment s0 = {{-1, 0}, {5, 0}},
154 s1 = {{ 0, 1}, {0, -1}};
155
156 checkIntersection(s0, s1);
157 }
158
159 {
160 Segment s0 = {{5, 0}, {-1, 0}},
161 s1 = {{ 0, -1}, {0, 1}};
162
163 checkIntersection(s0, s1);
164 }
165
166 {
167 Segment s0 = {{-5, -5}, {5, 5}},
168 s1 = {{-5, 5}, {5, -5}};
169
170 checkIntersection(s0, s1);
171 }
172
173 // Test very close segments (x0, 0) -> (x1, 1) & (x2, 0) -> (x3, 1)
174 for (int32_t x0 = -10; x0 <= 10; x0++) {
175 for (int32_t x1 = -10; x1 <= 10; x1++) {
176 for (int32_t x2 = -10; x2 <= 10; x2++) {
177 for (int32_t x3 = -10; x3 <= 10; x3++) {
178 Point P0 = {x0, 0},
179 P1 = {x1, 1},
180 P2 = {x2, 0},
181 P3 = {x3, 1};
182 bool actual = s0_intersects_s1({P0, P1}, {P2, P3});
183 bool expected = (x0 <= x2 && x3 <= x1) || (x2 <= x0 && x1 <= x3);
184 if (actual != expected) {
185 s0_intersects_s1({P0, P1}, {P2, P3});
186 REPORTER_ASSERT(r, actual == expected);
187 }
188 }
189 }
190 }
191 }
192
193 {
194 Segment s0 = {{0, -100}, {0, -50}},
195 s1 = {{100, -100}, {-100, 100}}; // goes through (0,0)
196 REPORTER_ASSERT(r, !s0_intersects_s1(s0, s1));
197 REPORTER_ASSERT(r, !s0_intersects_s1(s1, s0));
198 }
199 {
200 Segment s0 = {{0, 100}, {0, 50}},
201 s1 = {{100, -100}, {-100, 100}}; // goes through (0,0)
202 REPORTER_ASSERT(r, !s0_intersects_s1(s0, s1));
203 REPORTER_ASSERT(r, !s0_intersects_s1(s1, s0));
204 }
205 {
206 Segment s0 = {{0, -101}, {0, -50}},
207 s1 = {{100, -100}, {-100, 100}}; // goes through (0,0)
208 REPORTER_ASSERT(r, !s0_intersects_s1(s0, s1));
209 REPORTER_ASSERT(r, !s0_intersects_s1(s1, s0));
210 }
211 }
212
DEF_TEST(MFC_myers_brute_force_comparison,r)213 DEF_TEST(MFC_myers_brute_force_comparison, r) {
214 const std::vector<Segment> tests[] = {
215 {{{-58, -100}, {75, 105}}, {{149, -58}, {-156, 49}}, {{-34, -55}, {37, 49}}, {{-58, -100}, {75, 105}}, {{-147, -229}, {143, 220}}},
216 {{{-57, -138}, {56, 178}}, {{14, -146}, {-22, 132}}},
217 {{{-4, -23}, {-11, 11}}, {{6, -2}, {-11, 11}}, {{159, -244}, {-159, 233}}},
218 {{{-7, -22}, {10, 14}}, {{-7, -71}, {-7, 80}}, {{-7, -22}, {-4, 5}}},
219 {{{91, -22}, {-93, 24}}, {{31, -18}, {-25, 7}}, {{-25, 7}, {33, 12}}, {{-26, -24}, {18, 20}}},
220 {{{2, -21}, {-16, 7}}, {{-45, -28}, {51, 35}}, {{39, -48}, {-53, 44}}, {{-16, 7}, {26, 7}}},
221 {{{142, -82}, {-128, 64}}, {{208, -16}, {-217, -3}}, {{91, -22}, {-93, 24}}, {{31, -18}, {-25, 7}}, {{-25, 7}, {33, 12}}},
222 {{{-159, -101}, {167, 91}}, {{-96, -117}, {99, 117}}, {{-16, -21}, {12, 35}}, {{-48, -55}, {33, 63}}, {{-16, -21}, {26, 41}}},
223 {{{-51, -18}, {34, 1}}, {{189, -169}, {-171, 150}}, {{24, -8}, {-5, 7}}, {{24, -8}, {-26, 16}}, {{54, -22}, {-36, 20}}},
224 {{{-29, -3}, {15, -3}}, {{-28, -7}, {15, -3}}},
225 {{{20, -149}, {-32, 130}}, {{-29, -3}, {15, -3}}, {{-28, -7}, {15, -3}}},
226 {{{-32, -8}, {16, -8}}, {{-28, -104}, {23, 88}}, {{-17, -11}, {16, -8}}},
227 {{{-59, -9}, {48, 11}}, {{-59, -9}, {75, -9}}, {{173, -20}, {-178, 13}}},
228 {{{-11, 1}, {12, 1}}, {{-42, -35}, {54, 29}}},
229 {{{14, -11}, {-15, -2}}, {{-9, -2}, {13, -2}}}, // both end same s0 horz s1 < s0
230 {{{-38, 7}, {47, 7}}, {{-148, 6}, {166, 7}}}, // just sort of s0 along s1
231 {{{-26, -22}, {9, 21}}, {{-32, -28}, {13, 17}}}, // s1 endpoint on s0
232 {{{23, -2}, {-12, 3}}, {{22, -13}, {-5, 2}}}, // s1 endpoint on s0
233 {{{-2, -100}, {-2, 89}}, {{6, -70}, {-2, 72}}},
234 {{{8, -1}, {-8, 19}}, {{-130, -93}, {137, 85}}}, // Endpoint of s0 lies on s1
235 {{{-39, -111}, {25, 119}}, {{-26, -112}, {25, 119}}}, // Same end points
236 {{{-9, -5}, {16, -5}}, {{90, -134}, {-71, 144}}}, // Diag crossing horizontal
237 {{{-1, -1}, {1, 1}}, {{1, -1}, {-1, 1}}}, // Crossing
238 {{{-1, -1}, {-1, 1}}, {{1, -1}, {1, 1}}}, // Two vertical lines
239 {{{-1, -1}, {1, -1}}, {{-1, 1}, {1, 1}}}, // Two horizontal lines
240 {{{-2, 1}, {1, 1}}, {{-1, 1}, {2, 1}}}, // Overlapping horizontal lines
241 {{{0, -100}, {0, -50}}, {{100, -100}, {-100, 100}}},
242 {{{0, 100}, {0, 50}}, {{100, -100}, {-100, 100}}},
243 {{{0, -101}, {0, -50}}, {{100, -100}, {-100, 100}}},
244 {{{0, 0}, {0, 50}}, {{100, -100}, {-100, 100}}},
245 {{{-10, -10}, {10, 10}}, {{-10, -10}, {11, 11}}, {{10, -10}, {-10, 10}}},
246 {{{10, -10}, {-10, 10}}, {{10, -10}, {-11, 11}}, {{-10, -10}, {10, 10}}},
247 {{{-11, -11}, {10, 10}}, {{-10, -10}, {11, 11}}, {{10, -10}, {-10, 10}}},
248 };
249
250 for (const auto& segments : tests) {
251 std::vector<Segment> myersSegments = segments;
252 std::vector<Segment> bruteSegments = segments;
253 auto myersResponse = myers_find_crossings(myersSegments);
254 auto bruteResponse = brute_force_crossings(bruteSegments);
255
256 std::sort(myersResponse.begin(), myersResponse.end());
257 std::sort(bruteResponse.begin(), bruteResponse.end());
258
259 REPORTER_ASSERT(r, myersResponse.size() == bruteResponse.size());
260 #if 0
261 if (myersResponse.size() != bruteResponse.size()) {
262 SkASSERT(false);
263 }
264 #endif
265 // There should be no duplicate crossings.
266 REPORTER_ASSERT(r,
267 std::unique(myersResponse.begin(), myersResponse.end()) ==
268 myersResponse.end());
269 REPORTER_ASSERT(r,
270 std::unique(bruteResponse.begin(), bruteResponse.end()) ==
271 bruteResponse.end());
272
273 // Both should be equal.
274 REPORTER_ASSERT(r, std::equal(myersResponse.begin(), myersResponse.end(),
275 bruteResponse.begin(), bruteResponse.end()));
276 }
277 }
278
279 class StopWatch {
280 public:
start()281 void start() {
282 fStart = std::chrono::high_resolution_clock::now();
283 }
284
stop()285 void stop() {
286 std::chrono::high_resolution_clock::time_point stop =
287 std::chrono::high_resolution_clock::now();
288
289 fAccumulatedTime += std::chrono::duration_cast<std::chrono::microseconds>(stop - fStart);
290 fCount += 1;
291 }
292
print()293 void print() {
294 int64_t average = fAccumulatedTime.count() / fCount;
295 SkDebugf("average time: %" PRId64 " µs\n", average);
296 }
297
298 private:
299 int fCount = 0;
300 std::chrono::high_resolution_clock::time_point fStart;
301 std::chrono::microseconds fAccumulatedTime = std::chrono::microseconds::zero();
302 };
303
304 constexpr bool kRunRandomTest = false;
DEF_TEST(MFC_myers_brute_force_random_comparison,r)305 DEF_TEST(MFC_myers_brute_force_random_comparison, r) {
306 if constexpr (!kRunRandomTest) {
307 return;
308 }
309 const int n = 200;
310 const int boxSize = 20000;
311 SkRandom random{n + boxSize};
312 std::vector<Segment> segments;
313
314 StopWatch myersStopWatch;
315 StopWatch bruteStopWatch;
316
317 for (int trials = 0; trials < 100'000; trials++) {
318 for (int i = 0; i < n; ++i) {
319 float x = random.nextRangeF(-boxSize, boxSize),
320 y = random.nextRangeF(-boxSize, boxSize);
321
322 float angle = random.nextF() * SK_FloatPI;
323 float distance = random.nextRangeF(10, 300);
324
325 Point p0 = {sk_float_round2int(x + cos(angle) * distance),
326 sk_float_round2int(y + sin(angle) * distance)};
327 Point p1 = {sk_float_round2int(x - cos(angle) * distance),
328 sk_float_round2int(y - sin(angle) * distance)};
329
330 segments.emplace_back(p0, p1);
331 }
332
333 std::vector<Segment> myersSegments = segments;
334 std::vector<Segment> bruteSegments = segments;
335 myersStopWatch.start();
336 auto myersResponse = myers_find_crossings(myersSegments);
337 myersStopWatch.stop();
338 bruteStopWatch.start();
339 auto bruteResponse = brute_force_crossings(bruteSegments);
340 bruteStopWatch.stop();
341
342 std::sort(myersResponse.begin(), myersResponse.end());
343 std::sort(bruteResponse.begin(), bruteResponse.end());
344
345 //SkDebugf("myers size: %zu brute size: %zu\n", myersResponse.size(), bruteResponse.size());
346
347 REPORTER_ASSERT(r, myersResponse.size() == bruteResponse.size());
348 if (myersResponse.size() != bruteResponse.size()) {
349 SkDebugf("myers size: %zu brute size: %zu\n", myersResponse.size(), bruteResponse.size());
350 SkDebugf("{");
351 for (const Segment& s : segments) {
352 const auto [u, l] = s;
353 SkDebugf("{{%d, %d}, {%d, %d}}, ", u.x, u.y, l.x, l.y);
354 }
355 SkDebugf("},\n");
356 }
357
358 // There should be no duplicate crossings.
359 REPORTER_ASSERT(r,
360 std::unique(myersResponse.begin(), myersResponse.end()) ==
361 myersResponse.end());
362 REPORTER_ASSERT(r,
363 std::unique(bruteResponse.begin(), bruteResponse.end()) ==
364 bruteResponse.end());
365
366 // Both should be equal.
367 REPORTER_ASSERT(r, std::equal(myersResponse.begin(), myersResponse.end(),
368 bruteResponse.begin(), bruteResponse.end()));
369 segments.clear();
370 }
371 SkDebugf("myers ");
372 myersStopWatch.print();
373 SkDebugf("brute ");
374 bruteStopWatch.print();
375 }
376