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.internal;
    18
    19  import java.util.ArrayList;
    20  import java.util.Arrays;
    21  import java.util.Collections;
    22  import java.util.List;
    23  import java.util.function.Function;
    24
    25  import org.apache.commons.geometry.core.GeometryTestUtils;
    26  import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
    27  import org.apache.commons.geometry.euclidean.threed.Vector3D;
    28  import org.apache.commons.numbers.core.Precision;
    29  import org.junit.jupiter.api.Assertions;
    30  import org.junit.jupiter.api.Test;
    31
    32  class EuclideanUtilsTest {
    33
    34      private static final double TEST_EPS = 1e-10;
    35
    36      private static final Precision.DoubleEquivalence TEST_PRECISION =
    37              Precision.doubleEquivalenceOfEpsilon(TEST_EPS);
    38
    39      @Test
    40      void testConvexPolygonToTriangleFan_threeVertices() {
    41          // arrange
    42          final Vector3D p1 = Vector3D.ZERO;
    43          final Vector3D p2 = Vector3D.of(1, 0, 0);
    44          final Vector3D p3 = Vector3D.of(0, 1, 0);
    45
    46          final List<List<Vector3D>> tris = new ArrayList<>();
    47
    48          // act
    49          EuclideanUtils.convexPolygonToTriangleFan(Arrays.asList(p1, p2, p3), tris::add);
    50
    51          // assert
    52          Assertions.assertEquals(1, tris.size());
    53          EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p1, p2, p3), tris.get(0), TEST_PRECISION);
    54      }
    55
    56      @Test
    57      void testConvexPolygonToTriangleFan_fourVertices() {
    58          // arrange
    59          final Vector3D p1 = Vector3D.ZERO;
    60          final Vector3D p2 = Vector3D.of(1, 0, 0);
    61          final Vector3D p3 = Vector3D.of(1, 1, 0);
    62          final Vector3D p4 = Vector3D.of(0, 1, 0);
    63
    64          final List<List<Vector3D>> tris = new ArrayList<>();
    65
    66          // act
    67          EuclideanUtils.convexPolygonToTriangleFan(Arrays.asList(p1, p2, p3, p4), tris::add);
    68
    69          // assert
    70          Assertions.assertEquals(2, tris.size());
    71
    72          EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p1, p2, p3), tris.get(0), TEST_PRECISION);
    73          EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p1, p3, p4), tris.get(1), TEST_PRECISION);
    74      }
    75
    76      @Test
    77      void testConvexPolygonToTriangleFan_fourVertices_chooseLargestInteriorAngleForBase() {
    78          // arrange
    79          final Vector3D p1 = Vector3D.ZERO;
    80          final Vector3D p2 = Vector3D.of(1, 0, 0);
    81          final Vector3D p3 = Vector3D.of(2, 1, 0);
    82          final Vector3D p4 = Vector3D.of(1.5, 1, 0);
    83
    84          final List<List<Vector3D>> tris = new ArrayList<>();
    85
    86          // act
    87          EuclideanUtils.convexPolygonToTriangleFan(Arrays.asList(p1, p2, p3, p4), tris::add);
    88
    89          // assert
    90          Assertions.assertEquals(2, tris.size());
    91          EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p4, p1, p2), tris.get(0), TEST_PRECISION);
    92          EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p4, p2, p3), tris.get(1), TEST_PRECISION);
    93      }
    94
    95      @Test
    96      void testConvexPolygonToTriangleFan_fourVertices_distancesLessThanPrecision() {
    97          // This test checks that the triangle fan algorithm is not affected by the distances between
    98          // the vertices, just as long as the points are not exactly equal. Callers are responsible for
    99          // ensuring that the points are actually distinct according to the relevant precision context.
    100
    101         // arrange
    102         final Vector3D p1 = Vector3D.ZERO;
    103         final Vector3D p2 = Vector3D.of(1e-20, 0, 0);
    104         final Vector3D p3 = Vector3D.of(1e-20, 1e-20, 0);
    105         final Vector3D p4 = Vector3D.of(0, 1e-20, 0);
    106
    107         final List<List<Vector3D>> tris = new ArrayList<>();
    108
    109         // act
    110         EuclideanUtils.convexPolygonToTriangleFan(Arrays.asList(p1, p2, p3, p4), tris::add);
    111
    112         // assert
    113         Assertions.assertEquals(2, tris.size());
    114         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p1, p2, p3), tris.get(0), TEST_PRECISION);
    115         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p1, p3, p4), tris.get(1), TEST_PRECISION);
    116     }
    117
    118     @Test
    119     void testConvexPolygonToTriangleFan_sixVertices() {
    120         // arrange
    121         final Vector3D p1 = Vector3D.ZERO;
    122         final Vector3D p2 = Vector3D.of(1, -1, 0);
    123         final Vector3D p3 = Vector3D.of(1.5, -1, 0);
    124         final Vector3D p4 = Vector3D.of(5, 0, 0);
    125         final Vector3D p5 = Vector3D.of(3, 1, 0);
    126         final Vector3D p6 = Vector3D.of(0.5, 1, 0);
    127
    128         final List<List<Vector3D>> tris = new ArrayList<>();
    129
    130         // act
    131         EuclideanUtils.convexPolygonToTriangleFan(Arrays.asList(p1, p2, p3, p4, p5, p6), tris::add);
    132
    133         // assert
    134         Assertions.assertEquals(4, tris.size());
    135         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p3, p4, p5), tris.get(0), TEST_PRECISION);
    136         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p3, p5, p6), tris.get(1), TEST_PRECISION);
    137         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p3, p6, p1), tris.get(2), TEST_PRECISION);
    138         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p3, p1, p2), tris.get(3), TEST_PRECISION);
    139     }
    140
    141     @Test
    142     void testConvexPolygonToTriangleFan_notEnoughVertices() {
    143         // arrange
    144         final String baseMsg = "Cannot create triangle fan: 3 or more vertices are required but found only ";
    145
    146         // act/assert
    147         GeometryTestUtils.assertThrowsWithMessage(() -> {
    148             EuclideanUtils.convexPolygonToTriangleFan(Collections.emptyList(), Function.identity());
    149         }, IllegalArgumentException.class, baseMsg + "0");
    150
    151         GeometryTestUtils.assertThrowsWithMessage(() -> {
    152             EuclideanUtils.convexPolygonToTriangleFan(Collections.singletonList(Vector3D.ZERO), Function.identity());
    153         }, IllegalArgumentException.class, baseMsg + "1");
    154
    155         GeometryTestUtils.assertThrowsWithMessage(() -> {
    156             EuclideanUtils.convexPolygonToTriangleFan(Arrays.asList(Vector3D.ZERO, Vector3D.of(1, 0, 0)), Function.identity());
    157         }, IllegalArgumentException.class, baseMsg + "2");
    158     }
    159 }