VanGoghTriangulator2D.java
/*
* Copyright (C) 2012 Alberto Irurueta Carro (alberto@irurueta.com)
*
* Licensed 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 com.irurueta.geometry;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
* This class defines a triangulator for 2D polygons. Triangulators divide
* polygons into triangles, which are the simplest geometric figure.
* This implementation uses Van Gogh or Ear Cutting algorithm for triangulation.
*/
public class VanGoghTriangulator2D extends Triangulator2D {
/**
* Returns triangulator method.
* Each method implementation will divide polygons into triangles using
* different techniques.
*
* @return Triangulator method.
*/
@Override
public TriangulatorMethod getMethod() {
return TriangulatorMethod.VAN_GOGH_TRIANGULATOR;
}
/**
* Triangulates provided polygon by dividing it into a set of triangles.
*
* @param polygon Polygon to be triangulated.
* @return List of triangles forming the polygon that has been triangulated.
* @throws TriangulatorException Raised if triangulation cannot be done.
* Usually this indicates numerical instability or polygon degeneracy.
*/
@Override
public List<Triangle2D> triangulate(final Polygon2D polygon) throws TriangulatorException {
// triangulation will modify provided list of vertices, so we make a copy
// of it
// original vertices
final var vertices = polygon.getVertices();
final var verticesCopy = new ArrayList<>(polygon.getVertices());
return internalTriangulate(verticesCopy, null, vertices);
}
/**
* Triangulates a polygon formed by provided vertices.
*
* @param vertices List of points considered as vertices of a polygon.
* @return List of triangles forming the polygon that has been triangulated.
* @throws TriangulatorException Raised if triangulation cannot be done.
* Usually this indicates numerical instability or polygon degeneracy.
*/
@Override
public List<Triangle2D> triangulate(final List<Point2D> vertices) throws TriangulatorException {
if (vertices.size() < MIN_VERTICES) {
throw new TriangulatorException();
}
// triangulation will modify provided list of vertices, so we make a copy
// of it
final var verticesCopy = new ArrayList<>(vertices);
return internalTriangulate(verticesCopy, null, vertices);
}
/**
* Triangulates a polygon formed by provided vertices.
*
* @param vertices List of points considered as vertices of a polygon.
* @param indices List where indices of original vertices will be stored.
* This list can be used to refer to the original order of vertices. Notice
* that vertices indices might be repeated because vertices might appear in
* more than one triangle after triangulation. If this parameter is null,
* indices won't be stored in this list.
* @return List of triangles forming the polygon that has been triangulated
* @throws TriangulatorException Raised if triangulation cannot be done.
* Usually this indicates numerical instability or polygon degeneracy.
*/
@Override
public List<Triangle2D> triangulate(final List<Point2D> vertices, final List<int[]> indices)
throws TriangulatorException {
if (vertices.size() < MIN_VERTICES) {
throw new TriangulatorException();
}
// triangulation will modify provided list of vertices, so we make a copy
// of it
final var verticesCopy = new ArrayList<>(vertices);
return internalTriangulate(verticesCopy, indices, vertices);
}
/**
* Internal method that computes the actual triangulation.
*
* @param verticesCopy List of points considered as verticesCopy of a
* polygon. This list will be modified after execution of this method.
* @param indices List where indices of original verticesCopy will be
* stored.
* This list can be used to refer to the original order of verticesCopy.
* Notice that verticesCopy indices might be repeated because verticesCopy
* might appear in more than one triangle after triangulation. If this
* parameter is null, indices won't be stored in this list.
* @param originalVertices Reference to original list of vertices that won't
* be modified.
* @return List of triangles forming the polygon that has been triangulated.
* @throws TriangulatorException Raised if triangulation cannot be done.
* Usually this indicates numerical instability or polygon degeneracy.
*/
private static List<Triangle2D> internalTriangulate(
final List<Point2D> verticesCopy, final List<int[]> indices, final List<Point2D> originalVertices)
throws TriangulatorException {
if (verticesCopy.size() < MIN_VERTICES) {
throw new TriangulatorException();
}
final var result = new LinkedList<Triangle2D>();
boolean madeCut;
Triangle2D triangle = null;
// Second, apply algorithm
while (verticesCopy.size() > MIN_VERTICES) {
madeCut = false;
final var lastElement = verticesCopy.size() - 1;
for (int i = 0; i <= lastElement; i++) {
if (i == 0) {
if (triangle == null) {
// instantiate triangle if not already instantiated
triangle = new Triangle2D(verticesCopy.get(lastElement), verticesCopy.get(0),
verticesCopy.get(1));
} else {
triangle.setVertices(verticesCopy.get(lastElement), verticesCopy.get(0), verticesCopy.get(1));
}
} else if (i == lastElement) {
triangle.setVertices(verticesCopy.get(lastElement - 1), verticesCopy.get(lastElement),
verticesCopy.get(0));
} else {
triangle.setVertices(verticesCopy.get(i - 1), verticesCopy.get(i), verticesCopy.get(i + 1));
}
if (isEar(triangle, verticesCopy)) {
// If it is an ear, we build a face out of the triangle being
// cut and remove it from polygon by cutting it
result.add(triangle);
// so that it cannot be reused after being added
triangle = null;
// cut ear
verticesCopy.remove(i);
madeCut = true;
// Leave from FOR loop to loop again to new reduced vertices set
break;
}
}
// if arrived here but no cut was made and polygon size contains
// more than 3 vertices, then the algorithm failed for some reason
if (!madeCut) {
throw new TriangulatorException();
}
}
// instantiate final triangle
triangle = new Triangle2D(verticesCopy.get(0), verticesCopy.get(1), verticesCopy.get(2));
final var arePointsColinear = triangle.areVerticesColinear();
// only add final triangle if not co-linear (area greater than small
// threshold)
if (!arePointsColinear)
result.add(triangle);
// add indices of triangles verticesCopy
computeIndices(originalVertices, result, indices);
return result;
}
/**
* Computes indices of resulting triangles vertices respect to original
* polygon vertices. Indices are stored in provided indices list.
*
* @param vertices Vertices of polygon.
* @param triangles Triangles obtained after triangulation.
* @param indices Indices of original positions of resulting triangle's
* vertices.
*/
private static void computeIndices(
final List<Point2D> vertices, final List<Triangle2D> triangles, final List<int[]> indices) {
if (indices != null) {
int vertexCounter;
int triangleVertexCounter;
int[] triangleIndices;
for (final var t : triangles) {
triangleVertexCounter = 0;
triangleIndices = new int[Triangle2D.NUM_VERTICES];
for (final var p1 : t.getVertices()) {
vertexCounter = 0;
for (final var p2 : vertices) {
if (p1 == p2) {
triangleIndices[triangleVertexCounter] = vertexCounter;
break;
}
vertexCounter++;
}
triangleVertexCounter++;
}
indices.add(triangleIndices);
}
}
}
/**
* Determines if provided triangle can be considered as an ear of the
* remaining polygon formed by provided vertices.
* An ear is usually a triangle located at a corner of a polygon.
* A triangle is considered an ear if no other vertex of the polygon lies
* within the triangle and if the triangle is not convex (is concave).
*
* @param triangle A triangle.
* @param polygonVertices A list of points forming the remaining polygon
* @return true if triangle is ear, false otherwise.
*/
private static boolean isEar(final Triangle2D triangle, final List<Point2D> polygonVertices) {
boolean isInside;
boolean isNotConvex;
// in a counterclockwise polygon, reversed orientation means that
// triangle is not convex and cannot be an ear
final var triangleVertices = triangle.getVertices();
// check that no points in the polygon (aside from points belonging to
// the triangle) lie inside the triangle
for (final var testPoint : polygonVertices) {
// Do not compare with polygon elements which are triangle points
// if end is reached then polygon and triangle is equal and hence the
// polygon is the ear
if (triangleVertices.contains(testPoint)) {
continue;
}
isInside = triangle.isInside(testPoint);
isNotConvex = triangle.areVerticesClockwise();
// if a point is inside the triangle or orientation is reversed, then
// it is not an ear
if (isInside || isNotConvex) {
return false;
}
}
// no points in the polygon where found inside the triangle and
// orientation is the same, so an ear is detected
return true;
}
}