Flutter Engine
The Flutter Engine
Loading...
Searching...
No Matches
SegmentTest.cpp
Go to the documentation of this file.
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/Segment.h"
5#include "tests/Test.h"
6
7using namespace bentleyottmann;
8
9DEF_TEST(BO_SegmentBasic, reporter) {
10 {
11 Segment s = {{0, 0}, {1, 1}};
12 REPORTER_ASSERT(reporter, s.upper() == s.p0);
13 REPORTER_ASSERT(reporter, s.lower() == s.p1);
14 }
15
16 {
17 Segment s = {{1, 0}, {0, 1}};
18 REPORTER_ASSERT(reporter, s.upper() == s.p0);
19 REPORTER_ASSERT(reporter, s.lower() == s.p1);
20 }
21
22 {
23 Segment s = {{1, 1}, {0, 0}};
24 REPORTER_ASSERT(reporter, s.upper() == s.p1);
25 REPORTER_ASSERT(reporter, s.lower() == s.p0);
26 }
27
28 {
29 Segment s = {{0, 1}, {1, 0}};
30 REPORTER_ASSERT(reporter, s.upper() == s.p1);
31 REPORTER_ASSERT(reporter, s.lower() == s.p0);
32 }
33}
34
35static Segment swap_ends(const Segment& s) {
36 return {s.p1, s.p0};
37}
38
39DEF_TEST(BO_no_intersection_bounding_box, reporter) {
40 Segment interesting[] = {{Point::Smallest(), Point::Smallest()+ Point{10, 5}},
41 {Point::Largest(), Point::Largest() - Point{10, 5}},
42 {{-10, -5}, {10, 5}}};
43
44 // Intersection
45 for (auto& s0 : interesting) {
46 auto [l, t, r, b] = s0.bounds();
47
48 // Points in the interior of interesting rectangles
49 for(Point p : {Point {l + 1, t + 1},
50 Point {r - 1, t + 1},
51 Point {r - 1, b - 1},
52 Point {l + 1, b - 1}}) {
53 Segment s1 = {p, {0, 0}};
54 REPORTER_ASSERT(reporter, !no_intersection_by_bounding_box(s0, s1));
55 REPORTER_ASSERT(reporter, !no_intersection_by_bounding_box(s1, s0));
56 REPORTER_ASSERT(reporter,
57 !no_intersection_by_bounding_box(swap_ends(s0), swap_ends(s1)));
58 REPORTER_ASSERT(reporter,
59 !no_intersection_by_bounding_box(swap_ends(s0), swap_ends(s1)));
60 }
61 }
62
63 int32_t small = Point::Smallest().x,
64 big = Point::Largest().x;
65
66 // No Intersection
67 for (auto& s0 : interesting) {
68 auto [l, t, r, b] = s0.bounds();
69
70 Segment outside[] = {{{r, t}, {big, b}},
71 {{r, b}, {big, big}},
72 {{l, b}, {r, big}},
73 {{l, b}, {small, big}},
74 {{l, t}, {small, b}},
75 {{l, t}, {small, small}},
76 {{l, t}, {r, small}},
77 {{r, t}, {small, small}}};
78
79 for (auto& s1 : outside) {
80 REPORTER_ASSERT(reporter, no_intersection_by_bounding_box(s0, s1));
81 REPORTER_ASSERT(reporter, no_intersection_by_bounding_box(s1, s0));
82 REPORTER_ASSERT(reporter,
83 no_intersection_by_bounding_box(swap_ends(s0), swap_ends(s1)));
84 REPORTER_ASSERT(reporter,
85 no_intersection_by_bounding_box(swap_ends(s0), swap_ends(s1)));
86 }
87 }
88}
89
90DEF_TEST(BO_intersectBasic, reporter) {
91
92 auto checkIntersection = [reporter](Segment s0, Segment s1, Point expected) {
93 {
94 auto answer = intersect(s0, s1);
95 REPORTER_ASSERT(reporter, answer.has_value());
96 REPORTER_ASSERT(reporter, answer.value() == expected);
97 }
98 {
99 auto answer = intersect(s1, s0);
100 REPORTER_ASSERT(reporter, answer.has_value());
101 REPORTER_ASSERT(reporter, answer.value() == expected);
102 }
103 {
104 auto answer = intersect(swap_ends(s0), swap_ends(s1));
105 REPORTER_ASSERT(reporter, answer.has_value());
106 REPORTER_ASSERT(reporter, answer.value() == expected);
107 }
108 {
109 auto answer = intersect(swap_ends(s1), swap_ends(s0));
110 REPORTER_ASSERT(reporter, answer.has_value());
111 REPORTER_ASSERT(reporter, answer.value() == expected);
112 }
113 };
114
115 {
116 Segment s0 = {{-1, 0}, {1, 0}},
117 s1 = {{ 0, 1}, {0, -1}};
118
119 checkIntersection(s0, s1, Point{0, 0});
120 }
121 {
122 Segment s0 = {{-1, 0}, {5, 0}},
123 s1 = {{ 0, 1}, {0, -1}};
124
125 checkIntersection(s0, s1, Point{0, 0});
126 }
127
128 {
129 Segment s0 = {{5, 0}, {-1, 0}},
130 s1 = {{ 0, -1}, {0, 1}};
131
132 checkIntersection(s0, s1, Point{0, 0});
133 }
134
135 {
136 Segment s0 = {{-5, -5}, {5, 5}},
137 s1 = {{-5, 5}, {5, -5}};
138
139 checkIntersection(s0, s1, Point{0, 0});
140 }
141
142 // Test very close segments (x0, 0) -> (x1, 1) & (x2, 0) -> (x3, 1)
143 for (int32_t x0 = -10; x0 <= 10; x0++) {
144 for (int32_t x1 = -10; x1 <= 10; x1++) {
145 for (int32_t x2 = -10; x2 <= 10; x2++) {
146 for (int32_t x3 = -10; x3 <= 10; x3++) {
147 Point P0 = {x0, 0},
148 P1 = {x1, 1},
149 P2 = {x2, 0},
150 P3 = {x3, 1};
151 auto actual = intersect({P0, P1}, {P2, P3});
152 bool expected = (x0 < x2 && x3 < x1) || (x2 < x0 && x1 < x3);
153 REPORTER_ASSERT(reporter, actual.has_value() == expected);
154 if (actual) {
155 int32_t y = std::abs(x2 - x0) >= std::abs(x3 - x1);
156 REPORTER_ASSERT(reporter, actual.value().y == y);
157 }
158 }
159 }
160 }
161 }
162
163 {
164 Segment s0 = {{0, -100}, {0, -50}},
165 s1 = {{100, -100}, {-100, 100}}; // goes through (0,0)
166 auto answer = intersect(s0, s1);
167 REPORTER_ASSERT(reporter, !answer.has_value());
168 answer = intersect(s1, s0);
169 REPORTER_ASSERT(reporter, !answer.has_value());
170 }
171 {
172 Segment s0 = {{0, 100}, {0, 50}},
173 s1 = {{100, -100}, {-100, 100}}; // goes through (0,0)
174 auto answer = intersect(s0, s1);
175 REPORTER_ASSERT(reporter, !answer.has_value());
176 answer = intersect(s1, s0);
177 REPORTER_ASSERT(reporter, !answer.has_value());
178 }
179}
180
181DEF_TEST(BO_lessAtBasic, reporter) {
182 { // Parallel lines
183 Segment s0 = {{-1, 1}, {-1, -1}},
184 s1 = {{1, 1}, {1, -1}};
185
186 REPORTER_ASSERT(reporter, less_than_at(s0, s1, -1));
187 REPORTER_ASSERT(reporter, !less_than_at(s1, s0, -1));
188 REPORTER_ASSERT(reporter, less_than_at(s0, s1, 0));
189 REPORTER_ASSERT(reporter, !less_than_at(s1, s0, 0));
190 REPORTER_ASSERT(reporter, less_than_at(s0, s1, 1));
191 REPORTER_ASSERT(reporter, !less_than_at(s1, s0, 1));
192 }
193 { // Crossed lines
194 Segment s0 = {{-1, -1}, {1, 1}},
195 s1 = {{1, -1}, {-1, 1}};
196
197 REPORTER_ASSERT(reporter, less_than_at(s0, s1, -1));
198 REPORTER_ASSERT(reporter, !less_than_at(s1, s0, -1));
199
200 // When they are == neither is less.
201 REPORTER_ASSERT(reporter, !less_than_at(s0, s1, 0));
202 REPORTER_ASSERT(reporter, !less_than_at(s1, s0, 0));
203
204 REPORTER_ASSERT(reporter, !less_than_at(s0, s1, 1));
205 REPORTER_ASSERT(reporter, less_than_at(s1, s0, 1));
206 }
207 { // Near crossing
208 Segment s0 = {{0, -100}, {0, 100}},
209 s1 = {{-3, 98}, {3, 104}};
210
211 REPORTER_ASSERT(reporter, !less_than_at(s0, s1, 98));
212 REPORTER_ASSERT(reporter, less_than_at(s1, s0, 98));
213
214 REPORTER_ASSERT(reporter, !less_than_at(s0, s1, 99));
215 REPORTER_ASSERT(reporter, less_than_at(s1, s0, 99));
216
217 REPORTER_ASSERT(reporter, !less_than_at(s0, s1, 100));
218 REPORTER_ASSERT(reporter, less_than_at(s1, s0, 100));
219 }
220}
221
222DEF_TEST(BO_compareSlopesBasic, reporter) {
223 { // Both horizontal
224 Segment s0 = {{-1, 1}, {0, 1}},
225 s1 = {{-2, 1}, {1, 1}};
226 REPORTER_ASSERT(reporter, compare_slopes(s0, s1) == 0);
227 REPORTER_ASSERT(reporter, compare_slopes(s1, s0) == 0);
228 }
229 { // One horizontal
230 Segment s0 = {{-1, 1}, {0, 0}},
231 s1 = {{-2, 1}, {1, 1}};
232 REPORTER_ASSERT(reporter, compare_slopes(s0, s1) == -1);
233 REPORTER_ASSERT(reporter, compare_slopes(s1, s0) == 1);
234 }
235 { // One vertical
236 Segment s0 = {{-1, 1}, {-1, 0}}, // Vertical
237 s1 = {{-2, 1}, {-1, 0}},
238 s2 = {{2, 1}, {-1, 0}};
239 REPORTER_ASSERT(reporter, compare_slopes(s0, s1) == 1);
240 REPORTER_ASSERT(reporter, compare_slopes(s1, s0) == -1);
241 REPORTER_ASSERT(reporter, compare_slopes(s0, s2) == -1);
242 REPORTER_ASSERT(reporter, compare_slopes(s2, s0) == 1);
243 }
244
245 { // Equal slope
246 Segment s0 = {{-2, 1}, {0, 0}},
247 s1 = {{-4, 2}, {0, 0}};
248 REPORTER_ASSERT(reporter, compare_slopes(s0, s1) == 0);
249 REPORTER_ASSERT(reporter, compare_slopes(s1, s0) == 0);
250 }
251
252 { // Equal slope
253 Segment s0 = {{2, 1}, {0, 0}},
254 s1 = {{4, 2}, {0, 0}};
255 REPORTER_ASSERT(reporter, compare_slopes(s0, s1) == 0);
256 REPORTER_ASSERT(reporter, compare_slopes(s1, s0) == 0);
257 }
258
259 {
260 Segment s0 = {{-2, 1}, {0, 0}},
261 s1 = {{4, 2}, {0, 0}};
262 REPORTER_ASSERT(reporter, compare_slopes(s0, s1) == -1);
263 REPORTER_ASSERT(reporter, compare_slopes(s1, s0) == 1);
264 }
265
266 {
267 Segment s0 = {{-2, 1}, {0, 0}},
268 s1 = {{-3, 1}, {0, 0}};
269 REPORTER_ASSERT(reporter, compare_slopes(s0, s1) == 1);
270 REPORTER_ASSERT(reporter, compare_slopes(s1, s0) == -1);
271 }
272}
273
274DEF_TEST(BO_rounded_point_less_than_segment_in_x_lower, reporter) {
275 { // Vertical segment
276 Segment s = {{3, -50}, {3, 50}};
277 REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_lower(s, {4, 7}));
278 REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {3, 7}));
279 REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {2, 7}));
280 }
281 { // Horizontal segment
282 Segment s = {{-10, 3}, {10, 3}};
283 REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_lower(s, {11, 3}));
284 REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {10, 3}));
285 REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {4, 3}));
286 REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {-10, 3}));
287 REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {-11, 3}));
288 }
289 { // Pass through {0, 0}
290 Segment s = {{-100, -100}, {100, 100}};
291 REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_lower(s, {1, 0}));
292 REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {0, 0}));
293 REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {-1, 0}));
294 }
295 { // Just left of {0, 0}, but still rounds to {0, 0}
296 Segment s = {{-100, -100}, {199, 200}};
297 REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_lower(s, {1, 0}));
298 REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {0, 0}));
299 REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {-1, 0}));
300 }
301 { // Just right of {0, 0}, but still rounds to {0, 0}
302 Segment s = {{-100, -100}, {201, 200}};
303 REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_lower(s, {1, 0}));
304 REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {0, 0}));
305 REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_lower(s, {-1, 0}));
306 }
307}
308
309DEF_TEST(BO_rounded_point_less_than_segment_in_x_upper, reporter) {
310 { // Vertical segment
311 Segment s = {{3, -50}, {3, 50}};
312 REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_upper(s, {4, 7}));
313 REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_upper(s, {3, 7}));
314 REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_upper(s, {2, 7}));
315 }
316 { // Horizontal segment
317 Segment s = {{-10, 3}, {10, 3}};
318 REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_upper(s, {11, 3}));
319 REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_upper(s, {10, 3}));
320 REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_upper(s, {4, 3}));
321 REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_upper(s, {-10, 3}));
322 REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_upper(s, {-11, 3}));
323 }
324 { // Pass through {0, 0}
325 Segment s = {{-100, -100}, {100, 100}};
326 REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_upper(s, {1, 0}));
327 REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_upper(s, {0, 0}));
328 REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_upper(s, {-1, 0}));
329 }
330 { // Just left of {0, 0}, but still rounds to {0, 0}
331 Segment s = {{-100, -100}, {199, 200}};
332 REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_upper(s, {1, 0}));
333 REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_upper(s, {0, 0}));
334 REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_upper(s, {-1, 0}));
335 }
336 { // Just right of {0, 0}, but still rounds to {0, 0}
337 Segment s = {{-100, -100}, {201, 200}};
338 REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_upper(s, {1, 0}));
339 REPORTER_ASSERT(reporter, rounded_point_less_than_segment_in_x_upper(s, {0, 0}));
340 REPORTER_ASSERT(reporter, !rounded_point_less_than_segment_in_x_upper(s, {-1, 0}));
341 }
342}
reporter
reporter
Definition FontMgrTest.cpp:39
swap_ends
static Segment swap_ends(const Segment &s)
Definition SegmentTest.cpp:35
DEF_TEST
#define DEF_TEST(name, reporter)
Definition Test.h:312
REPORTER_ASSERT
#define REPORTER_ASSERT(r, cond,...)
Definition Test.h:286
b
static bool b
Definition ffi_native_test_module.c:74
s
struct MyStruct s
y
double y
Definition mouse-input-test.cc:83
bentleyottmann::rounded_point_less_than_segment_in_x_lower
bool rounded_point_less_than_segment_in_x_lower(const Segment &s, Point p)
Definition Segment.cpp:248
bentleyottmann::rounded_point_less_than_segment_in_x_upper
bool rounded_point_less_than_segment_in_x_upper(const Segment &s, Point p)
Definition Segment.cpp:290
bentleyottmann::no_intersection_by_bounding_box
bool no_intersection_by_bounding_box(const Segment &s0, const Segment &s1)
Definition Segment.cpp:39
bentleyottmann::intersect
std::optional< Point > intersect(const Segment &s0, const Segment &s1)
Definition Segment.cpp:97
bentleyottmann::compare_slopes
int compare_slopes(const Segment &s0, const Segment &s1)
Definition Segment.cpp:329
bentleyottmann::less_than_at
bool less_than_at(const Segment &s0, const Segment &s1, int32_t y)
Definition Segment.cpp:178
bentleyottmann::Point::Smallest
static Point Smallest()
Definition Point.cpp:36
bentleyottmann::Point::Largest
static Point Largest()
Definition Point.cpp:41
Generated on Fri Apr 26 2024 06:16:16 for Flutter Engine by doxygen 1.9.8