1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.geometry.core.partitioning.bsp;
18
19 import java.util.Arrays;
20 import java.util.List;
21
22 import org.apache.commons.geometry.core.GeometryTestUtils;
23 import org.apache.commons.geometry.core.RegionLocation;
24 import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset;
25 import org.apache.commons.geometry.core.partitioning.test.PartitionTestUtils;
26 import org.apache.commons.geometry.core.partitioning.test.TestLine;
27 import org.apache.commons.geometry.core.partitioning.test.TestLineSegment;
28 import org.apache.commons.geometry.core.partitioning.test.TestPoint2D;
29 import org.apache.commons.geometry.core.partitioning.test.TestRegionBSPTree;
30 import org.junit.jupiter.api.Assertions;
31 import org.junit.jupiter.api.Test;
32
33 class AbstractPartitionedRegionBuilderTest {
34
35 @Test
36 void testCtor_invalidTree() {
37
38 final TestRegionBSPTree tree = new TestRegionBSPTree(true);
39
40
41 GeometryTestUtils.assertThrowsWithMessage(() -> {
42 new TestRegionBuilder(tree);
43 }, IllegalArgumentException.class, "Tree must be empty");
44 }
45
46 @Test
47 void testBuildRegion_empty() {
48
49 final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
50
51
52 final TestRegionBSPTree tree = builder.build();
53
54
55 Assertions.assertTrue(tree.isEmpty());
56 Assertions.assertEquals(1, tree.count());
57 Assertions.assertEquals(0, tree.height());
58 }
59
60 @Test
61 void testInsertPartition_cannotInsertAfterBoundary() {
62
63 final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
64
65 builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
66
67
68 GeometryTestUtils.assertThrowsWithMessage(() -> {
69 builder.insertPartition(new TestLine(new TestPoint2D(0, 0), new TestPoint2D(1, 0)).span());
70 }, IllegalStateException.class, "Cannot insert partitions after boundaries have been inserted");
71 }
72
73 @Test
74 void testBuildRegion_noPartitions_halfSpace() {
75
76 final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
77
78
79 builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
80 final TestRegionBSPTree tree = builder.build();
81
82
83 Assertions.assertFalse(tree.isEmpty());
84 Assertions.assertFalse(tree.isFull());
85
86 Assertions.assertEquals(3, tree.count());
87 Assertions.assertEquals(1, tree.height());
88
89 PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
90 new TestPoint2D(-5, 1), new TestPoint2D(0, 1), new TestPoint2D(5, 1));
91
92 PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
93 new TestPoint2D(-5, 0), new TestPoint2D(0, 0), new TestPoint2D(5, 0));
94
95 PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
96 new TestPoint2D(-5, -1), new TestPoint2D(0, -1), new TestPoint2D(5, -1));
97 }
98
99 @Test
100 void testBuildRegion_boundaryOnPartition_sameOrientation() {
101
102 final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
103
104
105 builder.insertPartition(new TestLine(new TestPoint2D(0, 0), new TestPoint2D(1, 0)).span());
106
107 builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
108 final TestRegionBSPTree tree = builder.build();
109
110
111 Assertions.assertFalse(tree.isEmpty());
112 Assertions.assertFalse(tree.isFull());
113
114 PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
115 new TestPoint2D(-5, 1), new TestPoint2D(0, 1), new TestPoint2D(5, 1));
116
117 PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
118 new TestPoint2D(-5, 0), new TestPoint2D(0, 0), new TestPoint2D(5, 0));
119
120 PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
121 new TestPoint2D(-5, -1), new TestPoint2D(0, -1), new TestPoint2D(5, -1));
122 }
123
124 @Test
125 void testBuildRegion_boundaryOnPartition_oppositeOrientation() {
126
127 final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
128
129
130 builder.insertPartition(new TestLine(new TestPoint2D(1, 0), new TestPoint2D(0, 0)).span());
131
132 builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
133 final TestRegionBSPTree tree = builder.build();
134
135
136 Assertions.assertFalse(tree.isEmpty());
137 Assertions.assertFalse(tree.isFull());
138
139 PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
140 new TestPoint2D(-5, 1), new TestPoint2D(0, 1), new TestPoint2D(5, 1));
141
142 PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
143 new TestPoint2D(-5, 0), new TestPoint2D(0, 0), new TestPoint2D(5, 0));
144
145 PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
146 new TestPoint2D(-5, -1), new TestPoint2D(0, -1), new TestPoint2D(5, -1));
147 }
148
149 @Test
150 void testBuildRegion_boundaryOnPartition_multipleBoundaries_sameOrientation() {
151
152 final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
153
154
155 builder.insertPartition(new TestLine(new TestPoint2D(0, 0), new TestPoint2D(1, 0)).span());
156
157 builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 1), new TestPoint2D(0, 0)));
158 builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
159 final TestRegionBSPTree tree = builder.build();
160
161
162 Assertions.assertFalse(tree.isEmpty());
163 Assertions.assertFalse(tree.isFull());
164
165 PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE, new TestPoint2D(5, 1));
166
167 PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
168 new TestPoint2D(0, 5), new TestPoint2D(0, 0), new TestPoint2D(5, 0));
169
170 PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
171 new TestPoint2D(-5, 1), new TestPoint2D(-5, -1), new TestPoint2D(0, -1), new TestPoint2D(5, -1));
172 }
173
174 @Test
175 void testBuildRegion_boundaryOnPartition_multipleBoundaries_oppositeOrientation() {
176
177 final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
178
179
180 builder.insertPartition(new TestLine(new TestPoint2D(0, 0), new TestPoint2D(-1, 0)).span());
181
182 builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 1), new TestPoint2D(0, 0)));
183 builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
184 final TestRegionBSPTree tree = builder.build();
185
186
187 Assertions.assertFalse(tree.isEmpty());
188 Assertions.assertFalse(tree.isFull());
189
190 PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE, new TestPoint2D(5, 1));
191
192 PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
193 new TestPoint2D(0, 5), new TestPoint2D(0, 0), new TestPoint2D(5, 0));
194
195 PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
196 new TestPoint2D(-5, 1), new TestPoint2D(-5, -1), new TestPoint2D(0, -1), new TestPoint2D(5, -1));
197 }
198
199 @Test
200 void testBuildRegion_multipleBoundariesOnPartition() {
201
202 final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
203
204
205 builder.insertPartition(new TestLine(new TestPoint2D(0, 0), new TestPoint2D(1, 0)).span());
206
207 builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
208 builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 1), new TestPoint2D(0, 0)));
209 builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(0, 0)));
210 builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(-1, 0)));
211
212 final TestRegionBSPTree tree = builder.build();
213
214
215 Assertions.assertFalse(tree.isEmpty());
216 Assertions.assertFalse(tree.isFull());
217
218 PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
219 new TestPoint2D(1, 1), new TestPoint2D(-1, -1));
220
221 PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
222 new TestPoint2D(1, 0), new TestPoint2D(-1, 0), new TestPoint2D(0, 1), new TestPoint2D(0, -1));
223
224 PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
225 new TestPoint2D(-1, 1), new TestPoint2D(1, -1));
226 }
227
228 @Test
229 void testBuildRegion_grid_halfSpace_boundaryOnPartition() {
230
231 final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
232
233
234 insertGridRecursive(-2, 2, 5, builder);
235
236 builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
237 final TestRegionBSPTree tree = builder.build();
238
239
240 Assertions.assertFalse(tree.isEmpty());
241 Assertions.assertFalse(tree.isFull());
242
243 PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
244 new TestPoint2D(-5, 1), new TestPoint2D(0, 1), new TestPoint2D(5, 1));
245
246 PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
247 new TestPoint2D(-5, 0), new TestPoint2D(0, 0), new TestPoint2D(5, 0));
248
249 PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
250 new TestPoint2D(-5, -1), new TestPoint2D(0, -1), new TestPoint2D(5, -1));
251 }
252
253 @Test
254 void testBuildRegion_boundariesOnPartitionPropagateInsideCorrectly() {
255
256 final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
257
258
259 builder.insertPartition(new TestLineSegment(new TestPoint2D(-1, 0), new TestPoint2D(1, 0)));
260 builder.insertPartition(new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(0, 1)));
261
262 builder.insertBoundary(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
263 builder.insertBoundary(new TestLineSegment(new TestPoint2D(1, 1), new TestPoint2D(1, 0)));
264 final TestRegionBSPTree tree = builder.build();
265
266
267 Assertions.assertFalse(tree.isEmpty());
268 Assertions.assertFalse(tree.isFull());
269
270 PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
271 new TestPoint2D(2, 2), new TestPoint2D(5, 5));
272
273 PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
274 new TestPoint2D(1, 0), new TestPoint2D(1, 10), new TestPoint2D(10, 0));
275
276 PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
277 new TestPoint2D(-1, 1), new TestPoint2D(-10, 10),
278 new TestPoint2D(-1, -1), new TestPoint2D(1, -1));
279 }
280
281 @Test
282 void testBuildRegion_grid_cube() {
283
284 final int maxCount = 5;
285
286 final List<TestLineSegment> boundaries = Arrays.asList(
287 new TestLineSegment(new TestPoint2D(-1, -1), new TestPoint2D(1, -1)),
288 new TestLineSegment(new TestPoint2D(1, -1), new TestPoint2D(1, 1)),
289 new TestLineSegment(new TestPoint2D(1, 1), new TestPoint2D(-1, 1)),
290 new TestLineSegment(new TestPoint2D(-1, 1), new TestPoint2D(-1, -1))
291 );
292
293 for (int c = 0; c <= maxCount; ++c) {
294 final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
295
296
297 insertGridRecursive(-2, 2, c, builder);
298
299 for (final TestLineSegment boundary : boundaries) {
300 builder.insertBoundary(boundary);
301 }
302
303 final TestRegionBSPTree tree = builder.build();
304
305
306 Assertions.assertFalse(tree.isEmpty());
307 Assertions.assertFalse(tree.isFull());
308
309 PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
310 new TestPoint2D(0, 0),
311 new TestPoint2D(-0.5, -0.5), new TestPoint2D(0.5, -0.5),
312 new TestPoint2D(0.5, 0.5), new TestPoint2D(-0.5, 0.5));
313
314 PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
315 new TestPoint2D(-1, -1), new TestPoint2D(1, -1), new TestPoint2D(1, 1), new TestPoint2D(-1, 1),
316 new TestPoint2D(-1, 0), new TestPoint2D(1, 0), new TestPoint2D(0, 1), new TestPoint2D(0, -1));
317
318 PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
319 new TestPoint2D(-2, -2), new TestPoint2D(2, -2), new TestPoint2D(2, 2), new TestPoint2D(-2, 2),
320 new TestPoint2D(-2, 0), new TestPoint2D(2, 0), new TestPoint2D(0, 2), new TestPoint2D(0, -2));
321 }
322 }
323
324 @Test
325 void testBuildRegion_grid_diamond() {
326
327 final int maxCount = 5;
328
329 final List<TestLineSegment> boundaries = Arrays.asList(
330 new TestLineSegment(new TestPoint2D(0, 1), new TestPoint2D(-1, 0)),
331 new TestLineSegment(new TestPoint2D(-1, 0), new TestPoint2D(0, -1)),
332 new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(1, 0)),
333 new TestLineSegment(new TestPoint2D(1, 0), new TestPoint2D(0, 1))
334 );
335
336 for (int c = 0; c <= maxCount; ++c) {
337 final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
338
339
340 insertGridRecursive(-2, 2, c, builder);
341
342 for (final TestLineSegment boundary : boundaries) {
343 builder.insertBoundary(boundary);
344 }
345
346 final TestRegionBSPTree tree = builder.build();
347
348
349 Assertions.assertFalse(tree.isEmpty());
350 Assertions.assertFalse(tree.isFull());
351
352 PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
353 new TestPoint2D(0, 0),
354 new TestPoint2D(-0.25, -0.25), new TestPoint2D(0.25, -0.25),
355 new TestPoint2D(0.25, 0.25), new TestPoint2D(-0.25, 0.25));
356
357 PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
358 new TestPoint2D(-0.5, 0.5), new TestPoint2D(-0.5, -0.5), new TestPoint2D(0.5, -0.5), new TestPoint2D(0.5, 0.5),
359 new TestPoint2D(-1, 0), new TestPoint2D(1, 0), new TestPoint2D(0, 1), new TestPoint2D(0, -1));
360
361 PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
362 new TestPoint2D(-2, -2), new TestPoint2D(2, -2), new TestPoint2D(2, 2), new TestPoint2D(-2, 2),
363 new TestPoint2D(-2, 0), new TestPoint2D(2, 0), new TestPoint2D(0, 2), new TestPoint2D(0, -2));
364 }
365 }
366
367 @Test
368 void testBuildRegion_grid_horseshoe() {
369
370 final int maxCount = 5;
371
372 final List<TestLineSegment> boundaries = Arrays.asList(
373 new TestLineSegment(new TestPoint2D(1, 0), new TestPoint2D(1, 1)),
374 new TestLineSegment(new TestPoint2D(1, 1), new TestPoint2D(3, 1)),
375 new TestLineSegment(new TestPoint2D(3, 1), new TestPoint2D(3, 2)),
376 new TestLineSegment(new TestPoint2D(3, 2), new TestPoint2D(-1, 2)),
377 new TestLineSegment(new TestPoint2D(-1, 2), new TestPoint2D(-1, -1)),
378 new TestLineSegment(new TestPoint2D(-1, -1), new TestPoint2D(3, -1)),
379 new TestLineSegment(new TestPoint2D(3, -1), new TestPoint2D(3, 0)),
380 new TestLineSegment(new TestPoint2D(3, 0), new TestPoint2D(1, 0))
381 );
382
383 for (int c = 0; c <= maxCount; ++c) {
384 final TestRegionBuilder builder = new TestRegionBuilder(new TestRegionBSPTree(false));
385
386
387 insertGridRecursive(-2, 2, c, builder);
388
389 for (final TestLineSegment boundary : boundaries) {
390 builder.insertBoundary(boundary);
391 }
392
393 final TestRegionBSPTree tree = builder.build();
394
395
396 Assertions.assertFalse(tree.isEmpty());
397 Assertions.assertFalse(tree.isFull());
398
399 PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
400 new TestPoint2D(0, 0),
401 new TestPoint2D(0, 1.5), new TestPoint2D(2, 1.5),
402 new TestPoint2D(0, -0.5), new TestPoint2D(2, -0.5));
403
404 PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
405 new TestPoint2D(1, 0), new TestPoint2D(1, 1), new TestPoint2D(3, 1), new TestPoint2D(3, 2),
406 new TestPoint2D(-1, 2), new TestPoint2D(-1, -1), new TestPoint2D(3, -1), new TestPoint2D(3, 0),
407 new TestPoint2D(1, 0.5), new TestPoint2D(2, 1), new TestPoint2D(3, 1.5), new TestPoint2D(1, 2),
408 new TestPoint2D(-1, 0.5), new TestPoint2D(3, -0.5), new TestPoint2D(2, 0));
409
410 PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
411 new TestPoint2D(2, 0.5), new TestPoint2D(4, 0.5), new TestPoint2D(4, 0), new TestPoint2D(4, 1.5),
412 new TestPoint2D(1, 4), new TestPoint2D(1, -4), new TestPoint2D(-4, 0.5));
413 }
414 }
415
416 private static void insertGridRecursive(final double min, final double max, final int count, final TestRegionBuilder builder) {
417 if (count > 0) {
418 final double center = (0.5 * (max - min)) + min;
419
420 builder.insertPartition(
421 new TestLine(new TestPoint2D(center, center), new TestPoint2D(center + 1, center)).span());
422
423 builder.insertPartition(
424 new TestLine(new TestPoint2D(center, center), new TestPoint2D(center, center + 1)).span());
425
426 insertGridRecursive(min, center, count - 1, builder);
427 insertGridRecursive(center, max, count - 1, builder);
428 }
429 }
430
431 private static class TestRegionBuilder
432 extends AbstractPartitionedRegionBuilder<TestPoint2D, TestRegionBSPTree.TestRegionNode> {
433
434 TestRegionBuilder(final TestRegionBSPTree tree) {
435 super(tree);
436 }
437
438 public TestRegionBSPTree build() {
439 return (TestRegionBSPTree) buildInternal();
440 }
441
442 public void insertPartition(final HyperplaneConvexSubset<TestPoint2D> partition) {
443 insertPartitionInternal(partition);
444 }
445
446 public void insertBoundary(final HyperplaneConvexSubset<TestPoint2D> boundary) {
447 insertBoundaryInternal(boundary);
448 }
449 }
450 }