001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.geometry.euclidean.internal;
018
019import java.util.ArrayList;
020import java.util.Arrays;
021import java.util.Collections;
022import java.util.Iterator;
023import java.util.List;
024import java.util.function.Function;
025
026import org.apache.commons.geometry.euclidean.threed.Vector3D;
027
028/** Class containing utilities and algorithms intended to be internal to the library.
029 * Absolutely no guarantees are made regarding the stability of this API.
030 */
031public final class EuclideanUtils {
032
033    /** Number of vertices in a triangle, i.e. {@code 3}. */
034    public static final int TRIANGLE_VERTEX_COUNT = 3;
035
036    /** Utility class; no instantiation. */
037    private EuclideanUtils() { }
038
039    /** Convert a convex polygon defined by a list of vertices into a triangle fan. The vertex forming the largest
040     * interior angle in the polygon is selected as the base of the triangle fan. Callers are responsible for
041     * ensuring that the given list of vertices define a geometrically valid convex polygon; no validation (except
042     * for a check on the minimum number of vertices) is performed.
043     * @param <T> triangle result type
044     * @param vertices vertices defining a convex polygon
045     * @param fn function accepting the vertices of each triangle as a list and returning the object used
046     *      to represent that triangle in the result; each argument to this function is guaranteed to
047     *      contain 3 vertices
048     * @return a list containing the return results of the function when passed the vertices for each
049     *      triangle in order
050     * @throws IllegalArgumentException if fewer than 3 vertices are given
051     */
052    public static <T> List<T> convexPolygonToTriangleFan(final List<Vector3D> vertices,
053           final Function<List<Vector3D>, T> fn) {
054        final int size = vertices.size();
055        if (size < TRIANGLE_VERTEX_COUNT) {
056            throw new IllegalArgumentException("Cannot create triangle fan: " + TRIANGLE_VERTEX_COUNT +
057                    " or more vertices are required but found only " + vertices.size());
058        } else if (size == TRIANGLE_VERTEX_COUNT) {
059            return Collections.singletonList(fn.apply(vertices));
060        }
061
062        final List<T> triangles = new ArrayList<>(size - 2);
063
064        final int fanIdx = findBestTriangleFanIndex(vertices);
065        int vertexIdx = (fanIdx + 1) % size;
066
067        final Vector3D fanBase = vertices.get(fanIdx);
068        Vector3D vertexA = vertices.get(vertexIdx);
069        Vector3D vertexB;
070
071        vertexIdx = (vertexIdx + 1) % size;
072        while (vertexIdx != fanIdx) {
073            vertexB = vertices.get(vertexIdx);
074
075            triangles.add(fn.apply(Arrays.asList(fanBase, vertexA, vertexB)));
076
077            vertexA = vertexB;
078            vertexIdx = (vertexIdx + 1) % size;
079        }
080
081        return triangles;
082    }
083
084    /** Find the index of the best vertex to use as the base for a triangle fan split of the convex polygon
085     * defined by the given vertices. The best vertex is the one that forms the largest interior angle in the
086     * polygon since a split at that point will help prevent the creation of very thin triangles.
087     * @param vertices vertices defining the convex polygon; must not be empty; no validation is performed
088     *      to ensure that the vertices actually define a convex polygon
089     * @return the index of the best vertex to use as the base for a triangle fan split of the convex polygon
090     */
091    private static int findBestTriangleFanIndex(final List<Vector3D> vertices) {
092        final Iterator<Vector3D> it = vertices.iterator();
093
094        Vector3D curPt = it.next();
095        Vector3D nextPt;
096
097        final Vector3D lastVec = vertices.get(vertices.size() - 1).directionTo(curPt);
098        Vector3D incomingVec = lastVec;
099        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}