Flutter Engine
The Flutter Engine
Classes | Namespaces | Functions | Variables
MyersTest.cpp File Reference
#include "modules/bentleyottmann/include/Myers.h"
#include "src/base/SkRandom.h"
#include "tests/Test.h"
#include <chrono>
#include <cinttypes>
#include <cstdint>

Go to the source code of this file.

Classes

class  StopWatch
 

Namespaces

namespace  myers
 

Functions

bool myers::slope_s0_less_than_slope_s1 (const Segment &s0, const Segment &s1)
 
bool myers::segment_less_than_upper_to_insert (const Segment &segment, const Segment &to_insert)
 
bool myers::s0_less_than_s1_at_y (const Segment &s0, const Segment &s1, int32_t y)
 
bool myers::s0_intersects_s1 (const Segment &s0, const Segment &s1)
 
static bool operator== (std::pair< const Point &, const Point & > l, std::tuple< Point, Point > r)
 
 DEF_TEST (MFC_order_segment_points, r)
 
 DEF_TEST (MFC_segment_ctor, r)
 
 DEF_TEST (MFC_slope_less_than, r)
 
 DEF_TEST (MFC_segment_less_than_upper_to_insert, r)
 
 DEF_TEST (MFC_less_than_at_y, r)
 
static Segment swap_ends (const Segment &s)
 
 DEF_TEST (MFC_has_inner_intersection, r)
 
 DEF_TEST (MFC_myers_brute_force_comparison, r)
 
 DEF_TEST (MFC_myers_brute_force_random_comparison, r)
 

Variables

constexpr bool kRunRandomTest = false
 

Function Documentation

◆ DEF_TEST() [1/8]

DEF_TEST ( MFC_has_inner_intersection  ,
r   
)

Definition at line 138 of file MyersTest.cpp.

138 {
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}
swap_ends
static Segment swap_ends(const Segment &s)
Definition: MyersTest.cpp:134
REPORTER_ASSERT
#define REPORTER_ASSERT(r, cond,...)
Definition: Test.h:286
myers::s0_intersects_s1
bool s0_intersects_s1(const Segment &s0, const Segment &s1)
Definition: Myers.cpp:577

◆ DEF_TEST() [2/8]

DEF_TEST ( MFC_less_than_at_y  ,
r   
)

Definition at line 109 of file MyersTest.cpp.

109 {
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}
myers::s0_less_than_s1_at_y
bool s0_less_than_s1_at_y(const Segment &s0, const Segment &s1, int32_t y)
Definition: Myers.cpp:166

◆ DEF_TEST() [3/8]

DEF_TEST ( MFC_myers_brute_force_comparison  ,
r   
)

Definition at line 213 of file MyersTest.cpp.

213 {
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}
tests
static BlurTest tests[]
Definition: BlurTest.cpp:84
equal
static bool equal(const SkBitmap &a, const SkBitmap &b)
Definition: ImageTest.cpp:1395
SkASSERT
#define SkASSERT(cond)
Definition: SkAssert.h:116
sort
static std::vector< SkPDFIndirectReference > sort(const THashSet< SkPDFIndirectReference > &src)
Definition: SkPDFDevice.cpp:1061
bentleyottmann::brute_force_crossings
std::optional< std::vector< Crossing > > brute_force_crossings(SkSpan< const Segment > segments)
Definition: BruteForceCrossings.cpp:12
myers::myers_find_crossings
std::vector< Crossing > myers_find_crossings(const SkSpan< const Segment > segments)
Definition: Myers.cpp:565

◆ DEF_TEST() [4/8]

DEF_TEST ( MFC_myers_brute_force_random_comparison  ,
r   
)

Definition at line 305 of file MyersTest.cpp.

305 {
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}
kRunRandomTest
constexpr bool kRunRandomTest
Definition: MyersTest.cpp:304
SkDebugf
void SK_SPI SkDebugf(const char format[],...) SK_PRINTF_LIKE(1
sk_float_round2int
#define sk_float_round2int(x)
Definition: SkFloatingPoint.h:119
SK_FloatPI
constexpr float SK_FloatPI
Definition: SkFloatingPoint.h:20
StopWatch::start
void start()
Definition: MyersTest.cpp:281
StopWatch::print
void print()
Definition: MyersTest.cpp:293
StopWatch::stop
void stop()
Definition: MyersTest.cpp:285
s
struct MyStruct s
i
int i
Definition: fl_socket_accessible.cc:18
y
double y
Definition: mouse-input-test.cc:83
x
double x
Definition: mouse-input-test.cc:82

◆ DEF_TEST() [5/8]

DEF_TEST ( MFC_order_segment_points  ,
r   
)

Definition at line 26 of file MyersTest.cpp.

26 {
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}

◆ DEF_TEST() [6/8]

DEF_TEST ( MFC_segment_ctor  ,
r   
)

Definition at line 47 of file MyersTest.cpp.

47 {
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}

◆ DEF_TEST() [7/8]

DEF_TEST ( MFC_segment_less_than_upper_to_insert  ,
r   
)

Definition at line 93 of file MyersTest.cpp.

93 {
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}
myers::segment_less_than_upper_to_insert
bool segment_less_than_upper_to_insert(const Segment &segment, const Segment &to_insert)
Definition: Myers.cpp:158

◆ DEF_TEST() [8/8]

DEF_TEST ( MFC_slope_less_than  ,
r   
)

Definition at line 67 of file MyersTest.cpp.

67 {
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}
myers::slope_s0_less_than_slope_s1
bool slope_s0_less_than_slope_s1(const Segment &s0, const Segment &s1)
Definition: Myers.cpp:109

◆ operator==()

static bool operator== ( std::pair< const Point &, const Point & >  l,
std::tuple< Point, Point >  r 
)
static

Definition at line 22 of file MyersTest.cpp.

22 {
23 return std::get<0>(l) == std::get<0>(r) && std::get<1>(l) == std::get<1>(r);
24}
myers::get< 1 >
const myers::Point & get< 1 >(const myers::Segment &s)
Definition: Myers.h:81
myers::get< 0 >
const myers::Point & get< 0 >(const myers::Segment &s)
Definition: Myers.h:80

◆ swap_ends()

static Segment swap_ends ( const Segment &  s)
static

Definition at line 134 of file MyersTest.cpp.

134 {
135 return {s.lower(), s.upper()};
136}

Variable Documentation

◆ kRunRandomTest

constexpr bool kRunRandomTest = false
constexpr

Definition at line 304 of file MyersTest.cpp.

Generated on Sun Jun 23 2024 21:57:15 for Flutter Engine by doxygen 1.9.4