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.ArrayList;
    20  import java.util.Arrays;
    21  import java.util.List;
    22
    23  import org.apache.commons.geometry.core.GeometryTestUtils;
    24  import org.apache.commons.geometry.core.RegionLocation;
    25  import org.apache.commons.geometry.core.partitioning.Split;
    26  import org.apache.commons.geometry.core.partitioning.SplitLocation;
    27  import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
    28  import org.apache.commons.geometry.euclidean.threed.rotation.QuaternionRotation;
    29  import org.apache.commons.geometry.euclidean.twod.ConvexArea;
    30  import org.apache.commons.geometry.euclidean.twod.Vector2D;
    31  import org.apache.commons.numbers.angle.Angle;
    32  import org.apache.commons.numbers.core.Precision;
    33  import org.junit.jupiter.api.Assertions;
    34  import org.junit.jupiter.api.Test;
    35
    36  class VertexListConvexPolygon3DTest {
    37
    38      private static final double TEST_EPS = 1e-10;
    39
    40      private static final Precision.DoubleEquivalence TEST_PRECISION =
    41              Precision.doubleEquivalenceOfEpsilon(TEST_EPS);
    42
    43      private static final Plane XY_PLANE_Z1 = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
    44              Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    45
    46      private static final List<Vector3D> TRIANGLE_VERTICES =
    47              Arrays.asList(Vector3D.of(0, 0, 1), Vector3D.of(1, 0, 1), Vector3D.of(0, 1, 1));
    48
    49      @Test
    50      void testProperties() {
    51          // act
    52          final VertexListConvexPolygon3D p = new VertexListConvexPolygon3D(XY_PLANE_Z1, TRIANGLE_VERTICES);
    53
    54          // assert
    55          Assertions.assertFalse(p.isFull());
    56          Assertions.assertFalse(p.isEmpty());
    57          Assertions.assertTrue(p.isFinite());
    58          Assertions.assertFalse(p.isInfinite());
    59
    60          Assertions.assertEquals(0.5, p.getSize(), TEST_EPS);
    61          EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1.0 / 3.0, 1.0 / 3.0, 1), p.getCentroid(), TEST_EPS);
    62
    63          Assertions.assertSame(XY_PLANE_Z1, p.getPlane());
    64
    65          EuclideanTestUtils.assertVertexLoopSequence(
    66                  Arrays.asList(Vector3D.of(0, 0, 1), Vector3D.of(1, 0, 1), Vector3D.of(0, 1, 1)),
    67                  p.getVertices(), TEST_PRECISION);
    68
    69
    70          final Bounds3D bounds = p.getBounds();
    71          EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 1), bounds.getMin(), TEST_EPS);
    72          EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 1, 1), bounds.getMax(), TEST_EPS);
    73      }
    74
    75      @Test
    76      void testCtor_validatesVertexListSize() {
    77          // act/assert
    78          GeometryTestUtils.assertThrowsWithMessage(() -> {
    79              new VertexListConvexPolygon3D(XY_PLANE_Z1, Arrays.asList(Vector3D.ZERO, Vector3D.Unit.PLUS_X));
    80          }, IllegalArgumentException.class, "Convex polygon requires at least 3 points; found 2");
    81      }
    82
    83      @Test
    84      void testVertices_listIsImmutable() {
    85          // arrange
    86          final List<Vector3D> vertices = new ArrayList<>(TRIANGLE_VERTICES);
    87          final VertexListConvexPolygon3D p = new VertexListConvexPolygon3D(XY_PLANE_Z1, vertices);
    88
    89          // act/assert
    90          Assertions.assertThrows(UnsupportedOperationException.class, () -> p.getVertices().add(Vector3D.of(-1, 0, 1)));
    91      }
    92
    93      @Test
    94      void testGetCentroid_linearVertices() {
    95          // this should not happen with all of the checks in place for constructing these
    96          // instances; this test is to ensure that the centroid computation can still handle
    97          // the situation
    98
    99          // arrange
    100         final List<Vector3D> vertices = Arrays.asList(Vector3D.ZERO, Vector3D.of(0.5, 0, 0), Vector3D.of(2, 0, 0));
    101         final VertexListConvexPolygon3D p = new VertexListConvexPolygon3D(XY_PLANE_Z1, vertices);
    102
    103         // act
    104         final Vector3D center = p.getCentroid();
    105
    106         // assert
    107         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 0, 0), center, TEST_EPS);
    108     }
    109
    110     @Test
    111     void testGetSubspaceRegion() {
    112         // arrange
    113         final VertexListConvexPolygon3D p = new VertexListConvexPolygon3D(XY_PLANE_Z1, TRIANGLE_VERTICES);
    114
    115         // act
    116         final ConvexArea area = p.getEmbedded().getSubspaceRegion();
    117
    118         // assert
    119         Assertions.assertFalse(area.isFull());
    120         Assertions.assertFalse(area.isEmpty());
    121         Assertions.assertTrue(area.isFinite());
    122         Assertions.assertFalse(area.isInfinite());
    123
    124         Assertions.assertEquals(0.5, area.getSize(), TEST_EPS);
    125
    126         final List<Vector2D> vertices = area.getVertices();
    127         Assertions.assertEquals(3, vertices.size());
    128         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, vertices.get(0), TEST_EPS);
    129         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 0), vertices.get(1), TEST_EPS);
    130         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0, 1), vertices.get(2), TEST_EPS);
    131     }
    132
    133     @Test
    134     void testToTriangles_threeVertices() {
    135         // arrange
    136         final VertexListConvexPolygon3D p = new VertexListConvexPolygon3D(XY_PLANE_Z1, TRIANGLE_VERTICES);
    137
    138         // act
    139         final List<Triangle3D> tris = p.toTriangles();
    140
    141         // assert
    142         Assertions.assertEquals(1, tris.size());
    143
    144         final Triangle3D a = tris.get(0);
    145         Assertions.assertSame(XY_PLANE_Z1, a.getPlane());
    146         EuclideanTestUtils.assertVertexLoopSequence(TRIANGLE_VERTICES, a.getVertices(), TEST_PRECISION);
    147     }
    148
    149     @Test
    150     void testToTriangles_fiveVertices() {
    151         // arrange
    152         final Vector3D p1 = Vector3D.of(1, 1, 1);
    153         final Vector3D p2 = Vector3D.of(2, 1.2, 1);
    154         final Vector3D p3 = Vector3D.of(3, 2, 1);
    155         final Vector3D p4 = Vector3D.of(1, 4, 1);
    156         final Vector3D p5 = Vector3D.of(0, 2, 1);
    157
    158         final VertexListConvexPolygon3D p = new VertexListConvexPolygon3D(XY_PLANE_Z1, Arrays.asList(p1, p2, p3, p4, p5));
    159
    160         // act
    161         final List<Triangle3D> tris = p.toTriangles();
    162
    163         // assert
    164         Assertions.assertEquals(3, tris.size());
    165
    166         final Triangle3D a = tris.get(0);
    167         Assertions.assertSame(XY_PLANE_Z1, a.getPlane());
    168         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p2, p3, p4), a.getVertices(), TEST_PRECISION);
    169
    170         final Triangle3D b = tris.get(1);
    171         Assertions.assertSame(XY_PLANE_Z1, b.getPlane());
    172         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p2, p4, p5), b.getVertices(), TEST_PRECISION);
    173
    174         final Triangle3D c = tris.get(2);
    175         Assertions.assertSame(XY_PLANE_Z1, c.getPlane());
    176         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p2, p5, p1), c.getVertices(), TEST_PRECISION);
    177     }
    178
    179     @Test
    180     void testClassify() {
    181         // arrange
    182         final VertexListConvexPolygon3D p = new VertexListConvexPolygon3D(XY_PLANE_Z1, Arrays.asList(
    183                     Vector3D.of(1, 2, 1), Vector3D.of(3, 2, 1),
    184                     Vector3D.of(3, 4, 1), Vector3D.of(1, 4, 1)
    185                 ));
    186
    187         // act/assert
    188         checkPoints(p, RegionLocation.INSIDE, Vector3D.of(2, 3, 1));
    189         checkPoints(p, RegionLocation.BOUNDARY,
    190                 Vector3D.of(1, 3, 1), Vector3D.of(3, 3, 1),
    191                 Vector3D.of(2, 2, 1), Vector3D.of(2, 4, 1));
    192         checkPoints(p, RegionLocation.OUTSIDE,
    193                 Vector3D.of(2, 3, 0), Vector3D.of(2, 3, 2),
    194                 Vector3D.of(0, 3, 1), Vector3D.of(4, 3, 1),
    195                 Vector3D.of(2, 1, 1), Vector3D.of(2, 5, 1));
    196     }
    197
    198     @Test
    199     void testClosest() {
    200         // arrange
    201         final VertexListConvexPolygon3D p = new VertexListConvexPolygon3D(XY_PLANE_Z1, Arrays.asList(
    202                 Vector3D.of(1, 2, 1), Vector3D.of(3, 2, 1),
    203                 Vector3D.of(3, 4, 1), Vector3D.of(1, 4, 1)
    204             ));
    205
    206         // act/assert
    207         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(2, 3, 1), p.closest(Vector3D.of(2, 3, 1)), TEST_EPS);
    208         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(2, 3, 1), p.closest(Vector3D.of(2, 3, 100)), TEST_EPS);
    209
    210         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(3, 4, 1), p.closest(Vector3D.of(3, 5, 10)), TEST_EPS);
    211         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(3, 4, 1), p.closest(Vector3D.of(3, 4, 10)), TEST_EPS);
    212         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(3, 3, 1), p.closest(Vector3D.of(3, 3, 10)), TEST_EPS);
    213         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(3, 2, 1), p.closest(Vector3D.of(3, 2, 10)), TEST_EPS);
    214         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(3, 2, 1), p.closest(Vector3D.of(3, 1, 10)), TEST_EPS);
    215
    216         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 4, 1), p.closest(Vector3D.of(0, 5, -10)), TEST_EPS);
    217         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 4, 1), p.closest(Vector3D.of(1, 5, -10)), TEST_EPS);
    218         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(2, 4, 1), p.closest(Vector3D.of(2, 5, -10)), TEST_EPS);
    219         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(3, 4, 1), p.closest(Vector3D.of(3, 5, -10)), TEST_EPS);
    220         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(3, 4, 1), p.closest(Vector3D.of(4, 5, -10)), TEST_EPS);
    221
    222         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 2, 1), p.closest(Vector3D.of(0, 2, 1)), TEST_EPS);
    223         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 2, 1), p.closest(Vector3D.of(1, 2, 1)), TEST_EPS);
    224         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(2, 2, 1), p.closest(Vector3D.of(2, 2, 1)), TEST_EPS);
    225         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(3, 2, 1), p.closest(Vector3D.of(3, 2, 1)), TEST_EPS);
    226         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(3, 2, 1), p.closest(Vector3D.of(4, 2, 1)), TEST_EPS);
    227
    228         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 3, 1), p.closest(Vector3D.of(0, 3, -10)), TEST_EPS);
    229         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 3, 1), p.closest(Vector3D.of(1, 3, -10)), TEST_EPS);
    230         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(2, 3, 1), p.closest(Vector3D.of(2, 3, -10)), TEST_EPS);
    231         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(3, 3, 1), p.closest(Vector3D.of(3, 3, -10)), TEST_EPS);
    232         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(3, 3, 1), p.closest(Vector3D.of(4, 3, -10)), TEST_EPS);
    233
    234         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 2, 1),
    235                 p.closest(Vector3D.of(-100, -100, -100)), TEST_EPS);
    236         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(3, 3.5, 1),
    237                 p.closest(Vector3D.of(100, 3.5, 100)), TEST_EPS);
    238     }
    239
    240     @Test
    241     void testTransform() {
    242         // arrange
    243         final AffineTransformMatrix3D t = AffineTransformMatrix3D.identity()
    244                 .rotate(QuaternionRotation.fromAxisAngle(Vector3D.Unit.PLUS_Y, -Angle.PI_OVER_TWO))
    245                 .scale(1, 1, 2)
    246                 .translate(Vector3D.of(1, 0, 0));
    247
    248         final VertexListConvexPolygon3D p = new VertexListConvexPolygon3D(XY_PLANE_Z1, Arrays.asList(
    249                 Vector3D.of(1, 2, 1), Vector3D.of(3, 2, 1),
    250                 Vector3D.of(3, 4, 1), Vector3D.of(1, 4, 1)
    251             ));
    252
    253         // act
    254         final VertexListConvexPolygon3D result = p.transform(t);
    255
    256         // assert
    257         Assertions.assertFalse(result.isFull());
    258         Assertions.assertFalse(result.isEmpty());
    259         Assertions.assertTrue(result.isFinite());
    260         Assertions.assertFalse(result.isInfinite());
    261
    262         Assertions.assertEquals(8, result.getSize(), TEST_EPS);
    263
    264         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.MINUS_X, result.getPlane().getNormal(), TEST_EPS);
    265
    266         EuclideanTestUtils.assertVertexLoopSequence(
    267                 Arrays.asList(Vector3D.of(0, 2, 2), Vector3D.of(0, 2, 6), Vector3D.of(0, 4, 6), Vector3D.of(0, 4, 2)),
    268                 result.getVertices(), TEST_PRECISION);
    269     }
    270
    271     @Test
    272     void testReverse() {
    273         // arrange
    274         final VertexListConvexPolygon3D p = new VertexListConvexPolygon3D(XY_PLANE_Z1, Arrays.asList(
    275                 Vector3D.of(1, 2, 1), Vector3D.of(3, 2, 1),
    276                 Vector3D.of(3, 4, 1), Vector3D.of(1, 4, 1)
    277             ));
    278
    279         // act
    280         final VertexListConvexPolygon3D result = p.reverse();
    281
    282         // assert
    283         Assertions.assertFalse(result.isFull());
    284         Assertions.assertFalse(result.isEmpty());
    285         Assertions.assertTrue(result.isFinite());
    286         Assertions.assertFalse(result.isInfinite());
    287
    288         Assertions.assertEquals(4, result.getSize(), TEST_EPS);
    289
    290         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.MINUS_Z, result.getPlane().getNormal(), TEST_EPS);
    291
    292         EuclideanTestUtils.assertVertexLoopSequence(
    293                 Arrays.asList(Vector3D.of(1, 4, 1), Vector3D.of(3, 4, 1), Vector3D.of(3, 2, 1), Vector3D.of(1, 2, 1)),
    294                 result.getVertices(), TEST_PRECISION);
    295     }
    296
    297     @Test
    298     void testSplit_plus() {
    299         // arrange
    300         final VertexListConvexPolygon3D p = new VertexListConvexPolygon3D(XY_PLANE_Z1, TRIANGLE_VERTICES);
    301
    302         final Plane splitter = Planes.fromPointAndNormal(Vector3D.ZERO, Vector3D.Unit.PLUS_X, TEST_PRECISION);
    303
    304         // act
    305         final Split<PlaneConvexSubset> split = p.split(splitter);
    306
    307         // assert
    308         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
    309
    310         Assertions.assertNull(split.getMinus());
    311         Assertions.assertSame(p, split.getPlus());
    312     }
    313
    314     @Test
    315     void testSplit_minus() {
    316         // arrange
    317         final VertexListConvexPolygon3D p = new VertexListConvexPolygon3D(XY_PLANE_Z1, TRIANGLE_VERTICES);
    318
    319         final Plane splitter = Planes.fromPointAndNormal(Vector3D.ZERO, Vector3D.Unit.MINUS_Z, TEST_PRECISION);
    320
    321         // act
    322         final Split<PlaneConvexSubset> split = p.split(splitter);
    323
    324         // assert
    325         Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
    326
    327         Assertions.assertSame(p, split.getMinus());
    328         Assertions.assertNull(split.getPlus());
    329     }
    330
    331     @Test
    332     void testSplit_both() {
    333         // arrange
    334         final VertexListConvexPolygon3D p = new VertexListConvexPolygon3D(XY_PLANE_Z1, TRIANGLE_VERTICES);
    335
    336         final Plane splitter = Planes.fromPointAndNormal(Vector3D.ZERO, Vector3D.of(-1, 1, 0), TEST_PRECISION);
    337
    338         // act
    339         final Split<PlaneConvexSubset> split = p.split(splitter);
    340
    341         // assert
    342         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
    343
    344         final PlaneConvexSubset minus = split.getMinus();
    345         EuclideanTestUtils.assertVertexLoopSequence(
    346                 Arrays.asList(Vector3D.of(0, 0, 1), Vector3D.of(1, 0, 1), Vector3D.of(0.5, 0.5, 1)),
    347                 minus.getVertices(), TEST_PRECISION);
    348
    349         final PlaneConvexSubset plus = split.getPlus();
    350         EuclideanTestUtils.assertVertexLoopSequence(
    351                 Arrays.asList(Vector3D.of(0, 0, 1), Vector3D.of(0.5, 0.5, 1), Vector3D.of(0, 1, 1)),
    352                 plus.getVertices(), TEST_PRECISION);
    353     }
    354
    355     @Test
    356     void testSplit_neither() {
    357         // arrange
    358         final VertexListConvexPolygon3D p = new VertexListConvexPolygon3D(XY_PLANE_Z1, TRIANGLE_VERTICES);
    359
    360         final Plane splitter = Planes.fromPointAndNormal(Vector3D.of(0, 0, 1), Vector3D.of(0, 1e-15, -1), TEST_PRECISION);
    361
    362         // act
    363         final Split<PlaneConvexSubset> split = p.split(splitter);
    364
    365         // assert
    366         Assertions.assertEquals(SplitLocation.NEITHER, split.getLocation());
    367
    368         Assertions.assertNull(split.getMinus());
    369         Assertions.assertNull(split.getPlus());
    370     }
    371
    372     @Test
    373     void testToString() {
    374         // arrange
    375         final VertexListConvexPolygon3D p = new VertexListConvexPolygon3D(XY_PLANE_Z1, TRIANGLE_VERTICES);
    376
    377         // act
    378         final String str = p.toString();
    379
    380         // assert
    381         GeometryTestUtils.assertContains("VertexListConvexPolygon3D[normal= (", str);
    382         GeometryTestUtils.assertContains("vertices= [", str);
    383     }
    384
    385     private static void checkPoints(final ConvexPolygon3D ps, final RegionLocation loc, final Vector3D... pts) {
    386         for (final Vector3D pt : pts) {
    387             Assertions.assertEquals(loc, ps.classify(pt), "Unexpected location for point " + pt);
    388         }
    389     }
    390 }