EuclideanUtils.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.geometry.euclidean.internal;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.function.Function;

import org.apache.commons.geometry.euclidean.threed.Vector3D;

/** Class containing utilities and algorithms intended to be internal to the library.
 * Absolutely no guarantees are made regarding the stability of this API.
 */
public final class EuclideanUtils {

    /** Number of vertices in a triangle, i.e. {@code 3}. */
    public static final int TRIANGLE_VERTEX_COUNT = 3;

    /** Utility class; no instantiation. */
    private EuclideanUtils() { }

    /** Convert a convex polygon defined by a list of vertices into a triangle fan. The vertex forming the largest
     * interior angle in the polygon is selected as the base of the triangle fan. Callers are responsible for
     * ensuring that the given list of vertices define a geometrically valid convex polygon; no validation (except
     * for a check on the minimum number of vertices) is performed.
     * @param <T> triangle result type
     * @param vertices vertices defining a convex polygon
     * @param fn function accepting the vertices of each triangle as a list and returning the object used
     *      to represent that triangle in the result; each argument to this function is guaranteed to
     *      contain 3 vertices
     * @return a list containing the return results of the function when passed the vertices for each
     *      triangle in order
     * @throws IllegalArgumentException if fewer than 3 vertices are given
     */
    public static <T> List<T> convexPolygonToTriangleFan(final List<Vector3D> vertices,
           final Function<List<Vector3D>, T> fn) {
        final int size = vertices.size();
        if (size < TRIANGLE_VERTEX_COUNT) {
            throw new IllegalArgumentException("Cannot create triangle fan: " + TRIANGLE_VERTEX_COUNT +
                    " or more vertices are required but found only " + vertices.size());
        } else if (size == TRIANGLE_VERTEX_COUNT) {
            return Collections.singletonList(fn.apply(vertices));
        }

        final List<T> triangles = new ArrayList<>(size - 2);

        final int fanIdx = findBestTriangleFanIndex(vertices);
        int vertexIdx = (fanIdx + 1) % size;

        final Vector3D fanBase = vertices.get(fanIdx);
        Vector3D vertexA = vertices.get(vertexIdx);
        Vector3D vertexB;

        vertexIdx = (vertexIdx + 1) % size;
        while (vertexIdx != fanIdx) {
            vertexB = vertices.get(vertexIdx);

            triangles.add(fn.apply(Arrays.asList(fanBase, vertexA, vertexB)));

            vertexA = vertexB;
            vertexIdx = (vertexIdx + 1) % size;
        }

        return triangles;
    }

    /** Find the index of the best vertex to use as the base for a triangle fan split of the convex polygon
     * defined by the given vertices. The best vertex is the one that forms the largest interior angle in the
     * polygon since a split at that point will help prevent the creation of very thin triangles.
     * @param vertices vertices defining the convex polygon; must not be empty; no validation is performed
     *      to ensure that the vertices actually define a convex polygon
     * @return the index of the best vertex to use as the base for a triangle fan split of the convex polygon
     */
    private static int findBestTriangleFanIndex(final List<Vector3D> vertices) {
        final Iterator<Vector3D> it = vertices.iterator();

        Vector3D curPt = it.next();
        Vector3D nextPt;

        final Vector3D lastVec = vertices.get(vertices.size() - 1).directionTo(curPt);
        Vector3D incomingVec = lastVec;
        Vector3D outgoingVec;

        int bestIdx = 0;
        double bestDot = -1.0;

        int idx = 0;
        double dot;
        while (it.hasNext()) {
            nextPt = it.next();
            outgoingVec = curPt.directionTo(nextPt);

            dot = incomingVec.dot(outgoingVec);
            if (dot > bestDot) {
                bestIdx = idx;
                bestDot = dot;
            }

            curPt = nextPt;
            incomingVec = outgoingVec;

            ++idx;
        }

        // handle the last vertex on its own
        dot = incomingVec.dot(lastVec);
        if (dot > bestDot) {
            bestIdx = idx;
        }

        return bestIdx;
    }
}