View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.geometry.core.partitioning;
18  
19  import java.util.ArrayList;
20  import java.util.Arrays;
21  import java.util.Collections;
22  import java.util.List;
23  
24  import org.apache.commons.geometry.core.GeometryTestUtils;
25  import org.apache.commons.geometry.core.Region;
26  import org.apache.commons.geometry.core.RegionLocation;
27  import org.apache.commons.geometry.core.Transform;
28  import org.apache.commons.geometry.core.partitioning.test.PartitionTestUtils;
29  import org.apache.commons.geometry.core.partitioning.test.TestLine;
30  import org.apache.commons.geometry.core.partitioning.test.TestLineSegment;
31  import org.apache.commons.geometry.core.partitioning.test.TestPoint2D;
32  import org.apache.commons.geometry.core.partitioning.test.TestTransform2D;
33  import org.junit.jupiter.api.Assertions;
34  import org.junit.jupiter.api.Test;
35  
36  class AbstractConvexHyperplaneBoundedRegionTest {
37  
38      @Test
39      void testBoundaries_areUnmodifiable() {
40          // arrange
41          final StubRegion region = new StubRegion(new ArrayList<>());
42          final List<TestLineSegment> boundaries = region.getBoundaries();
43          final TestLineSegment span = TestLine.X_AXIS.span();
44  
45  
46          // act/assert
47          Assertions.assertThrows(UnsupportedOperationException.class, () ->  boundaries.add(span));
48      }
49  
50      @Test
51      void testFull() {
52          // act
53          final StubRegion region = new StubRegion(Collections.emptyList());
54  
55          // assert
56          Assertions.assertTrue(region.isFull());
57          Assertions.assertFalse(region.isEmpty());
58      }
59  
60      @Test
61      void testGetBoundarySize() {
62          // arrange
63          final TestPoint2D p1 = new TestPoint2D(1, 0);
64          final TestPoint2D p2 = new TestPoint2D(2, 0);
65          final TestPoint2D p3 = new TestPoint2D(1, 1);
66  
67          // act/assert
68          Assertions.assertEquals(0, new StubRegion(Collections.emptyList()).getBoundarySize(), PartitionTestUtils.EPS);
69          GeometryTestUtils.assertPositiveInfinity(new StubRegion(Collections.singletonList(TestLine.X_AXIS.span())).getBoundarySize());
70          Assertions.assertEquals(2 + Math.sqrt(2), new StubRegion(Arrays.asList(
71                      new TestLineSegment(p1, p2),
72                      new TestLineSegment(p2, p3),
73                      new TestLineSegment(p3, p1)
74                  )).getBoundarySize(), PartitionTestUtils.EPS);
75      }
76  
77      @Test
78      void testClassify() {
79          // arrange
80          final TestPoint2D p1 = new TestPoint2D(1, 0);
81          final TestPoint2D p2 = new TestPoint2D(2, 0);
82          final TestPoint2D p3 = new TestPoint2D(1, 1);
83  
84          final StubRegion full = new StubRegion(Collections.emptyList());
85          final StubRegion halfSpace = new StubRegion(Collections.singletonList(TestLine.X_AXIS.span()));
86          final StubRegion triangle = new StubRegion(Arrays.asList(
87                  new TestLineSegment(p1, p2),
88                  new TestLineSegment(p2, p3),
89                  new TestLineSegment(p3, p1)
90              ));
91  
92          // act/assert
93          checkClassify(full, RegionLocation.INSIDE, TestPoint2D.ZERO, p1, p2, p3);
94  
95          checkClassify(halfSpace, RegionLocation.INSIDE, new TestPoint2D(0, 1));
96          checkClassify(halfSpace, RegionLocation.OUTSIDE, new TestPoint2D(0, -1));
97          checkClassify(halfSpace, RegionLocation.BOUNDARY,
98                  new TestPoint2D(-1, 0), new TestPoint2D(0, 0), new TestPoint2D(1, 0));
99  
100         checkClassify(triangle, RegionLocation.INSIDE, new TestPoint2D(1.25, 0.25));
101         checkClassify(triangle, RegionLocation.OUTSIDE, new TestPoint2D(-1, 0), new TestPoint2D(0, 0), new TestPoint2D(3, 0));
102         checkClassify(triangle, RegionLocation.BOUNDARY, p1, p2, p3);
103     }
104 
105     @Test
106     void testProject() {
107         // arrange
108         final TestPoint2D p1 = new TestPoint2D(1, 0);
109         final TestPoint2D p2 = new TestPoint2D(2, 0);
110         final TestPoint2D p3 = new TestPoint2D(1, 1);
111 
112         final StubRegion full = new StubRegion(Collections.emptyList());
113         final StubRegion halfSpace = new StubRegion(Collections.singletonList(TestLine.X_AXIS.span()));
114         final StubRegion triangle = new StubRegion(Arrays.asList(
115                 new TestLineSegment(p1, p2),
116                 new TestLineSegment(p2, p3),
117                 new TestLineSegment(p3, p1)
118             ));
119 
120         // act/assert
121         Assertions.assertNull(full.project(TestPoint2D.ZERO));
122         Assertions.assertNull(full.project(new TestPoint2D(1, 1)));
123 
124         PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, halfSpace.project(new TestPoint2D(0, 1)));
125         PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, halfSpace.project(new TestPoint2D(0, 0)));
126         PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, halfSpace.project(new TestPoint2D(0, -1)));
127 
128         PartitionTestUtils.assertPointsEqual(new TestPoint2D(1.25, 0), triangle.project(new TestPoint2D(1.25, 0.1)));
129         PartitionTestUtils.assertPointsEqual(p1, triangle.project(TestPoint2D.ZERO));
130         PartitionTestUtils.assertPointsEqual(p3, triangle.project(new TestPoint2D(0, 10)));
131     }
132 
133     @Test
134     void testTrim() {
135         // arrange
136         final TestPoint2D p1 = new TestPoint2D(1, 0);
137         final TestPoint2D p2 = new TestPoint2D(2, 0);
138         final TestPoint2D p3 = new TestPoint2D(2, 1);
139         final TestPoint2D p4 = new TestPoint2D(1, 1);
140 
141         final StubRegion full = new StubRegion(Collections.emptyList());
142         final StubRegion halfSpace = new StubRegion(Collections.singletonList(TestLine.Y_AXIS.span()));
143         final StubRegion square = new StubRegion(Arrays.asList(
144                 new TestLineSegment(p1, p2),
145                 new TestLineSegment(p2, p3),
146                 new TestLineSegment(p3, p4),
147                 new TestLineSegment(p4, p1)
148             ));
149 
150         final TestLineSegment segment = new TestLineSegment(new TestPoint2D(-1, 0.5), new TestPoint2D(4, 0.5));
151 
152         // act/assert
153         Assertions.assertSame(segment, full.trim(segment));
154 
155         final TestLineSegment trimmedA = halfSpace.trim(segment);
156         PartitionTestUtils.assertPointsEqual(new TestPoint2D(-1, 0.5), trimmedA.getStartPoint());
157         PartitionTestUtils.assertPointsEqual(new TestPoint2D(0, 0.5), trimmedA.getEndPoint());
158 
159         final TestLineSegment trimmedB = square.trim(segment);
160         PartitionTestUtils.assertPointsEqual(new TestPoint2D(1, 0.5), trimmedB.getStartPoint());
161         PartitionTestUtils.assertPointsEqual(new TestPoint2D(2, 0.5), trimmedB.getEndPoint());
162     }
163 
164     @Test
165     void testSplit_full() {
166         // arrange
167         final StubRegion region = new StubRegion(Collections.emptyList());
168 
169         final TestLine splitter = TestLine.X_AXIS;
170 
171         // act
172         final Split<StubRegion> split = region.split(splitter);
173 
174         // assert
175         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
176 
177         final StubRegion minus = split.getMinus();
178         Assertions.assertEquals(1, minus.getBoundaries().size());
179         checkClassify(minus, RegionLocation.INSIDE, new TestPoint2D(0, 1));
180         checkClassify(minus, RegionLocation.BOUNDARY, new TestPoint2D(0, 0));
181         checkClassify(minus, RegionLocation.OUTSIDE, new TestPoint2D(0, -1));
182 
183         final StubRegion plus = split.getPlus();
184         Assertions.assertEquals(1, plus.getBoundaries().size());
185         checkClassify(plus, RegionLocation.OUTSIDE, new TestPoint2D(0, 1));
186         checkClassify(plus, RegionLocation.BOUNDARY, new TestPoint2D(0, 0));
187         checkClassify(plus, RegionLocation.INSIDE, new TestPoint2D(0, -1));
188     }
189 
190     @Test
191     void testSplit_parallel_splitterIsOutside_plusOnly() {
192      // arrange
193         final StubRegion region = new StubRegion(
194                 Collections.singletonList(new TestLineSegment(new TestPoint2D(0, 1), new TestPoint2D(1, 1))));
195 
196         final TestLine splitter = TestLine.X_AXIS.reverse();
197 
198         // act
199         final Split<StubRegion> split = region.split(splitter);
200 
201         // assert
202         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
203 
204         Assertions.assertNull(split.getMinus());
205         Assertions.assertSame(region, split.getPlus());
206     }
207 
208     @Test
209     void testSplit_parallel_splitterIsOutside_minusOnly() {
210      // arrange
211         final StubRegion region = new StubRegion(
212                 Collections.singletonList(new TestLineSegment(new TestPoint2D(0, 1), new TestPoint2D(1, 1))));
213 
214         final TestLine splitter = TestLine.X_AXIS;
215 
216         // act
217         final Split<StubRegion> split = region.split(splitter);
218 
219         // assert
220         Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
221 
222         Assertions.assertSame(region, split.getMinus());
223         Assertions.assertNull(split.getPlus());
224     }
225 
226     @Test
227     void testSplit_parallel_splitterIsInside() {
228      // arrange
229         final StubRegion region = new StubRegion(
230                 Collections.singletonList(new TestLineSegment(new TestPoint2D(1, 1), new TestPoint2D(0, 1))));
231 
232         final TestLine splitter = TestLine.X_AXIS;
233 
234         // act
235         final Split<StubRegion> split = region.split(splitter);
236 
237         // assert
238         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
239 
240         final TestPoint2D p1 = new TestPoint2D(0, 1.5);
241         final TestPoint2D p2 = new TestPoint2D(0, 0.5);
242         final TestPoint2D p3 = new TestPoint2D(0, -0.5);
243 
244         final StubRegion minus = split.getMinus();
245         Assertions.assertEquals(2, minus.getBoundaries().size());
246         checkClassify(minus, RegionLocation.INSIDE, p2);
247         checkClassify(minus, RegionLocation.OUTSIDE, p1, p3);
248 
249         final StubRegion plus = split.getPlus();
250         Assertions.assertEquals(1, plus.getBoundaries().size());
251         checkClassify(plus, RegionLocation.INSIDE, p3);
252         checkClassify(plus, RegionLocation.OUTSIDE, p1, p2);
253     }
254 
255     @Test
256     void testSplit_coincident_sameOrientation() {
257      // arrange
258         final StubRegion region = new StubRegion(Collections.singletonList(TestLine.X_AXIS.span()));
259 
260         final TestLine splitter = TestLine.X_AXIS;
261 
262         // act
263         final Split<StubRegion> split = region.split(splitter);
264 
265         // assert
266         Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
267 
268         Assertions.assertSame(region, split.getMinus());
269         Assertions.assertNull(split.getPlus());
270     }
271 
272     @Test
273     void testSplit_coincident_oppositeOrientation() {
274      // arrange
275         final StubRegion region = new StubRegion(Collections.singletonList(TestLine.X_AXIS.span()));
276 
277         final TestLine splitter = TestLine.X_AXIS.reverse();
278 
279         // act
280         final Split<StubRegion> split = region.split(splitter);
281 
282         // assert
283         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
284 
285         Assertions.assertNull(split.getMinus());
286         Assertions.assertSame(region, split.getPlus());
287     }
288 
289     @Test
290     void testSplit_finite_both() {
291         // arrange
292         final TestPoint2D p1 = new TestPoint2D(1, -0.5);
293         final TestPoint2D p2 = new TestPoint2D(2, -0.5);
294         final TestPoint2D p3 = new TestPoint2D(2, 0.5);
295         final TestPoint2D p4 = new TestPoint2D(1, 0.5);
296 
297         final StubRegion region = new StubRegion(Arrays.asList(
298                     new TestLineSegment(p1, p2),
299                     new TestLineSegment(p2, p3),
300                     new TestLineSegment(p3, p4),
301                     new TestLineSegment(p4, p1)
302                 ));
303 
304         final TestLine splitter = TestLine.X_AXIS;
305 
306         // act
307         final Split<StubRegion> split = region.split(splitter);
308 
309         // assert
310         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
311 
312         final StubRegion minus = split.getMinus();
313         Assertions.assertEquals(4, minus.getBoundaries().size());
314         checkClassify(minus, RegionLocation.INSIDE, new TestPoint2D(1.5, 0.25));
315         checkClassify(minus, RegionLocation.BOUNDARY, new TestPoint2D(1.5, 0));
316         checkClassify(minus, RegionLocation.OUTSIDE, new TestPoint2D(1.5, -0.25));
317 
318         final StubRegion plus = split.getPlus();
319         Assertions.assertEquals(4, plus.getBoundaries().size());
320         checkClassify(plus, RegionLocation.OUTSIDE, new TestPoint2D(1.5, 0.25));
321         checkClassify(plus, RegionLocation.BOUNDARY, new TestPoint2D(1.5, 0));
322         checkClassify(plus, RegionLocation.INSIDE, new TestPoint2D(1.5, -0.25));
323     }
324 
325     // The following tests are designed to check the situation where there are
326     // inconsistencies between how a splitter splits a set of boundaries and how
327     // the boundaries split the splitter. For example, no portion of the splitter
328     // may lie inside the region (on the minus sides of all boundaries), but some
329     // of the boundaries may be determined to lie on both sides of the splitter.
330     // One potential cause of this situation is accumulated floating point errors.
331 
332     @Test
333     void testSplit_inconsistentBoundarySplitLocations_minus() {
334         // arrange
335         final TestLine a = new TestLine(new TestPoint2D(0, 0), new TestPoint2D(1, 1));
336         final TestLine b = new TestLine(new TestPoint2D(-1, 1), new TestPoint2D(0, 0));
337 
338         final StubRegion region = new StubRegion(Arrays.asList(
339                     new TestLineSegment(-1e-8, Double.POSITIVE_INFINITY, a),
340                     new TestLineSegment(Double.NEGATIVE_INFINITY, 1e-8, b)
341                 ));
342 
343         final List<TestLineSegment> segments = region.getBoundaries();
344         PartitionTestUtils.assertPointsEqual(segments.get(0).getStartPoint(), segments.get(1).getEndPoint());
345 
346         final TestLine splitter = new TestLine(new TestPoint2D(0, 0), new TestPoint2D(1, 0));
347 
348         // act
349         final Split<StubRegion> split = region.split(splitter);
350 
351         // assert
352         Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
353         Assertions.assertSame(region, split.getMinus());
354         Assertions.assertNull(split.getPlus());
355     }
356 
357     @Test
358     void testSplit_inconsistentBoundarySplitLocations_plus() {
359         // arrange
360         final TestLine a = new TestLine(new TestPoint2D(0, 0), new TestPoint2D(1, 1));
361         final TestLine b = new TestLine(new TestPoint2D(-1, 1), new TestPoint2D(0, 0));
362 
363         final StubRegion region = new StubRegion(Arrays.asList(
364                     new TestLineSegment(-1e-8, Double.POSITIVE_INFINITY, a),
365                     new TestLineSegment(Double.NEGATIVE_INFINITY, 1e-8, b)
366                 ));
367 
368         final List<TestLineSegment> segments = region.getBoundaries();
369         PartitionTestUtils.assertPointsEqual(segments.get(0).getStartPoint(), segments.get(1).getEndPoint());
370 
371         final TestLine splitter = new TestLine(new TestPoint2D(1, 0), new TestPoint2D(0, 0));
372 
373         // act
374         final Split<StubRegion> split = region.split(splitter);
375 
376         // assert
377         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
378         Assertions.assertNull(split.getMinus());
379         Assertions.assertSame(region, split.getPlus());
380     }
381 
382     @Test
383     void testSplit_inconsistentBoundarySplitLocations_trimmedNotNull_minus() {
384         // arrange
385         final TestLine a = new TestLine(new TestPoint2D(1e-8, 0), new TestPoint2D(1, 1));
386         final TestLine b = new TestLine(new TestPoint2D(-1, 1), new TestPoint2D(-1e-8, 0));
387 
388         final StubRegion region = new StubRegion(Arrays.asList(
389                     new TestLineSegment(1e-8, Double.POSITIVE_INFINITY, a),
390                     new TestLineSegment(Double.NEGATIVE_INFINITY, -1e-8, b)
391                 ));
392 
393         final List<TestLineSegment> segments = region.getBoundaries();
394         PartitionTestUtils.assertPointsEqual(segments.get(0).getStartPoint(), segments.get(1).getEndPoint());
395 
396         final TestLine splitter = new TestLine(new TestPoint2D(0, 0), new TestPoint2D(1, 0));
397 
398         // act
399         final Split<StubRegion> split = region.split(splitter);
400 
401         // assert
402         Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
403         Assertions.assertSame(region, split.getMinus());
404         Assertions.assertNull(split.getPlus());
405     }
406 
407     @Test
408     void testSplit_inconsistentBoundarySplitLocations_trimmedNotNull_plus() {
409         // arrange
410         final TestLine a = new TestLine(new TestPoint2D(1e-8, 0), new TestPoint2D(1, 1));
411         final TestLine b = new TestLine(new TestPoint2D(-1, 1), new TestPoint2D(-1e-8, 0));
412 
413         final StubRegion region = new StubRegion(Arrays.asList(
414                     new TestLineSegment(1e-8, Double.POSITIVE_INFINITY, a),
415                     new TestLineSegment(Double.NEGATIVE_INFINITY, -1e-8, b)
416                 ));
417 
418         final List<TestLineSegment> segments = region.getBoundaries();
419         PartitionTestUtils.assertPointsEqual(segments.get(0).getStartPoint(), segments.get(1).getEndPoint());
420 
421         final TestLine splitter = new TestLine(new TestPoint2D(0, 0), new TestPoint2D(-1, 0));
422 
423         // act
424         final Split<StubRegion> split = region.split(splitter);
425 
426         // assert
427         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
428         Assertions.assertNull(split.getMinus());
429         Assertions.assertSame(region, split.getPlus());
430     }
431 
432     @Test
433     void testSplit_inconsistentBoundarySplitLocations_trimmedNotNull_neither() {
434         // arrange
435         final TestLine a = new TestLine(new TestPoint2D(1e-8, 0), new TestPoint2D(1, 1));
436         final TestLine b = new TestLine(new TestPoint2D(-1, 1), new TestPoint2D(-1e-8, 0));
437 
438         final StubRegion region = new StubRegion(Arrays.asList(
439                     new TestLineSegment(0, 0, a),
440                     new TestLineSegment(0, 0, b)
441                 ));
442 
443         final List<TestLineSegment> segments = region.getBoundaries();
444         PartitionTestUtils.assertPointsEqual(segments.get(0).getStartPoint(), segments.get(1).getEndPoint());
445 
446         final TestLine splitter = new TestLine(new TestPoint2D(0, 0), new TestPoint2D(1, 0));
447 
448         // act
449         final Split<StubRegion> split = region.split(splitter);
450 
451         // assert
452         Assertions.assertEquals(SplitLocation.NEITHER, split.getLocation());
453         Assertions.assertNull(split.getMinus());
454         Assertions.assertNull(split.getPlus());
455     }
456 
457     @Test
458     void testTransform_full() {
459         // arrange
460         final StubRegion region = new StubRegion(Collections.emptyList());
461 
462         final Transform<TestPoint2D> transform = new TestTransform2D(p -> new TestPoint2D(p.getX() + 1, p.getY() + 2));
463 
464         // act
465         final StubRegion transformed = region.transform(transform);
466 
467         // assert
468         Assertions.assertTrue(transformed.isFull());
469         Assertions.assertFalse(transformed.isEmpty());
470     }
471 
472     @Test
473     void testTransform_infinite() {
474         // arrange
475         final TestLine line = TestLine.Y_AXIS;
476 
477         final StubRegion region = new StubRegion(Collections.singletonList(line.span()));
478 
479         final Transform<TestPoint2D> transform = new TestTransform2D(p -> new TestPoint2D(p.getX() + 1, p.getY() + 2));
480 
481         // act
482         final StubRegion transformed = region.transform(transform);
483 
484         // assert
485         final List<TestLineSegment> boundaries = transformed.getBoundaries();
486 
487         Assertions.assertEquals(1, boundaries.size());
488 
489         final TestLineSegment a = boundaries.get(0);
490         final TestLine aLine = a.getHyperplane();
491         PartitionTestUtils.assertPointsEqual(aLine.getOrigin(), new TestPoint2D(1, 0));
492         Assertions.assertEquals(0.0, aLine.getDirectionX(), PartitionTestUtils.EPS);
493         Assertions.assertEquals(1.0, aLine.getDirectionY(), PartitionTestUtils.EPS);
494 
495         GeometryTestUtils.assertNegativeInfinity(a.getStart());
496         GeometryTestUtils.assertPositiveInfinity(a.getEnd());
497     }
498 
499     @Test
500     void testTransform_finite() {
501         // arrange
502         final TestPoint2D p1 = new TestPoint2D(1, 0);
503         final TestPoint2D p2 = new TestPoint2D(2, 0);
504         final TestPoint2D p3 = new TestPoint2D(1, 1);
505 
506         final StubRegion region = new StubRegion(Arrays.asList(
507                 new TestLineSegment(p1, p2),
508                 new TestLineSegment(p2, p3),
509                 new TestLineSegment(p3, p1)
510             ));
511 
512         final Transform<TestPoint2D> transform = new TestTransform2D(p -> new TestPoint2D(p.getX() + 1, p.getY() + 2));
513 
514         // act
515         final StubRegion transformed = region.transform(transform);
516 
517         // assert
518         final List<TestLineSegment> boundaries = transformed.getBoundaries();
519 
520         Assertions.assertEquals(3, boundaries.size());
521 
522         final TestLineSegment a = boundaries.get(0);
523         PartitionTestUtils.assertPointsEqual(new TestPoint2D(2, 2), a.getStartPoint());
524         PartitionTestUtils.assertPointsEqual(new TestPoint2D(3, 2), a.getEndPoint());
525 
526         final TestLineSegment b = boundaries.get(1);
527         PartitionTestUtils.assertPointsEqual(new TestPoint2D(3, 2), b.getStartPoint());
528         PartitionTestUtils.assertPointsEqual(new TestPoint2D(2, 3), b.getEndPoint());
529 
530         final TestLineSegment c = boundaries.get(2);
531         PartitionTestUtils.assertPointsEqual(new TestPoint2D(2, 3), c.getStartPoint());
532         PartitionTestUtils.assertPointsEqual(new TestPoint2D(2, 2), c.getEndPoint());
533     }
534 
535     @Test
536     void testTransform_reflection() {
537         // arrange
538         final TestPoint2D p1 = new TestPoint2D(1, 0);
539         final TestPoint2D p2 = new TestPoint2D(2, 0);
540         final TestPoint2D p3 = new TestPoint2D(1, 1);
541 
542         final StubRegion region = new StubRegion(Arrays.asList(
543                 new TestLineSegment(p1, p2),
544                 new TestLineSegment(p2, p3),
545                 new TestLineSegment(p3, p1)
546             ));
547 
548         final Transform<TestPoint2D> transform = new TestTransform2D(p -> new TestPoint2D(-p.getX(), p.getY()));
549 
550         // act
551         final StubRegion transformed = region.transform(transform);
552 
553         // assert
554         final List<TestLineSegment> boundaries = transformed.getBoundaries();
555 
556         Assertions.assertEquals(3, boundaries.size());
557 
558         final TestLineSegment a = boundaries.get(0);
559         PartitionTestUtils.assertPointsEqual(new TestPoint2D(-2, 0), a.getStartPoint());
560         PartitionTestUtils.assertPointsEqual(new TestPoint2D(-1, 0), a.getEndPoint());
561 
562         final TestLineSegment b = boundaries.get(1);
563         PartitionTestUtils.assertPointsEqual(new TestPoint2D(-1, 1), b.getStartPoint());
564         PartitionTestUtils.assertPointsEqual(new TestPoint2D(-2, 0), b.getEndPoint());
565 
566         final TestLineSegment c = boundaries.get(2);
567         PartitionTestUtils.assertPointsEqual(new TestPoint2D(-1, 0), c.getStartPoint());
568         PartitionTestUtils.assertPointsEqual(new TestPoint2D(-1, 1), c.getEndPoint());
569     }
570 
571     @Test
572     void testConvexRegionBoundaryBuilder_full() {
573         // act
574         final StubRegion region = StubRegion.fromBounds(Collections.emptyList());
575 
576         // assert
577         Assertions.assertSame(StubRegion.FULL, region);
578     }
579 
580     @Test
581     void testConvexRegionBoundaryBuilder_singleLine() {
582         // act
583         final StubRegion region = StubRegion.fromBounds(Collections.singletonList(TestLine.Y_AXIS));
584 
585         // assert
586         Assertions.assertEquals(1, region.getBoundaries().size());
587 
588         checkClassify(region, RegionLocation.INSIDE, new TestPoint2D(-1, 0));
589         checkClassify(region, RegionLocation.BOUNDARY, new TestPoint2D(0, 0));
590         checkClassify(region, RegionLocation.OUTSIDE, new TestPoint2D(1, 0));
591     }
592 
593     @Test
594     void testConvexRegionBoundaryBuilder_multipleLines() {
595         // act
596         final StubRegion region = StubRegion.fromBounds(Arrays.asList(
597                     TestLine.X_AXIS,
598                     new TestLine(new TestPoint2D(1, 0), new TestPoint2D(0, 1)),
599                     TestLine.Y_AXIS.reverse()
600                 ));
601 
602         // assert
603         Assertions.assertEquals(3, region.getBoundaries().size());
604 
605         checkClassify(region, RegionLocation.INSIDE, new TestPoint2D(0.25, 0.25));
606 
607         checkClassify(region, RegionLocation.BOUNDARY,
608                 TestPoint2D.ZERO, new TestPoint2D(1, 0), new TestPoint2D(1, 0), new TestPoint2D(0.5, 0.5));
609 
610         checkClassify(region, RegionLocation.OUTSIDE,
611                 new TestPoint2D(-1, 0.5), new TestPoint2D(1, 0.5),
612                 new TestPoint2D(0.5, 1), new TestPoint2D(0.5, -1));
613     }
614 
615     @Test
616     void testConvexRegionBoundaryBuilder_duplicateLines() {
617         // act
618         final StubRegion region = StubRegion.fromBounds(Arrays.asList(
619                 TestLine.Y_AXIS,
620                 TestLine.Y_AXIS,
621                 new TestLine(new TestPoint2D(0, 0), new TestPoint2D(0, 1)),
622                 TestLine.Y_AXIS));
623 
624         // assert
625         Assertions.assertEquals(1, region.getBoundaries().size());
626 
627         checkClassify(region, RegionLocation.INSIDE, new TestPoint2D(-1, 0));
628         checkClassify(region, RegionLocation.BOUNDARY, new TestPoint2D(0, 0));
629         checkClassify(region, RegionLocation.OUTSIDE, new TestPoint2D(1, 0));
630     }
631 
632     @Test
633     void testConvexRegionBoundaryBuilder() {
634         // arrange
635         final List<TestLine> opposites = Arrays.asList(TestLine.X_AXIS, TestLine.X_AXIS.reverse());
636         final List<TestLine> nonConvex = Arrays.asList(
637                 TestLine.X_AXIS,
638                 TestLine.Y_AXIS,
639                 new TestLine(new TestPoint2D(1, 0), new TestPoint2D(0, -1)),
640                 new TestLine(new TestPoint2D(1, 0), new TestPoint2D(0, -2)));
641 
642         // act/assert
643         Assertions.assertThrows(IllegalArgumentException.class, () -> StubRegion.fromBounds(opposites));
644         Assertions.assertThrows(IllegalArgumentException.class, () -> StubRegion.fromBounds(nonConvex));
645     }
646 
647     @Test
648     void testToString() {
649         // arrange
650         final StubRegion region = new StubRegion(Collections.emptyList());
651 
652         // act
653         final String str = region.toString();
654 
655         // assert
656         Assertions.assertEquals("StubRegion[boundaries= []]", str);
657     }
658 
659     private static void checkClassify(final Region<TestPoint2D> region, final RegionLocation loc, final TestPoint2D... pts) {
660         for (final TestPoint2D pt : pts) {
661             Assertions.assertEquals(loc, region.classify(pt), "Unexpected location for point " + pt);
662         }
663     }
664 
665     private static final class StubRegion extends AbstractConvexHyperplaneBoundedRegion<TestPoint2D, TestLineSegment> {
666 
667         private static final StubRegion FULL = new StubRegion(Collections.emptyList());
668 
669         StubRegion(final List<TestLineSegment> boundaries) {
670             super(boundaries);
671         }
672 
673         public StubRegion transform(final Transform<TestPoint2D> transform) {
674             return transformInternal(transform, this, TestLineSegment.class, StubRegion::new);
675         }
676 
677         @Override
678         public Split<StubRegion> split(final Hyperplane<TestPoint2D> splitter) {
679             return splitInternal(splitter, this, TestLineSegment.class, StubRegion::new);
680         }
681 
682         @Override
683         public TestLineSegment trim(final HyperplaneConvexSubset<TestPoint2D> subset) {
684             return (TestLineSegment) super.trim(subset);
685         }
686 
687         @Override
688         public double getSize() {
689             throw new UnsupportedOperationException();
690         }
691 
692         @Override
693         public TestPoint2D getCentroid() {
694             throw new UnsupportedOperationException();
695         }
696 
697         public static StubRegion fromBounds(final Iterable<TestLine> boundingLines) {
698             final List<TestLineSegment> segments = new ConvexRegionBoundaryBuilder<>(TestLineSegment.class)
699                     .build(boundingLines);
700             return segments.isEmpty() ? FULL : new StubRegion(segments);
701         }
702     }
703 }