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.euclidean.threed;
    18
    19  import java.util.Arrays;
    20  import java.util.List;
    21  import java.util.regex.Pattern;
    22
    23  import org.apache.commons.geometry.core.GeometryTestUtils;
    24  import org.apache.commons.geometry.core.RegionLocation;
    25  import org.apache.commons.geometry.core.Transform;
    26  import org.apache.commons.geometry.core.partitioning.Split;
    27  import org.apache.commons.geometry.core.partitioning.SplitLocation;
    28  import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
    29  import org.apache.commons.geometry.euclidean.threed.rotation.QuaternionRotation;
    30  import org.apache.commons.geometry.euclidean.twod.ConvexArea;
    31  import org.apache.commons.geometry.euclidean.twod.Lines;
    32  import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D;
    33  import org.apache.commons.geometry.euclidean.twod.Vector2D;
    34  import org.apache.commons.geometry.euclidean.twod.shape.Parallelogram;
    35  import org.apache.commons.numbers.angle.Angle;
    36  import org.apache.commons.numbers.core.Precision;
    37  import org.junit.jupiter.api.Assertions;
    38  import org.junit.jupiter.api.Test;
    39
    40  class EmbeddedTreePlaneSubsetTest {
    41
    42      private static final double TEST_EPS = 1e-10;
    43
    44      private static final Precision.DoubleEquivalence TEST_PRECISION =
    45              Precision.doubleEquivalenceOfEpsilon(TEST_EPS);
    46
    47      private static final EmbeddingPlane XY_PLANE = Planes.fromPointAndPlaneVectors(Vector3D.ZERO,
    48              Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    49
    50      @Test
    51      void testCtor_plane() {
    52          // act
    53          final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(XY_PLANE);
    54
    55          // assert
    56          Assertions.assertFalse(ps.isFull());
    57          Assertions.assertTrue(ps.isEmpty());
    58
    59          Assertions.assertEquals(0, ps.getSize(), TEST_EPS);
    60      }
    61
    62      @Test
    63      void testCtor_plane_booleanFalse() {
    64          // act
    65          final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(XY_PLANE, false);
    66
    67          // assert
    68          Assertions.assertFalse(ps.isFull());
    69          Assertions.assertTrue(ps.isEmpty());
    70
    71          Assertions.assertEquals(0, ps.getSize(), TEST_EPS);
    72      }
    73
    74      @Test
    75      void testCtor_plane_booleanTrue() {
    76          // act
    77          final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(XY_PLANE, true);
    78
    79          // assert
    80          Assertions.assertTrue(ps.isFull());
    81          Assertions.assertFalse(ps.isEmpty());
    82
    83          GeometryTestUtils.assertPositiveInfinity(ps.getSize());
    84      }
    85
    86      @Test
    87      void testSpaceConversion() {
    88          // arrange
    89          final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(1, 0, 0),
    90                  Vector3D.Unit.PLUS_Y, Vector3D.Unit.PLUS_Z, TEST_PRECISION);
    91
    92          final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(plane, true);
    93
    94          // act/assert
    95          EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 2), ps.toSubspace(Vector3D.of(-5, 1, 2)), TEST_EPS);
    96          EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, -2, 4), ps.toSpace(Vector2D.of(-2, 4)), TEST_EPS);
    97      }
    98
    99      @Test
    100     void testToConvex_full() {
    101         // act
    102         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(XY_PLANE, true);
    103
    104         // act
    105         final List<PlaneConvexSubset> convex = ps.toConvex();
    106
    107         // assert
    108         Assertions.assertEquals(1, convex.size());
    109         Assertions.assertTrue(convex.get(0).isFull());
    110     }
    111
    112     @Test
    113     void testToConvex_empty() {
    114         // arrange
    115         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(XY_PLANE, false);
    116
    117         // act
    118         final List<PlaneConvexSubset> convex = ps.toConvex();
    119
    120         // assert
    121         Assertions.assertEquals(0, convex.size());
    122     }
    123
    124     @Test
    125     void testToConvex_nonConvexRegion() {
    126         // act
    127         final ConvexArea a = ConvexArea.convexPolygonFromVertices(Arrays.asList(
    128                     Vector2D.of(0, 0), Vector2D.of(1, 0),
    129                     Vector2D.of(1, 1), Vector2D.of(0, 1)
    130                 ), TEST_PRECISION);
    131         final ConvexArea b = ConvexArea.convexPolygonFromVertices(Arrays.asList(
    132                     Vector2D.of(1, 0), Vector2D.of(2, 0),
    133                     Vector2D.of(2, 1), Vector2D.of(1, 1)
    134                 ), TEST_PRECISION);
    135
    136         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(XY_PLANE, false);
    137         ps.add(Planes.subsetFromConvexArea(XY_PLANE, a));
    138         ps.add(Planes.subsetFromConvexArea(XY_PLANE, b));
    139
    140         // act
    141         final List<PlaneConvexSubset> convex = ps.toConvex();
    142
    143         // assert
    144         Assertions.assertEquals(2, convex.size());
    145         Assertions.assertEquals(1, convex.get(0).getSize(), TEST_EPS);
    146         Assertions.assertEquals(1, convex.get(1).getSize(), TEST_EPS);
    147     }
    148
    149     @Test
    150     void testToTriangles_empty() {
    151         // arrange
    152         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(XY_PLANE, false);
    153
    154         // act
    155         final List<Triangle3D> tris = ps.toTriangles();
    156
    157         // assert
    158         Assertions.assertEquals(0, tris.size());
    159     }
    160
    161     @Test
    162     void testToTriangles_infinite() {
    163         // arrange
    164         final Pattern pattern = Pattern.compile("^Cannot convert infinite plane subset to triangles: .*");
    165
    166         // act/assert
    167         GeometryTestUtils.assertThrowsWithMessage(() -> {
    168             new EmbeddedTreePlaneSubset(XY_PLANE, true).toTriangles();
    169         }, IllegalStateException.class, pattern);
    170
    171         GeometryTestUtils.assertThrowsWithMessage(() -> {
    172             final EmbeddedTreePlaneSubset halfSpace = new EmbeddedTreePlaneSubset(XY_PLANE, false);
    173             halfSpace.getSubspaceRegion().getRoot()
    174                 .insertCut(Lines.fromPointAndAngle(Vector2D.ZERO, 0, TEST_PRECISION));
    175
    176             halfSpace.toTriangles();
    177         }, IllegalStateException.class, pattern);
    178
    179         GeometryTestUtils.assertThrowsWithMessage(() -> {
    180             final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    181             tree.insert(Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.of(1, 0), TEST_PRECISION));
    182             tree.insert(Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.of(0, 1), TEST_PRECISION));
    183
    184             final EmbeddedTreePlaneSubset halfSpaceWithVertices = new EmbeddedTreePlaneSubset(XY_PLANE, tree);
    185
    186             halfSpaceWithVertices.toTriangles();
    187         }, IllegalStateException.class, pattern);
    188     }
    189
    190     @Test
    191     void testToTriangles_finite() {
    192         // arrange
    193         final Vector3D p1 = Vector3D.ZERO;
    194         final Vector3D p2 = Vector3D.of(1, 0, 0);
    195         final Vector3D p3 = Vector3D.of(2, 1, 0);
    196         final Vector3D p4 = Vector3D.of(1.5, 1, 0);
    197
    198         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(XY_PLANE);
    199         ps.add(Planes.convexPolygonFromVertices(Arrays.asList(
    200                     p1, p2, p3, p4
    201                 ), TEST_PRECISION));
    202
    203         // act
    204         final List<Triangle3D> tris = ps.toTriangles();
    205
    206         // assert
    207         Assertions.assertEquals(2, tris.size());
    208
    209         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p4, p1, p2),
    210                 tris.get(0).getVertices(), TEST_PRECISION);
    211         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p4, p2, p3),
    212                 tris.get(1).getVertices(), TEST_PRECISION);
    213     }
    214
    215     @Test
    216     void testToTriangles_finite_disjoint() {
    217         // arrange
    218         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(XY_PLANE);
    219         ps.add(Planes.convexPolygonFromVertices(Arrays.asList(
    220                     Vector3D.ZERO, Vector3D.of(1, 0, 0),
    221                     Vector3D.of(2, 1, 0), Vector3D.of(1.5, 1, 0)
    222                 ), TEST_PRECISION));
    223
    224         ps.add(Planes.convexPolygonFromVertices(Arrays.asList(
    225                 Vector3D.of(-1, -1, 0), Vector3D.of(0, -1, 0), Vector3D.of(-1, 0, 0)
    226             ), TEST_PRECISION));
    227
    228         // act
    229         final List<Triangle3D> tris = ps.toTriangles();
    230
    231         // assert
    232         Assertions.assertEquals(3, tris.size());
    233     }
    234
    235     @Test
    236     void testGetBounds_noBounds() {
    237         // arrange
    238         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
    239                 Vector3D.Unit.PLUS_Y, Vector3D.Unit.MINUS_X, TEST_PRECISION);
    240
    241         final EmbeddedTreePlaneSubset full = new EmbeddedTreePlaneSubset(plane, true);
    242         final EmbeddedTreePlaneSubset empty = new EmbeddedTreePlaneSubset(plane, false);
    243
    244         final EmbeddedTreePlaneSubset halfPlane = new EmbeddedTreePlaneSubset(plane, false);
    245         halfPlane.getSubspaceRegion().getRoot().insertCut(Lines.fromPointAndAngle(Vector2D.ZERO, 0, TEST_PRECISION));
    246
    247         // act/assert
    248         Assertions.assertNull(full.getBounds());
    249         Assertions.assertNull(empty.getBounds());
    250         Assertions.assertNull(halfPlane.getBounds());
    251     }
    252
    253     @Test
    254     void testGetBounds_hasBounds() {
    255         // arrange
    256         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
    257                 Vector3D.Unit.PLUS_Y, Vector3D.Unit.MINUS_X, TEST_PRECISION);
    258
    259         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(plane, false);
    260         ps.getSubspaceRegion().add(ConvexArea.convexPolygonFromVertices(Arrays.asList(
    261                     Vector2D.of(1, 1), Vector2D.of(2, 1), Vector2D.of(1, 2)
    262                 ), TEST_PRECISION));
    263
    264         // act
    265         final Bounds3D bounds = ps.getBounds();
    266
    267         // assert
    268         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(-2, 1, 1), bounds.getMin(), TEST_EPS);
    269         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(-1, 2, 1), bounds.getMax(), TEST_EPS);
    270     }
    271
    272     @Test
    273     void testSplit_empty() {
    274         // arrange
    275         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(XY_PLANE, false);
    276
    277         final Plane splitter = Planes.fromNormal(Vector3D.Unit.PLUS_X, TEST_PRECISION);
    278
    279         // act
    280         final Split<EmbeddedTreePlaneSubset> split = ps.split(splitter);
    281
    282         // assert
    283         Assertions.assertEquals(SplitLocation.NEITHER, split.getLocation());
    284
    285         Assertions.assertNull(split.getMinus());
    286         Assertions.assertNull(split.getPlus());
    287     }
    288
    289     @Test
    290     void testSplit_halfSpace() {
    291         // arrange
    292         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(XY_PLANE, false);
    293         ps.getSubspaceRegion().getRoot().cut(
    294                 Lines.fromPointAndAngle(Vector2D.ZERO, 0.0, TEST_PRECISION));
    295
    296         final Plane splitter = Planes.fromNormal(Vector3D.Unit.PLUS_X, TEST_PRECISION);
    297
    298         // act
    299         final Split<EmbeddedTreePlaneSubset> split = ps.split(splitter);
    300
    301         // assert
    302         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
    303
    304         final EmbeddedTreePlaneSubset minus = split.getMinus();
    305         checkPoints(minus, RegionLocation.INSIDE, Vector3D.of(-1, 1, 0));
    306         checkPoints(minus, RegionLocation.OUTSIDE, Vector3D.of(1, 1, 0), Vector3D.of(0, -1, 0));
    307
    308         final EmbeddedTreePlaneSubset plus = split.getPlus();
    309         checkPoints(plus, RegionLocation.OUTSIDE, Vector3D.of(-1, 1, 0), Vector3D.of(0, -1, 0));
    310         checkPoints(plus, RegionLocation.INSIDE, Vector3D.of(1, 1, 0));
    311     }
    312
    313     @Test
    314     void testSplit_both() {
    315         // arrange
    316         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(XY_PLANE, false);
    317         ps.getSubspaceRegion().union(
    318                 Parallelogram.axisAligned(Vector2D.of(-1, -1), Vector2D.of(1, 1), TEST_PRECISION).toTree());
    319
    320         final Plane splitter = Planes.fromNormal(Vector3D.Unit.PLUS_X, TEST_PRECISION);
    321
    322         // act
    323         final Split<EmbeddedTreePlaneSubset> split = ps.split(splitter);
    324
    325         // assert
    326         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
    327
    328         final EmbeddedTreePlaneSubset minus = split.getMinus();
    329         checkPoints(minus, RegionLocation.INSIDE, Vector3D.of(-0.5, 0, 0));
    330         checkPoints(minus, RegionLocation.OUTSIDE,
    331                 Vector3D.of(0.5, 0, 0), Vector3D.of(1.5, 0, 0),
    332                 Vector3D.of(0, 1.5, 0), Vector3D.of(0, -1.5, 0));
    333
    334         final EmbeddedTreePlaneSubset plus = split.getPlus();
    335         checkPoints(plus, RegionLocation.INSIDE, Vector3D.of(0.5, 0, 0));
    336         checkPoints(plus, RegionLocation.OUTSIDE,
    337                 Vector3D.of(-0.5, 0, 0), Vector3D.of(1.5, 0, 0),
    338                 Vector3D.of(0, 1.5, 0), Vector3D.of(0, -1.5, 0));
    339     }
    340
    341     @Test
    342     void testSplit_intersects_plusOnly() {
    343         // arrange
    344         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(XY_PLANE, false);
    345         ps.getSubspaceRegion().union(
    346                 Parallelogram.axisAligned(Vector2D.of(-1, -1), Vector2D.of(1, 1), TEST_PRECISION).toTree());
    347
    348         final Plane splitter = Planes.fromPointAndNormal(Vector3D.of(0, 0, 1), Vector3D.of(0.1, 0, 1), TEST_PRECISION);
    349
    350         // act
    351         final Split<EmbeddedTreePlaneSubset> split = ps.split(splitter);
    352
    353         // assert
    354         Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
    355
    356         Assertions.assertSame(ps, split.getMinus());
    357         Assertions.assertNull(split.getPlus());
    358     }
    359
    360     @Test
    361     void testSplit_intersects_minusOnly() {
    362         // arrange
    363         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(XY_PLANE, false);
    364         ps.getSubspaceRegion().union(
    365                 Parallelogram.axisAligned(Vector2D.of(-1, -1), Vector2D.of(1, 1), TEST_PRECISION).toTree());
    366
    367         final Plane splitter = Planes.fromPointAndNormal(Vector3D.of(0, 0, 1), Vector3D.of(0.1, 0, -1), TEST_PRECISION);
    368
    369         // act
    370         final Split<EmbeddedTreePlaneSubset> split = ps.split(splitter);
    371
    372         // assert
    373         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
    374
    375         Assertions.assertNull(split.getMinus());
    376         Assertions.assertSame(ps, split.getPlus());
    377     }
    378
    379     @Test
    380     void testSplit_parallel_plusOnly() {
    381         // arrange
    382         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(XY_PLANE, false);
    383         ps.getSubspaceRegion().union(
    384                 Parallelogram.axisAligned(Vector2D.of(-1, -1), Vector2D.of(1, 1), TEST_PRECISION).toTree());
    385
    386         final Plane splitter = Planes.fromPointAndNormal(Vector3D.of(0, 0, 1), Vector3D.Unit.PLUS_Z, TEST_PRECISION);
    387
    388         // act
    389         final Split<EmbeddedTreePlaneSubset> split = ps.split(splitter);
    390
    391         // assert
    392         Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
    393
    394         Assertions.assertSame(ps, split.getMinus());
    395         Assertions.assertNull(split.getPlus());
    396     }
    397
    398     @Test
    399     void testSplit_parallel_minusOnly() {
    400         // arrange
    401         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(XY_PLANE, false);
    402         ps.getSubspaceRegion().union(
    403                 Parallelogram.axisAligned(Vector2D.of(-1, -1), Vector2D.of(1, 1), TEST_PRECISION).toTree());
    404
    405         final Plane splitter = Planes.fromPointAndNormal(Vector3D.of(0, 0, 1), Vector3D.Unit.MINUS_Z, TEST_PRECISION);
    406
    407         // act
    408         final Split<EmbeddedTreePlaneSubset> split = ps.split(splitter);
    409
    410         // assert
    411         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
    412
    413         Assertions.assertNull(split.getMinus());
    414         Assertions.assertSame(ps, split.getPlus());
    415     }
    416
    417     @Test
    418     void testSplit_coincident() {
    419         // arrange
    420         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(XY_PLANE, false);
    421         ps.getSubspaceRegion().union(
    422                 Parallelogram.axisAligned(Vector2D.of(-1, -1), Vector2D.of(1, 1), TEST_PRECISION).toTree());
    423
    424         // act
    425         final Split<EmbeddedTreePlaneSubset> split = ps.split(ps.getPlane());
    426
    427         // assert
    428         Assertions.assertEquals(SplitLocation.NEITHER, split.getLocation());
    429
    430         Assertions.assertNull(split.getMinus());
    431         Assertions.assertNull(split.getPlus());
    432     }
    433
    434     @Test
    435     void testTransform_empty() {
    436         // arrange
    437         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(XY_PLANE, false);
    438
    439         final AffineTransformMatrix3D transform = AffineTransformMatrix3D.createTranslation(Vector3D.Unit.PLUS_Z);
    440
    441         // act
    442         final EmbeddedTreePlaneSubset result = ps.transform(transform);
    443
    444         // assert
    445         Assertions.assertNotSame(ps, result);
    446
    447         final Plane resultPlane = result.getPlane();
    448         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 1), resultPlane.getOrigin(), TEST_EPS);
    449         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.PLUS_Z, resultPlane.getNormal(), TEST_EPS);
    450
    451         Assertions.assertFalse(result.isFull());
    452         Assertions.assertTrue(result.isEmpty());
    453     }
    454
    455     @Test
    456     void testTransform_full() {
    457         // arrange
    458         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(XY_PLANE, true);
    459
    460         final AffineTransformMatrix3D transform = AffineTransformMatrix3D.createTranslation(Vector3D.Unit.PLUS_Z);
    461
    462         // act
    463         final EmbeddedTreePlaneSubset result = ps.transform(transform);
    464
    465         // assert
    466         Assertions.assertNotSame(ps, result);
    467
    468         final Plane resultPlane = result.getPlane();
    469         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 1), resultPlane.getOrigin(), TEST_EPS);
    470         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.PLUS_Z, resultPlane.getNormal(), TEST_EPS);
    471
    472         Assertions.assertTrue(result.isFull());
    473         Assertions.assertFalse(result.isEmpty());
    474     }
    475
    476     @Test
    477     void testTransform() {
    478         // arrange
    479         final ConvexArea area = ConvexArea.convexPolygonFromVertices(
    480                 Arrays.asList(Vector2D.ZERO, Vector2D.Unit.PLUS_X, Vector2D.Unit.PLUS_Y), TEST_PRECISION);
    481         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1), Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    482
    483         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(plane, area.toTree());
    484
    485         final Transform<Vector3D> transform = AffineTransformMatrix3D.identity()
    486                 .rotate(QuaternionRotation.fromAxisAngle(Vector3D.Unit.PLUS_Y, Angle.PI_OVER_TWO))
    487                 .translate(Vector3D.of(1, 0, 0));
    488
    489         // act
    490         final EmbeddedTreePlaneSubset result = ps.transform(transform);
    491
    492         // assert
    493         Assertions.assertNotSame(ps, result);
    494
    495         final Plane resultPlane = result.getPlane();
    496         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(2, 0, 0), resultPlane.getOrigin(), TEST_EPS);
    497         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.PLUS_X, resultPlane.getNormal(), TEST_EPS);
    498
    499         checkPoints(result, RegionLocation.INSIDE, Vector3D.of(2, 0.25, -0.25));
    500         checkPoints(result, RegionLocation.OUTSIDE, Vector3D.of(1, 0.25, -0.25), Vector3D.of(3, 0.25, -0.25));
    501
    502         checkPoints(result, RegionLocation.BOUNDARY,
    503                 Vector3D.of(2, 0, 0), Vector3D.of(2, 0, -1), Vector3D.of(2, 1, 0));
    504     }
    505
    506     @Test
    507     void testTransform_reflection() {
    508         // arrange
    509         final ConvexArea area = ConvexArea.convexPolygonFromVertices(
    510                 Arrays.asList(Vector2D.ZERO, Vector2D.Unit.PLUS_X, Vector2D.Unit.PLUS_Y), TEST_PRECISION);
    511         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1), Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    512
    513         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(plane, area.toTree());
    514
    515         final Transform<Vector3D> transform = AffineTransformMatrix3D.createScale(-1, 1, 1);
    516
    517         // act
    518         final EmbeddedTreePlaneSubset result = ps.transform(transform);
    519
    520         // assert
    521         Assertions.assertNotSame(ps, result);
    522
    523         final Plane resultPlane = result.getPlane();
    524         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 1), resultPlane.getOrigin(), TEST_EPS);
    525         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.MINUS_Z, resultPlane.getNormal(), TEST_EPS);
    526
    527         checkPoints(result, RegionLocation.INSIDE, Vector3D.of(-0.25, 0.25, 1));
    528         checkPoints(result, RegionLocation.OUTSIDE, Vector3D.of(0.25, 0.25, 0), Vector3D.of(0.25, 0.25, 2));
    529
    530         checkPoints(result, RegionLocation.BOUNDARY,
    531                 Vector3D.of(-1, 0, 1), Vector3D.of(0, 1, 1), Vector3D.of(0, 0, 1));
    532     }
    533
    534     @Test
    535     void testAddMethods() {
    536         // arrange
    537         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(
    538                 Vector3D.of(0, 0, 1), Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    539         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(plane, false);
    540
    541         // act
    542         ps.add(Planes.subsetFromConvexArea(plane, ConvexArea.convexPolygonFromVertices(Arrays.asList(
    543                     Vector2D.ZERO, Vector2D.of(1, 0), Vector2D.of(0, 1)
    544                 ), TEST_PRECISION)));
    545
    546         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    547         tree.add(ConvexArea.convexPolygonFromVertices(Arrays.asList(
    548                     Vector2D.of(1, 0), Vector2D.of(1, 1), Vector2D.of(0, 1)
    549                 ), TEST_PRECISION));
    550         ps.add(new EmbeddedTreePlaneSubset(plane, tree));
    551
    552         // assert
    553         Assertions.assertFalse(ps.isFull());
    554         Assertions.assertFalse(ps.isEmpty());
    555         Assertions.assertTrue(ps.isFinite());
    556         Assertions.assertFalse(ps.isInfinite());
    557
    558         Assertions.assertEquals(1, ps.getSize(), TEST_EPS);
    559
    560         checkPoints(ps, RegionLocation.INSIDE, Vector3D.of(0.5, 0.5, 1));
    561         checkPoints(ps, RegionLocation.BOUNDARY,
    562                 Vector3D.of(0, 0, 1), Vector3D.of(1, 0, 1),
    563                 Vector3D.of(1, 1, 1), Vector3D.of(0, 1, 1));
    564         checkPoints(ps, RegionLocation.OUTSIDE,
    565                 Vector3D.of(0.5, 0.5, 0), Vector3D.of(0.5, 0.5, 2),
    566                 Vector3D.of(-0.5, 0.5, 1), Vector3D.of(0.5, -0.5, 1),
    567                 Vector3D.of(1.5, 0.5, 1), Vector3D.of(0.5, 1.5, 1));
    568     }
    569
    570     @Test
    571     void testAddMethods_rotatesEquivalentPlanesWithDifferentUAndV() {
    572         // arrange
    573         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(
    574                 Vector3D.of(0, 0, 1), Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    575
    576         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(plane, false);
    577
    578         final EmbeddingPlane otherPlane1 = Planes.fromPointAndPlaneVectors(
    579                 Vector3D.of(0, 0, 1), Vector3D.of(1e-12, 1, 0), Vector3D.Unit.MINUS_X, TEST_PRECISION);
    580
    581         final EmbeddingPlane otherPlane2 = Planes.fromPointAndPlaneVectors(
    582                 Vector3D.of(0, 0, 1), Vector3D.of(0, -1, 1e-12), Vector3D.Unit.PLUS_X, TEST_PRECISION);
    583
    584         final ConvexArea area = ConvexArea.convexPolygonFromVertices(Arrays.asList(
    585                     Vector2D.of(0, -1), Vector2D.of(1, -1), Vector2D.of(1, 1), Vector2D.of(0, 1)
    586                 ), TEST_PRECISION);
    587
    588         // act
    589         ps.add(Planes.subsetFromConvexArea(plane, area));
    590         ps.add(new EmbeddedTreePlaneSubset(otherPlane1, area.toTree()));
    591         ps.add(Planes.subsetFromConvexArea(otherPlane2, area));
    592
    593         // assert
    594         Assertions.assertEquals(4, ps.getSize(), TEST_EPS);
    595         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 1), ps.getCentroid(), TEST_EPS);
    596
    597         final Bounds3D bounds = ps.getBounds();
    598         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(-1, -1, 1), bounds.getMin(), TEST_EPS);
    599         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 1, 1), bounds.getMax(), TEST_EPS);
    600     }
    601
    602     @Test
    603     void testAddMethods_rotatesEquivalentPlanesWithDifferentUAndV_singleConvexArea() {
    604         // arrange
    605         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(
    606                 Vector3D.of(0, 0, 1), Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    607
    608         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(plane, false);
    609
    610         final EmbeddingPlane otherPlane1 = Planes.fromPointAndPlaneVectors(
    611                 Vector3D.of(0, 0, 1), Vector3D.of(1e-12, 1, 0), Vector3D.Unit.MINUS_X, TEST_PRECISION);
    612
    613         final ConvexArea area = ConvexArea.convexPolygonFromVertices(Arrays.asList(
    614                     Vector2D.ZERO, Vector2D.of(1, 0), Vector2D.of(1, 2), Vector2D.of(0, 2)
    615                 ), TEST_PRECISION);
    616
    617         // act
    618         ps.add(Planes.subsetFromConvexArea(otherPlane1, area));
    619
    620         // assert
    621         Assertions.assertEquals(2, ps.getSize(), TEST_EPS);
    622         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(-1, 0.5, 1), ps.getCentroid(), TEST_EPS);
    623
    624         final Bounds3D bounds = ps.getBounds();
    625         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(-2, 0, 1), bounds.getMin(), TEST_EPS);
    626         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 1, 1), bounds.getMax(), TEST_EPS);
    627     }
    628
    629     @Test
    630     void testAddMethods_rotatesEquivalentPlanesWithDifferentUAndV_singleTree() {
    631         // arrange
    632         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(
    633                 Vector3D.of(0, 0, 1), Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    634
    635         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(plane, false);
    636
    637         final EmbeddingPlane otherPlane1 = Planes.fromPointAndPlaneVectors(
    638                 Vector3D.of(0, 0, 1), Vector3D.Unit.MINUS_X, Vector3D.Unit.MINUS_Y, TEST_PRECISION);
    639
    640         final ConvexArea area = ConvexArea.convexPolygonFromVertices(Arrays.asList(
    641                     Vector2D.ZERO, Vector2D.of(1, 0), Vector2D.of(1, 2), Vector2D.of(0, 2)
    642                 ), TEST_PRECISION);
    643
    644         // act
    645         ps.add(new EmbeddedTreePlaneSubset(otherPlane1, area.toTree()));
    646
    647         // assert
    648         Assertions.assertEquals(2, ps.getSize(), TEST_EPS);
    649         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(-0.5, -1, 1), ps.getCentroid(), TEST_EPS);
    650
    651         final Bounds3D bounds = ps.getBounds();
    652         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(-1, -2, 1), bounds.getMin(), TEST_EPS);
    653         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 1), bounds.getMax(), TEST_EPS);
    654     }
    655
    656     @Test
    657     void testAddMethods_validatesPlane() {
    658         // arrange
    659         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(XY_PLANE, false);
    660
    661         // act/assert
    662         Assertions.assertThrows(IllegalArgumentException.class, () -> ps.add(Planes.subsetFromConvexArea(
    663                 Planes.fromPointAndPlaneVectors(Vector3D.ZERO, Vector3D.Unit.PLUS_X, Vector3D.Unit.MINUS_Z, TEST_PRECISION),
    664                 ConvexArea.full())));
    665         Assertions.assertThrows(IllegalArgumentException.class, () -> ps.add(new EmbeddedTreePlaneSubset(
    666                 Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, -1), Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION),
    667                 false)));
    668     }
    669
    670     @Test
    671     void testToString() {
    672         // arrange
    673         final EmbeddedTreePlaneSubset ps = new EmbeddedTreePlaneSubset(
    674                 Planes.fromNormal(Vector3D.Unit.PLUS_Z, TEST_PRECISION).getEmbedding());
    675
    676         // act
    677         final String str = ps.toString();
    678
    679         // assert
    680         GeometryTestUtils.assertContains("EmbeddedTreePlaneSubset[plane= EmbeddingPlane[", str);
    681         GeometryTestUtils.assertContains("subspaceRegion= RegionBSPTree2D[", str);
    682     }
    683
    684     private static void checkPoints(final EmbeddedTreePlaneSubset ps, final RegionLocation loc, final Vector3D... pts) {
    685         for (final Vector3D pt : pts) {
    686             Assertions.assertEquals(loc, ps.classify(pt), "Unexpected location for point " + pt);
    687         }
    688     }
    689 }