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