Class QuadEdgeTriangle

1	/*
2	* Copyright (c) 2016 Vivid Solutions.
3	*
4	* All rights reserved. This program and the accompanying materials
5	* are made available under the terms of the Eclipse Public License 2.0
6	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
7	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
8	* and the Eclipse Distribution License is available at
9	*
10	* http://www.eclipse.org/org/documents/edl-v10.php.
11	*/
12
13	package org.locationtech.jts.triangulate.quadedge;
14
15	import java.util.ArrayList;
16	import java.util.Arrays;
17	import java.util.List;
18
19	import org.locationtech.jts.algorithm.PointLocation;
20	import org.locationtech.jts.geom.Coordinate;
21	import org.locationtech.jts.geom.Geometry;
22	import org.locationtech.jts.geom.GeometryFactory;
23	import org.locationtech.jts.geom.LineSegment;
24	import org.locationtech.jts.geom.LinearRing;
25	import org.locationtech.jts.geom.Polygon;
26
27
28	/**
29	* Models a triangle formed from {@link QuadEdge}s in a {@link QuadEdgeSubdivision}
30	* which forms a triangulation. The class provides methods to access the
31	* topological and geometric properties of the triangle and its neighbours in
32	* the triangulation. Triangle vertices are ordered in CCW orientation in the
33	* structure.
34	* <p>
35	* QuadEdgeTriangles support having an external data attribute attached to them.
36	* Alternatively, this class can be subclassed and attributes can
37	* be defined in the subclass. Subclasses will need to define
38	* their own <tt>BuilderVisitor</tt> class
39	* and <tt>createOn</tt> method.
40	*
41	* @author Martin Davis
42	* @version 1.0
43	*/
44	public class QuadEdgeTriangle
45	{
46	/**
47	* Creates {@link QuadEdgeTriangle}s for all facets of a
48	* {@link QuadEdgeSubdivision} representing a triangulation.
49	* The <tt>data</tt> attributes of the {@link QuadEdge}s in the subdivision
50	* will be set to point to the triangle which contains that edge.
51	* This allows tracing the neighbour triangles of any given triangle.
52	*
53	* @param subdiv
54	* the QuadEdgeSubdivision to create the triangles on.
55	* @return a List of the created QuadEdgeTriangles
56	*/
57	public static List createOn(QuadEdgeSubdivision subdiv)
58	{
59	QuadEdgeTriangleBuilderVisitor visitor = new QuadEdgeTriangleBuilderVisitor();
60	subdiv.visitTriangles(visitor, false);
61	return visitor.getTriangles();
62	}
63
64	/**
65	* Tests whether the point pt is contained in the triangle defined by 3
66	* {@link Vertex}es.
67	*
68	* @param tri
69	* an array containing at least 3 Vertexes
70	* @param pt
71	* the point to test
72	* @return true if the point is contained in the triangle
73	*/
74	public static boolean contains(Vertex[] tri, Coordinate pt) {
75	Coordinate[] ring = new Coordinate[] { tri[0].getCoordinate(),
76	tri[1].getCoordinate(), tri[2].getCoordinate(), tri[0].getCoordinate() };
77	return PointLocation.isInRing(pt, ring);
78	}
79
80	/**
81	* Tests whether the point pt is contained in the triangle defined by 3
82	* {@link QuadEdge}es.
83	*
84	* @param tri
85	* an array containing at least 3 QuadEdges
86	* @param pt
87	* the point to test
88	* @return true if the point is contained in the triangle
89	*/
90	public static boolean contains(QuadEdge[] tri, Coordinate pt) {
91	Coordinate[] ring = new Coordinate[] { tri[0].orig().getCoordinate(),
92	tri[1].orig().getCoordinate(), tri[2].orig().getCoordinate(),
93	tri[0].orig().getCoordinate() };
94	return PointLocation.isInRing(pt, ring);
95	}
96
97	public static Geometry toPolygon(Vertex[] v) {
98	Coordinate[] ringPts = new Coordinate[] { v[0].getCoordinate(),
99	v[1].getCoordinate(), v[2].getCoordinate(), v[0].getCoordinate() };
100	GeometryFactory fact = new GeometryFactory();
101	LinearRing ring = fact.createLinearRing(ringPts);
102	Polygon tri = fact.createPolygon(ring);
103	return tri;
104	}
105
106	public static Geometry toPolygon(QuadEdge[] e) {
107	Coordinate[] ringPts = new Coordinate[] { e[0].orig().getCoordinate(),
108	e[1].orig().getCoordinate(), e[2].orig().getCoordinate(),
109	e[0].orig().getCoordinate() };
110	GeometryFactory fact = new GeometryFactory();
111	LinearRing ring = fact.createLinearRing(ringPts);
112	Polygon tri = fact.createPolygon(ring);
113	return tri;
114	}
115
116	/**
117	* Finds the next index around the triangle. Index may be an edge or vertex
118	* index.
119	*
120	* @param index
121	* @return the next index
122	*/
123	public static int nextIndex(int index) {
124	return index = (index + 1) % 3;
125	}
126
127	private QuadEdge[] edge;
128	private Object data;
129
130	/**
131	* Creates a new triangle from the given edges.
132	*
133	* @param edge an array of the edges of the triangle in CCW order
134	*/
135	public QuadEdgeTriangle(QuadEdge[] edge) {
136	this.edge = (QuadEdge[]) Arrays.copyOf(edge, edge.length);
137	// link the quadedges back to this triangle
138	for (int i = 0; i < 3; i++) {
139	edge[i].setData(this);
140	}
141	}
142
143	/**
144	* Sets the external data value for this triangle.
145	*
146	* @param data an object containing external data
147	*/
148	public void setData(Object data) {
149	this.data = data;
150	}
151
152	/**
153	* Gets the external data value for this triangle.
154	*
155	* @return the data object
156	*/
157	public Object getData() {
158	return data;
159	}
160
161	public void kill() {
162	edge = null;
163	}
164
165	public boolean isLive() {
166	return edge != null;
167	}
168
169	public QuadEdge[] getEdges() {
170	return edge;
171	}
172
173	public QuadEdge getEdge(int i) {
174	return edge[i];
175	}
176
177	public Vertex getVertex(int i) {
178	return edge[i].orig();
179	}
180
181	/**
182	* Gets the vertices for this triangle.
183	*
184	* @return a new array containing the triangle vertices
185	*/
186	public Vertex[] getVertices() {
187	Vertex[] vert = new Vertex[3];
188	for (int i = 0; i < 3; i++) {
189	vert[i] = getVertex(i);
190	}
191	return vert;
192	}
193
194	public Coordinate getCoordinate(int i) {
195	return edge[i].orig().getCoordinate();
196	}
197
198	/**
199	* Gets the index for the given edge of this triangle
200	*
201	* @param e
202	* a QuadEdge
203	* @return the index of the edge in this triangle
204	* or -1 if the edge is not an edge of this triangle
205	*/
206	public int getEdgeIndex(QuadEdge e) {
207	for (int i = 0; i < 3; i++) {
208	if (edge[i] == e)
209	return i;
210	}
211	return -1;
212	}
213
214	/**
215	* Gets the index for the edge that starts at vertex v.
216	*
217	* @param v
218	* the vertex to find the edge for
219	* @return the index of the edge starting at the vertex
220	* or -1 if the vertex is not in the triangle
221	*/
222	public int getEdgeIndex(Vertex v) {
223	for (int i = 0; i < 3; i++) {
224	if (edge[i].orig() == v)
225	return i;
226	}
227	return -1;
228	}
229
230	public void getEdgeSegment(int i, LineSegment seg) {
231	seg.p0 = edge[i].orig().getCoordinate();
232	int nexti = (i + 1) % 3;
233	seg.p1 = edge[nexti].orig().getCoordinate();
234	}
235
236	public Coordinate[] getCoordinates() {
237	Coordinate[] pts = new Coordinate[4];
238	for (int i = 0; i < 3; i++) {
239	pts[i] = edge[i].orig().getCoordinate();
240	}
241	pts[3] = new Coordinate(pts[0]);
242	return pts;
243	}
244
245	public boolean contains(Coordinate pt) {
246	Coordinate[] ring = getCoordinates();
247	return PointLocation.isInRing(pt, ring);
248	}
249
250	public Polygon getGeometry(GeometryFactory fact) {
251	LinearRing ring = fact.createLinearRing(getCoordinates());
252	Polygon tri = fact.createPolygon(ring);
253	return tri;
254	}
255
256	public String toString() {
257	return getGeometry(new GeometryFactory()).toString();
258	}
259
260	/**
261	* Tests whether this triangle is adjacent to the outside of the subdivision.
262	*
263	* @return true if the triangle is adjacent to the subdivision exterior
264	*/
265	public boolean isBorder() {
266	for (int i = 0; i < 3; i++) {
267	if (getAdjacentTriangleAcrossEdge(i) == null)
268	return true;
269	}
270	return false;
271	}
272
273	public boolean isBorder(int i) {
274	return getAdjacentTriangleAcrossEdge(i) == null;
275	}
276
277	public QuadEdgeTriangle getAdjacentTriangleAcrossEdge(int edgeIndex) {
278	return (QuadEdgeTriangle) getEdge(edgeIndex).sym().getData();
279	}
280
281	public int getAdjacentTriangleEdgeIndex(int i) {
282	return getAdjacentTriangleAcrossEdge(i).getEdgeIndex(getEdge(i).sym());
283	}
284
285	/**
286	* Gets the triangles which are adjacent (include) to a
287	* given vertex of this triangle.
288	*
289	* @param vertexIndex the vertex to query
290	* @return a list of the vertex-adjacent triangles
291	*/
292	public List getTrianglesAdjacentToVertex(int vertexIndex) {
293	// Assert: isVertex
294	List adjTris = new ArrayList();
295
296	QuadEdge start = getEdge(vertexIndex);
297	QuadEdge qe = start;
298	do {
299	QuadEdgeTriangle adjTri = (QuadEdgeTriangle) qe.getData();
300	if (adjTri != null) {
301	adjTris.add(adjTri);
302	}
303	qe = qe.oNext();
304	} while (qe != start);
305
306	return adjTris;
307
308	}
309
310	/**
311	* Gets the neighbours of this triangle. If there is no neighbour triangle,
312	* the array element is <code>null</code>
313	*
314	* @return an array containing the 3 neighbours of this triangle
315	*/
316	public QuadEdgeTriangle[] getNeighbours() {
317	QuadEdgeTriangle[] neigh = new QuadEdgeTriangle[3];
318	for (int i = 0; i < 3; i++) {
319	neigh[i] = (QuadEdgeTriangle) getEdge(i).sym().getData();
320	}
321	return neigh;
322	}
323
324	private static class QuadEdgeTriangleBuilderVisitor implements TriangleVisitor {
325	private List triangles = new ArrayList();
326
327	public QuadEdgeTriangleBuilderVisitor() {
328	}
329
330	public void visit(QuadEdge[] edges) {
331	triangles.add(new QuadEdgeTriangle(edges));
332	}
333
334	public List getTriangles() {
335	return triangles;
336	}
337	}
338	}
339
340
341