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 }