QuadEdgeTriangle.java
/*
* Copyright (c) 2016 Vivid Solutions.
*
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License 2.0
* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
* and the Eclipse Distribution License is available at
*
* http://www.eclipse.org/org/documents/edl-v10.php.
*/
package org.locationtech.jts.triangulate.quadedge;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import org.locationtech.jts.algorithm.PointLocation;
import org.locationtech.jts.geom.Coordinate;
import org.locationtech.jts.geom.Geometry;
import org.locationtech.jts.geom.GeometryFactory;
import org.locationtech.jts.geom.LineSegment;
import org.locationtech.jts.geom.LinearRing;
import org.locationtech.jts.geom.Polygon;
/**
* Models a triangle formed from {@link QuadEdge}s in a {@link QuadEdgeSubdivision}
* which forms a triangulation. The class provides methods to access the
* topological and geometric properties of the triangle and its neighbours in
* the triangulation. Triangle vertices are ordered in CCW orientation in the
* structure.
* <p>
* QuadEdgeTriangles support having an external data attribute attached to them.
* Alternatively, this class can be subclassed and attributes can
* be defined in the subclass. Subclasses will need to define
* their own <tt>BuilderVisitor</tt> class
* and <tt>createOn</tt> method.
*
* @author Martin Davis
* @version 1.0
*/
public class QuadEdgeTriangle
{
/**
* Creates {@link QuadEdgeTriangle}s for all facets of a
* {@link QuadEdgeSubdivision} representing a triangulation.
* The <tt>data</tt> attributes of the {@link QuadEdge}s in the subdivision
* will be set to point to the triangle which contains that edge.
* This allows tracing the neighbour triangles of any given triangle.
*
* @param subdiv
* the QuadEdgeSubdivision to create the triangles on.
* @return a List of the created QuadEdgeTriangles
*/
public static List createOn(QuadEdgeSubdivision subdiv)
{
QuadEdgeTriangleBuilderVisitor visitor = new QuadEdgeTriangleBuilderVisitor();
subdiv.visitTriangles(visitor, false);
return visitor.getTriangles();
}
/**
* Tests whether the point pt is contained in the triangle defined by 3
* {@link Vertex}es.
*
* @param tri
* an array containing at least 3 Vertexes
* @param pt
* the point to test
* @return true if the point is contained in the triangle
*/
public static boolean contains(Vertex[] tri, Coordinate pt) {
Coordinate[] ring = new Coordinate[] { tri[0].getCoordinate(),
tri[1].getCoordinate(), tri[2].getCoordinate(), tri[0].getCoordinate() };
return PointLocation.isInRing(pt, ring);
}
/**
* Tests whether the point pt is contained in the triangle defined by 3
* {@link QuadEdge}es.
*
* @param tri
* an array containing at least 3 QuadEdges
* @param pt
* the point to test
* @return true if the point is contained in the triangle
*/
public static boolean contains(QuadEdge[] tri, Coordinate pt) {
Coordinate[] ring = new Coordinate[] { tri[0].orig().getCoordinate(),
tri[1].orig().getCoordinate(), tri[2].orig().getCoordinate(),
tri[0].orig().getCoordinate() };
return PointLocation.isInRing(pt, ring);
}
public static Geometry toPolygon(Vertex[] v) {
Coordinate[] ringPts = new Coordinate[] { v[0].getCoordinate(),
v[1].getCoordinate(), v[2].getCoordinate(), v[0].getCoordinate() };
GeometryFactory fact = new GeometryFactory();
LinearRing ring = fact.createLinearRing(ringPts);
Polygon tri = fact.createPolygon(ring);
return tri;
}
public static Geometry toPolygon(QuadEdge[] e) {
Coordinate[] ringPts = new Coordinate[] { e[0].orig().getCoordinate(),
e[1].orig().getCoordinate(), e[2].orig().getCoordinate(),
e[0].orig().getCoordinate() };
GeometryFactory fact = new GeometryFactory();
LinearRing ring = fact.createLinearRing(ringPts);
Polygon tri = fact.createPolygon(ring);
return tri;
}
/**
* Finds the next index around the triangle. Index may be an edge or vertex
* index.
*
* @param index
* @return the next index
*/
public static int nextIndex(int index) {
return index = (index + 1) % 3;
}
private QuadEdge[] edge;
private Object data;
/**
* Creates a new triangle from the given edges.
*
* @param edge an array of the edges of the triangle in CCW order
*/
public QuadEdgeTriangle(QuadEdge[] edge) {
this.edge = (QuadEdge[]) Arrays.copyOf(edge, edge.length);
// link the quadedges back to this triangle
for (int i = 0; i < 3; i++) {
edge[i].setData(this);
}
}
/**
* Sets the external data value for this triangle.
*
* @param data an object containing external data
*/
public void setData(Object data) {
this.data = data;
}
/**
* Gets the external data value for this triangle.
*
* @return the data object
*/
public Object getData() {
return data;
}
public void kill() {
edge = null;
}
public boolean isLive() {
return edge != null;
}
public QuadEdge[] getEdges() {
return edge;
}
public QuadEdge getEdge(int i) {
return edge[i];
}
public Vertex getVertex(int i) {
return edge[i].orig();
}
/**
* Gets the vertices for this triangle.
*
* @return a new array containing the triangle vertices
*/
public Vertex[] getVertices() {
Vertex[] vert = new Vertex[3];
for (int i = 0; i < 3; i++) {
vert[i] = getVertex(i);
}
return vert;
}
public Coordinate getCoordinate(int i) {
return edge[i].orig().getCoordinate();
}
/**
* Gets the index for the given edge of this triangle
*
* @param e
* a QuadEdge
* @return the index of the edge in this triangle
* or -1 if the edge is not an edge of this triangle
*/
public int getEdgeIndex(QuadEdge e) {
for (int i = 0; i < 3; i++) {
if (edge[i] == e)
return i;
}
return -1;
}
/**
* Gets the index for the edge that starts at vertex v.
*
* @param v
* the vertex to find the edge for
* @return the index of the edge starting at the vertex
* or -1 if the vertex is not in the triangle
*/
public int getEdgeIndex(Vertex v) {
for (int i = 0; i < 3; i++) {
if (edge[i].orig() == v)
return i;
}
return -1;
}
public void getEdgeSegment(int i, LineSegment seg) {
seg.p0 = edge[i].orig().getCoordinate();
int nexti = (i + 1) % 3;
seg.p1 = edge[nexti].orig().getCoordinate();
}
public Coordinate[] getCoordinates() {
Coordinate[] pts = new Coordinate[4];
for (int i = 0; i < 3; i++) {
pts[i] = edge[i].orig().getCoordinate();
}
pts[3] = new Coordinate(pts[0]);
return pts;
}
public boolean contains(Coordinate pt) {
Coordinate[] ring = getCoordinates();
return PointLocation.isInRing(pt, ring);
}
public Polygon getGeometry(GeometryFactory fact) {
LinearRing ring = fact.createLinearRing(getCoordinates());
Polygon tri = fact.createPolygon(ring);
return tri;
}
public String toString() {
return getGeometry(new GeometryFactory()).toString();
}
/**
* Tests whether this triangle is adjacent to the outside of the subdivision.
*
* @return true if the triangle is adjacent to the subdivision exterior
*/
public boolean isBorder() {
for (int i = 0; i < 3; i++) {
if (getAdjacentTriangleAcrossEdge(i) == null)
return true;
}
return false;
}
public boolean isBorder(int i) {
return getAdjacentTriangleAcrossEdge(i) == null;
}
public QuadEdgeTriangle getAdjacentTriangleAcrossEdge(int edgeIndex) {
return (QuadEdgeTriangle) getEdge(edgeIndex).sym().getData();
}
public int getAdjacentTriangleEdgeIndex(int i) {
return getAdjacentTriangleAcrossEdge(i).getEdgeIndex(getEdge(i).sym());
}
/**
* Gets the triangles which are adjacent (include) to a
* given vertex of this triangle.
*
* @param vertexIndex the vertex to query
* @return a list of the vertex-adjacent triangles
*/
public List getTrianglesAdjacentToVertex(int vertexIndex) {
// Assert: isVertex
List adjTris = new ArrayList();
QuadEdge start = getEdge(vertexIndex);
QuadEdge qe = start;
do {
QuadEdgeTriangle adjTri = (QuadEdgeTriangle) qe.getData();
if (adjTri != null) {
adjTris.add(adjTri);
}
qe = qe.oNext();
} while (qe != start);
return adjTris;
}
/**
* Gets the neighbours of this triangle. If there is no neighbour triangle,
* the array element is <code>null</code>
*
* @return an array containing the 3 neighbours of this triangle
*/
public QuadEdgeTriangle[] getNeighbours() {
QuadEdgeTriangle[] neigh = new QuadEdgeTriangle[3];
for (int i = 0; i < 3; i++) {
neigh[i] = (QuadEdgeTriangle) getEdge(i).sym().getData();
}
return neigh;
}
private static class QuadEdgeTriangleBuilderVisitor implements TriangleVisitor {
private List triangles = new ArrayList();
public QuadEdgeTriangleBuilderVisitor() {
}
public void visit(QuadEdge[] edges) {
triangles.add(new QuadEdgeTriangle(edges));
}
public List getTriangles() {
return triangles;
}
}
}