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.Iterator;
    23  import java.util.List;
    24  import java.util.function.Function;
    25
    26  import org.apache.commons.geometry.euclidean.threed.Vector3D;
    27
    28  /** Class containing utilities and algorithms intended to be internal to the library.
    29   * Absolutely no guarantees are made regarding the stability of this API.
    30   */
    31  public final class EuclideanUtils {
    32
    33      /** Number of vertices in a triangle, i.e. {@code 3}. */
    34      public static final int TRIANGLE_VERTEX_COUNT = 3;
    35
    36      /** Utility class; no instantiation. */
    37      private EuclideanUtils() { }
    38
    39      /** Convert a convex polygon defined by a list of vertices into a triangle fan. The vertex forming the largest
    40       * interior angle in the polygon is selected as the base of the triangle fan. Callers are responsible for
    41       * ensuring that the given list of vertices define a geometrically valid convex polygon; no validation (except
    42       * for a check on the minimum number of vertices) is performed.
    43       * @param <T> triangle result type
    44       * @param vertices vertices defining a convex polygon
    45       * @param fn function accepting the vertices of each triangle as a list and returning the object used
    46       *      to represent that triangle in the result; each argument to this function is guaranteed to
    47       *      contain 3 vertices
    48       * @return a list containing the return results of the function when passed the vertices for each
    49       *      triangle in order
    50       * @throws IllegalArgumentException if fewer than 3 vertices are given
    51       */
    52      public static <T> List<T> convexPolygonToTriangleFan(final List<Vector3D> vertices,
    53             final Function<List<Vector3D>, T> fn) {
    54          final int size = vertices.size();
    55          if (size < TRIANGLE_VERTEX_COUNT) {
    56              throw new IllegalArgumentException("Cannot create triangle fan: " + TRIANGLE_VERTEX_COUNT +
    57                      " or more vertices are required but found only " + vertices.size());
    58          } else if (size == TRIANGLE_VERTEX_COUNT) {
    59              return Collections.singletonList(fn.apply(vertices));
    60          }
    61
    62          final List<T> triangles = new ArrayList<>(size - 2);
    63
    64          final int fanIdx = findBestTriangleFanIndex(vertices);
    65          int vertexIdx = (fanIdx + 1) % size;
    66
    67          final Vector3D fanBase = vertices.get(fanIdx);
    68          Vector3D vertexA = vertices.get(vertexIdx);
    69          Vector3D vertexB;
    70
    71          vertexIdx = (vertexIdx + 1) % size;
    72          while (vertexIdx != fanIdx) {
    73              vertexB = vertices.get(vertexIdx);
    74
    75              triangles.add(fn.apply(Arrays.asList(fanBase, vertexA, vertexB)));
    76
    77              vertexA = vertexB;
    78              vertexIdx = (vertexIdx + 1) % size;
    79          }
    80
    81          return triangles;
    82      }
    83
    84      /** Find the index of the best vertex to use as the base for a triangle fan split of the convex polygon
    85       * defined by the given vertices. The best vertex is the one that forms the largest interior angle in the
    86       * polygon since a split at that point will help prevent the creation of very thin triangles.
    87       * @param vertices vertices defining the convex polygon; must not be empty; no validation is performed
    88       *      to ensure that the vertices actually define a convex polygon
    89       * @return the index of the best vertex to use as the base for a triangle fan split of the convex polygon
    90       */
    91      private static int findBestTriangleFanIndex(final List<Vector3D> vertices) {
    92          final Iterator<Vector3D> it = vertices.iterator();
    93
    94          Vector3D curPt = it.next();
    95          Vector3D nextPt;
    96
    97          final Vector3D lastVec = vertices.get(vertices.size() - 1).directionTo(curPt);
    98          Vector3D incomingVec = lastVec;
    99          Vector3D outgoingVec;
    100
    101         int bestIdx = 0;
    102         double bestDot = -1.0;
    103
    104         int idx = 0;
    105         double dot;
    106         while (it.hasNext()) {
    107             nextPt = it.next();
    108             outgoingVec = curPt.directionTo(nextPt);
    109
    110             dot = incomingVec.dot(outgoingVec);
    111             if (dot > bestDot) {
    112                 bestIdx = idx;
    113                 bestDot = dot;
    114             }
    115
    116             curPt = nextPt;
    117             incomingVec = outgoingVec;
    118
    119             ++idx;
    120         }
    121
    122         // handle the last vertex on its own
    123         dot = incomingVec.dot(lastVec);
    124         if (dot > bestDot) {
    125             bestIdx = idx;
    126         }
    127
    128         return bestIdx;
    129     }
    130 }