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