Class QuadEdgeSubdivision

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.Collection;
17	import java.util.HashSet;
18	import java.util.Iterator;
19	import java.util.List;
20	import java.util.Set;
21	import java.util.Stack;
22
23	import org.locationtech.jts.geom.Coordinate;
24	import org.locationtech.jts.geom.CoordinateList;
25	import org.locationtech.jts.geom.Envelope;
26	import org.locationtech.jts.geom.Geometry;
27	import org.locationtech.jts.geom.GeometryCollection;
28	import org.locationtech.jts.geom.GeometryFactory;
29	import org.locationtech.jts.geom.LineSegment;
30	import org.locationtech.jts.geom.LineString;
31	import org.locationtech.jts.geom.MultiLineString;
32	import org.locationtech.jts.geom.Polygon;
33	import org.locationtech.jts.geom.Triangle;
34	import org.locationtech.jts.io.WKTWriter;
35
36
37	/**
38	* A class that contains the {@link QuadEdge}s representing a planar
39	* subdivision that models a triangulation.
40	* The subdivision is constructed using the
41	* quadedge algebra defined in the class {@link QuadEdge}.
42	* All metric calculations
43	* are done in the {@link Vertex} class.
44	* In addition to a triangulation, subdivisions
45	* support extraction of Voronoi diagrams.
46	* This is easily accomplished, since the Voronoi diagram is the dual
47	* of the Delaunay triangulation.
48	* <p>
49	* Subdivisions can be provided with a tolerance value. Inserted vertices which
50	* are closer than this value to vertices already in the subdivision will be
51	* ignored. Using a suitable tolerance value can prevent robustness failures
52	* from happening during Delaunay triangulation.
53	* <p>
54	* Subdivisions maintain a <b>frame</b> triangle around the client-created
55	* edges. The frame is used to provide a bounded "container" for all edges
56	* within a TIN. Normally the frame edges, frame connecting edges, and frame
57	* triangles are not included in client processing.
58	*
59	* @author David Skea
60	* @author Martin Davis
61	*/
62	public class QuadEdgeSubdivision {
63	/**
64	* Gets the edges for the triangle to the left of the given {@link QuadEdge}.
65	*
66	* @param startQE
67	* @param triEdge
68	*
69	* @throws IllegalArgumentException
70	* if the edges do not form a triangle
71	*/
72	public static void getTriangleEdges(QuadEdge startQE, QuadEdge[] triEdge) {
73	triEdge[0] = startQE;
74	triEdge[1] = triEdge[0].lNext();
75	triEdge[2] = triEdge[1].lNext();
76	if (triEdge[2].lNext() != triEdge[0])
77	throw new IllegalArgumentException("Edges do not form a triangle");
78	}
79
80	private final static double EDGE_COINCIDENCE_TOL_FACTOR = 1000;
81
82	// debugging only - preserve current subdiv statically
83	// private static QuadEdgeSubdivision currentSubdiv;
84
85	// used for edge extraction to ensure edge uniqueness
86	private int visitedKey = 0;
87	// private Set quadEdges = new HashSet();
88	private List quadEdges = new ArrayList();
89	private QuadEdge startingEdge;
90	private double tolerance;
91	private double edgeCoincidenceTolerance;
92	private Vertex[] frameVertex = new Vertex[3];
93	private Envelope frameEnv;
94	private QuadEdgeLocator locator = null;
95
96	/**
97	* Creates a new instance of a quad-edge subdivision based on a frame triangle
98	* that encloses a supplied bounding box. A new super-bounding box that
99	* contains the triangle is computed and stored.
100	*
101	* @param env
102	* the bounding box to surround
103	* @param tolerance
104	* the tolerance value for determining if two sites are equal
105	*/
106	public QuadEdgeSubdivision(Envelope env, double tolerance) {
107	// currentSubdiv = this;
108	this.tolerance = tolerance;
109	edgeCoincidenceTolerance = tolerance / EDGE_COINCIDENCE_TOL_FACTOR;
110
111	createFrame(env);
112
113	startingEdge = initSubdiv();
114	locator = new LastFoundQuadEdgeLocator(this);
115	}
116
117	private void createFrame(Envelope env)
118	{
119	double deltaX = env.getWidth();
120	double deltaY = env.getHeight();
121	double offset = 0.0;
122	if (deltaX > deltaY) {
123	offset = deltaX * 10.0;
124	} else {
125	offset = deltaY * 10.0;
126	}
127
128	frameVertex[0] = new Vertex((env.getMaxX() + env.getMinX()) / 2.0, env
129	.getMaxY()
130	+ offset);
131	frameVertex[1] = new Vertex(env.getMinX() - offset, env.getMinY() - offset);
132	frameVertex[2] = new Vertex(env.getMaxX() + offset, env.getMinY() - offset);
133
134	frameEnv = new Envelope(frameVertex[0].getCoordinate(), frameVertex[1]
135	.getCoordinate());
136	frameEnv.expandToInclude(frameVertex[2].getCoordinate());
137	}
138
139	private QuadEdge initSubdiv()
140	{
141	// build initial subdivision from frame
142	QuadEdge ea = makeEdge(frameVertex[0], frameVertex[1]);
143	QuadEdge eb = makeEdge(frameVertex[1], frameVertex[2]);
144	QuadEdge.splice(ea.sym(), eb);
145	QuadEdge ec = makeEdge(frameVertex[2], frameVertex[0]);
146	QuadEdge.splice(eb.sym(), ec);
147	QuadEdge.splice(ec.sym(), ea);
148	return ea;
149	}
150
151	/**
152	* Gets the vertex-equality tolerance value
153	* used in this subdivision
154	*
155	* @return the tolerance value
156	*/
157	public double getTolerance() {
158	return tolerance;
159	}
160
161	/**
162	* Gets the envelope of the Subdivision (including the frame).
163	*
164	* @return the envelope
165	*/
166	public Envelope getEnvelope() {
167	return new Envelope(frameEnv);
168	}
169
170	/**
171	* Gets the collection of base {@link QuadEdge}s (one for every pair of
172	* vertices which is connected).
173	*
174	* @return a collection of QuadEdges
175	*/
176	public Collection getEdges() {
177	return quadEdges;
178	}
179
180	/**
181	* Sets the {@link QuadEdgeLocator} to use for locating containing triangles
182	* in this subdivision.
183	*
184	* @param locator
185	* a QuadEdgeLocator
186	*/
187	public void setLocator(QuadEdgeLocator locator) {
188	this.locator = locator;
189	}
190
191	/**
192	* Creates a new quadedge, recording it in the edges list.
193	*
194	* @param o
195	* @param d
196	* @return a new quadedge
197	*/
198	public QuadEdge makeEdge(Vertex o, Vertex d) {
199	QuadEdge q = QuadEdge.makeEdge(o, d);
200	quadEdges.add(q);
201	return q;
202	}
203
204	/**
205	* Creates a new QuadEdge connecting the destination of a to the origin of b,
206	* in such a way that all three have the same left face after the connection
207	* is complete. The quadedge is recorded in the edges list.
208	*
209	* @param a
210	* @param b
211	* @return a quadedge
212	*/
213	public QuadEdge connect(QuadEdge a, QuadEdge b) {
214	QuadEdge q = QuadEdge.connect(a, b);
215	quadEdges.add(q);
216	return q;
217	}
218
219	/**
220	* Deletes a quadedge from the subdivision. Linked quadedges are updated to
221	* reflect the deletion.
222	*
223	* @param e
224	* the quadedge to delete
225	*/
226	public void delete(QuadEdge e) {
227	QuadEdge.splice(e, e.oPrev());
228	QuadEdge.splice(e.sym(), e.sym().oPrev());
229
230	QuadEdge eSym = e.sym();
231	QuadEdge eRot = e.rot();
232	QuadEdge eRotSym = e.rot().sym();
233
234	// this is inefficient on an ArrayList, but this method should be called infrequently
235	quadEdges.remove(e);
236	quadEdges.remove(eSym);
237	quadEdges.remove(eRot);
238	quadEdges.remove(eRotSym);
239
240	e.delete();
241	eSym.delete();
242	eRot.delete();
243	eRotSym.delete();
244	}
245
246	/**
247	* Locates an edge of a triangle which contains a location
248	* specified by a Vertex v.
249	* The edge returned has the
250	* property that either v is on e, or e is an edge of a triangle containing v.
251	* The search starts from startEdge amd proceeds on the general direction of v.
252	* <p>
253	* This locate algorithm relies on the subdivision being Delaunay. For
254	* non-Delaunay subdivisions, this may loop for ever.
255	*
256	* @param v the location to search for
257	* @param startEdge an edge of the subdivision to start searching at
258	* @return a QuadEdge which contains v, or is on the edge of a triangle containing v
259	* @throws LocateFailureException
260	* if the location algorithm fails to converge in a reasonable
261	* number of iterations
262	*/
263	public QuadEdge locateFromEdge(Vertex v, QuadEdge startEdge) {
264	int iter = 0;
265	int maxIter = quadEdges.size();
266
267	QuadEdge e = startEdge;
268
269	while (true) {
270	iter++;
271
272	/**
273	* So far it has always been the case that failure to locate indicates an
274	* invalid subdivision. So just fail completely. (An alternative would be
275	* to perform an exhaustive search for the containing triangle, but this
276	* would mask errors in the subdivision topology)
277	*
278	* This can also happen if two vertices are located very close together,
279	* since the orientation predicates may experience precision failures.
280	*/
281	if (iter > maxIter) {
282	throw new LocateFailureException(e.toLineSegment());
283	// String msg = "Locate failed to converge (at edge: " + e + ").
284	// Possible causes include invalid Subdivision topology or very close
285	// sites";
286	// System.err.println(msg);
287	// dumpTriangles();
288	}
289
290	if ((v.equals(e.orig())) \|\| (v.equals(e.dest()))) {
291	break;
292	} else if (v.rightOf(e)) {
293	e = e.sym();
294	} else if (!v.rightOf(e.oNext())) {
295	e = e.oNext();
296	} else if (!v.rightOf(e.dPrev())) {
297	e = e.dPrev();
298	} else {
299	// on edge or in triangle containing edge
300	break;
301	}
302	}
303	// System.out.println("Locate count: " + iter);
304	return e;
305	}
306
307	/**
308	* Finds a quadedge of a triangle containing a location
309	* specified by a {@link Vertex}, if one exists.
310	*
311	* @param v the vertex to locate
312	* @return a quadedge on the edge of a triangle which touches or contains the location
313	* or null if no such triangle exists
314	*/
315	public QuadEdge locate(Vertex v) {
316	return locator.locate(v);
317	}
318
319	/**
320	* Finds a quadedge of a triangle containing a location
321	* specified by a {@link Coordinate}, if one exists.
322	*
323	* @param p the Coordinate to locate
324	* @return a quadedge on the edge of a triangle which touches or contains the location
325	* or null if no such triangle exists
326	*/
327	public QuadEdge locate(Coordinate p) {
328	return locator.locate(new Vertex(p));
329	}
330
331	/**
332	* Locates the edge between the given vertices, if it exists in the
333	* subdivision.
334	*
335	* @param p0 a coordinate
336	* @param p1 another coordinate
337	* @return the edge joining the coordinates, if present
338	* or null if no such edge exists
339	*/
340	public QuadEdge locate(Coordinate p0, Coordinate p1) {
341	// find an edge containing one of the points
342	QuadEdge e = locator.locate(new Vertex(p0));
343	if (e == null)
344	return null;
345
346	// normalize so that p0 is origin of base edge
347	QuadEdge base = e;
348	if (e.dest().getCoordinate().equals2D(p0))
349	base = e.sym();
350	// check all edges around origin of base edge
351	QuadEdge locEdge = base;
352	do {
353	if (locEdge.dest().getCoordinate().equals2D(p1))
354	return locEdge;
355	locEdge = locEdge.oNext();
356	} while (locEdge != base);
357	return null;
358	}
359
360	/**
361	* Inserts a new site into the Subdivision, connecting it to the vertices of
362	* the containing triangle (or quadrilateral, if the split point falls on an
363	* existing edge).
364	* <p>
365	* This method does NOT maintain the Delaunay condition. If desired, this must
366	* be checked and enforced by the caller.
367	* <p>
368	* This method does NOT check if the inserted vertex falls on an edge. This
369	* must be checked by the caller, since this situation may cause erroneous
370	* triangulation
371	*
372	* @param v
373	* the vertex to insert
374	* @return a new quad edge terminating in v
375	*/
376	public QuadEdge insertSite(Vertex v) {
377	QuadEdge e = locate(v);
378
379	if ((v.equals(e.orig(), tolerance)) \|\| (v.equals(e.dest(), tolerance))) {
380	return e; // point already in subdivision.
381	}
382
383	// Connect the new point to the vertices of the containing
384	// triangle (or quadrilateral, if the new point fell on an
385	// existing edge.)
386	QuadEdge base = makeEdge(e.orig(), v);
387	QuadEdge.splice(base, e);
388	QuadEdge startEdge = base;
389	do {
390	base = connect(e, base.sym());
391	e = base.oPrev();
392	} while (e.lNext() != startEdge);
393
394	return startEdge;
395	}
396
397	/**
398	* Tests whether a QuadEdge is an edge incident on a frame triangle vertex.
399	*
400	* @param e
401	* the edge to test
402	* @return true if the edge is connected to the frame triangle
403	*/
404	public boolean isFrameEdge(QuadEdge e) {
405	if (isFrameVertex(e.orig()) \|\| isFrameVertex(e.dest()))
406	return true;
407	return false;
408	}
409
410	/**
411	* Tests whether a QuadEdge is an edge on the border of the frame facets and
412	* the internal facets. E.g. an edge which does not itself touch a frame
413	* vertex, but which touches an edge which does.
414	*
415	* @param e
416	* the edge to test
417	* @return true if the edge is on the border of the frame
418	*/
419	public boolean isFrameBorderEdge(QuadEdge e) {
420	// MD debugging
421	QuadEdge[] leftTri = new QuadEdge[3];
422	getTriangleEdges(e, leftTri);
423	// System.out.println(new QuadEdgeTriangle(leftTri).toString());
424	QuadEdge[] rightTri = new QuadEdge[3];
425	getTriangleEdges(e.sym(), rightTri);
426	// System.out.println(new QuadEdgeTriangle(rightTri).toString());
427
428	// check other vertex of triangle to left of edge
429	Vertex vLeftTriOther = e.lNext().dest();
430	if (isFrameVertex(vLeftTriOther))
431	return true;
432	// check other vertex of triangle to right of edge
433	Vertex vRightTriOther = e.sym().lNext().dest();
434	if (isFrameVertex(vRightTriOther))
435	return true;
436
437	return false;
438	}
439
440	/**
441	* Tests whether a vertex is a vertex of the outer triangle.
442	*
443	* @param v
444	* the vertex to test
445	* @return true if the vertex is an outer triangle vertex
446	*/
447	public boolean isFrameVertex(Vertex v) {
448	if (v.equals(frameVertex[0]))
449	return true;
450	if (v.equals(frameVertex[1]))
451	return true;
452	if (v.equals(frameVertex[2]))
453	return true;
454	return false;
455	}
456
457	private LineSegment seg = new LineSegment();
458
459	/**
460	* Tests whether a {@link Coordinate} lies on a {@link QuadEdge}, up to a
461	* tolerance determined by the subdivision tolerance.
462	*
463	* @param e
464	* a QuadEdge
465	* @param p
466	* a point
467	* @return true if the vertex lies on the edge
468	*/
469	public boolean isOnEdge(QuadEdge e, Coordinate p) {
470	seg.setCoordinates(e.orig().getCoordinate(), e.dest().getCoordinate());
471	double dist = seg.distance(p);
472	// heuristic (hack?)
473	return dist < edgeCoincidenceTolerance;
474	}
475
476	/**
477	* Tests whether a {@link Vertex} is the start or end vertex of a
478	* {@link QuadEdge}, up to the subdivision tolerance distance.
479	*
480	* @param e
481	* @param v
482	* @return true if the vertex is a endpoint of the edge
483	*/
484	public boolean isVertexOfEdge(QuadEdge e, Vertex v) {
485	if ((v.equals(e.orig(), tolerance)) \|\| (v.equals(e.dest(), tolerance))) {
486	return true;
487	}
488	return false;
489	}
490
491	/**
492	* Gets the unique {@link Vertex}es in the subdivision,
493	* including the frame vertices if desired.
494	*
495	* @param includeFrame
496	* true if the frame vertices should be included
497	* @return a collection of the subdivision vertices
498	*
499	* @see #getVertexUniqueEdges
500	*/
501	public Collection getVertices(boolean includeFrame)
502	{
503	Set vertices = new HashSet();
504	for (Iterator i = quadEdges.iterator(); i.hasNext();) {
505	QuadEdge qe = (QuadEdge) i.next();
506	Vertex v = qe.orig();
507	//System.out.println(v);
508	if (includeFrame \|\| ! isFrameVertex(v))
509	vertices.add(v);
510
511	/**
512	* Inspect the sym edge as well, since it is
513	* possible that a vertex is only at the
514	* dest of all tracked quadedges.
515	*/
516	Vertex vd = qe.dest();
517	//System.out.println(vd);
518	if (includeFrame \|\| ! isFrameVertex(vd))
519	vertices.add(vd);
520	}
521	return vertices;
522	}
523
524	/**
525	* Gets a collection of {@link QuadEdge}s whose origin
526	* vertices are a unique set which includes
527	* all vertices in the subdivision.
528	* The frame vertices can be included if required.
529	* <p>
530	* This is useful for algorithms which require traversing the
531	* subdivision starting at all vertices.
532	* Returning a quadedge for each vertex
533	* is more efficient than
534	* the alternative of finding the actual vertices
535	* using {@link #getVertices} and then locating
536	* quadedges attached to them.
537	*
538	* @param includeFrame true if the frame vertices should be included
539	* @return a collection of QuadEdge with the vertices of the subdivision as their origins
540	*/
541	public List getVertexUniqueEdges(boolean includeFrame)
542	{
543	List edges = new ArrayList();
544	Set visitedVertices = new HashSet();
545	for (Iterator i = quadEdges.iterator(); i.hasNext();) {
546	QuadEdge qe = (QuadEdge) i.next();
547	Vertex v = qe.orig();
548	//System.out.println(v);
549	if (! visitedVertices.contains(v)) {
550	visitedVertices.add(v);
551	if (includeFrame \|\| ! isFrameVertex(v)) {
552	edges.add(qe);
553	}
554	}
555
556	/**
557	* Inspect the sym edge as well, since it is
558	* possible that a vertex is only at the
559	* dest of all tracked quadedges.
560	*/
561	QuadEdge qd = qe.sym();
562	Vertex vd = qd.orig();
563	//System.out.println(vd);
564	if (! visitedVertices.contains(vd)) {
565	visitedVertices.add(vd);
566	if (includeFrame \|\| ! isFrameVertex(vd)) {
567	edges.add(qd);
568	}
569	}
570	}
571	return edges;
572	}
573
574	/**
575	* Gets all primary quadedges in the subdivision.
576	* A primary edge is a {@link QuadEdge}
577	* which occupies the 0'th position in its array of associated quadedges.
578	* These provide the unique geometric edges of the triangulation.
579	*
580	* @param includeFrame true if the frame edges are to be included
581	* @return a List of QuadEdges
582	*/
583	public List getPrimaryEdges(boolean includeFrame) {
584	visitedKey++;
585
586	List edges = new ArrayList();
587	Stack edgeStack = new Stack();
588	edgeStack.push(startingEdge);
589
590	Set visitedEdges = new HashSet();
591
592	while (!edgeStack.empty()) {
593	QuadEdge edge = (QuadEdge) edgeStack.pop();
594	if (! visitedEdges.contains(edge)) {
595	QuadEdge priQE = edge.getPrimary();
596
597	if (includeFrame \|\| ! isFrameEdge(priQE))
598	edges.add(priQE);
599
600	edgeStack.push(edge.oNext());
601	edgeStack.push(edge.sym().oNext());
602
603	visitedEdges.add(edge);
604	visitedEdges.add(edge.sym());
605	}
606	}
607	return edges;
608	}
609
610	/**
611	* A TriangleVisitor which computes and sets the
612	* circumcentre as the origin of the dual
613	* edges originating in each triangle.
614	*
615	* @author mbdavis
616	*
617	*/
618	private static class TriangleCircumcentreVisitor implements TriangleVisitor
619	{
620	public TriangleCircumcentreVisitor() {
621	}
622
623	public void visit(QuadEdge[] triEdges)
624	{
625	Coordinate a = triEdges[0].orig().getCoordinate();
626	Coordinate b = triEdges[1].orig().getCoordinate();
627	Coordinate c = triEdges[2].orig().getCoordinate();
628
629	// TODO: choose the most accurate circumcentre based on the edges
630	Coordinate cc = Triangle.circumcentreDD(a, b, c);
631	Vertex ccVertex = new Vertex(cc);
632	// save the circumcentre as the origin for the dual edges originating in this triangle
633	for (int i = 0; i < 3; i++) {
634	triEdges[i].rot().setOrig(ccVertex);
635	}
636	}
637	}
638
639	/*****************************************************************************
640	* Visitors
641	****************************************************************************/
642
643	public void visitTriangles(TriangleVisitor triVisitor,
644	boolean includeFrame) {
645	visitedKey++;
646
647	// visited flag is used to record visited edges of triangles
648	// setVisitedAll(false);
649	Stack edgeStack = new Stack();
650	edgeStack.push(startingEdge);
651
652	Set visitedEdges = new HashSet();
653
654	while (!edgeStack.empty()) {
655	QuadEdge edge = (QuadEdge) edgeStack.pop();
656	if (! visitedEdges.contains(edge)) {
657	QuadEdge[] triEdges = fetchTriangleToVisit(edge, edgeStack,
658	includeFrame, visitedEdges);
659	if (triEdges != null)
660	triVisitor.visit(triEdges);
661	}
662	}
663	}
664
665	/**
666	* The quadedges forming a single triangle.
667	* Only one visitor is allowed to be active at a
668	* time, so this is safe.
669	*/
670	private QuadEdge[] triEdges = new QuadEdge[3];
671
672	/**
673	* Stores the edges for a visited triangle. Also pushes sym (neighbour) edges
674	* on stack to visit later.
675	*
676	* @param edge
677	* @param edgeStack
678	* @param includeFrame
679	* @return the visited triangle edges
680	* or null if the triangle should not be visited (for instance, if it is
681	* outer)
682	*/
683	private QuadEdge[] fetchTriangleToVisit(QuadEdge edge, Stack edgeStack,
684	boolean includeFrame, Set visitedEdges) {
685	QuadEdge curr = edge;
686	int edgeCount = 0;
687	boolean isFrame = false;
688	do {
689	triEdges[edgeCount] = curr;
690
691	if (isFrameEdge(curr))
692	isFrame = true;
693
694	// push sym edges to visit next
695	QuadEdge sym = curr.sym();
696	if (! visitedEdges.contains(sym))
697	edgeStack.push(sym);
698
699	// mark this edge as visited
700	visitedEdges.add(curr);
701
702	edgeCount++;
703	curr = curr.lNext();
704	} while (curr != edge);
705
706	if (isFrame && !includeFrame)
707	return null;
708	return triEdges;
709	}
710
711	/**
712	* Gets a list of the triangles
713	* in the subdivision, specified as
714	* an array of the primary quadedges around the triangle.
715	*
716	* @param includeFrame
717	* true if the frame triangles should be included
718	* @return a List of QuadEdge[3] arrays
719	*/
720	public List getTriangleEdges(boolean includeFrame) {
721	TriangleEdgesListVisitor visitor = new TriangleEdgesListVisitor();
722	visitTriangles(visitor, includeFrame);
723	return visitor.getTriangleEdges();
724	}
725
726	private static class TriangleEdgesListVisitor implements TriangleVisitor {
727	private List triList = new ArrayList();
728
729	public void visit(QuadEdge[] triEdges) {
730	triList.add(triEdges);
731	}
732
733	public List getTriangleEdges() {
734	return triList;
735	}
736	}
737
738	/**
739	* Gets a list of the triangles in the subdivision,
740	* specified as an array of the triangle {@link Vertex}es.
741	*
742	* @param includeFrame
743	* true if the frame triangles should be included
744	* @return a List of Vertex[3] arrays
745	*/
746	public List getTriangleVertices(boolean includeFrame) {
747	TriangleVertexListVisitor visitor = new TriangleVertexListVisitor();
748	visitTriangles(visitor, includeFrame);
749	return visitor.getTriangleVertices();
750	}
751
752	private static class TriangleVertexListVisitor implements TriangleVisitor {
753	private List triList = new ArrayList();
754
755	public void visit(QuadEdge[] triEdges) {
756	triList.add(new Vertex[] { triEdges[0].orig(), triEdges[1].orig(),
757	triEdges[2].orig() });
758	}
759
760	public List getTriangleVertices() {
761	return triList;
762	}
763	}
764
765	/**
766	* Gets the coordinates for each triangle in the subdivision as an array.
767	*
768	* @param includeFrame
769	* true if the frame triangles should be included
770	* @return a list of Coordinate[4] representing each triangle
771	*/
772	public List getTriangleCoordinates(boolean includeFrame) {
773	TriangleCoordinatesVisitor visitor = new TriangleCoordinatesVisitor();
774	visitTriangles(visitor, includeFrame);
775	return visitor.getTriangles();
776	}
777
778	private static class TriangleCoordinatesVisitor implements TriangleVisitor {
779	private CoordinateList coordList = new CoordinateList();
780
781	private List triCoords = new ArrayList();
782
783	public TriangleCoordinatesVisitor() {
784	}
785
786	public void visit(QuadEdge[] triEdges) {
787	coordList.clear();
788	for (int i = 0; i < 3; i++) {
789	Vertex v = triEdges[i].orig();
790	coordList.add(v.getCoordinate());
791	}
792	if (coordList.size() > 0) {
793	coordList.closeRing();
794	Coordinate[] pts = coordList.toCoordinateArray();
795	if (pts.length != 4) {
796	//checkTriangleSize(pts);
797	return;
798	}
799
800	triCoords.add(pts);
801	}
802	}
803
804	private void checkTriangleSize(Coordinate[] pts)
805	{
806	String loc = "";
807	if (pts.length >= 2)
808	loc = WKTWriter.toLineString(pts[0], pts[1]);
809	else {
810	if (pts.length >= 1)
811	loc = WKTWriter.toPoint(pts[0]);
812	}
813	// Assert.isTrue(pts.length == 4, "Too few points for visited triangle at " + loc);
814	//com.vividsolutions.jts.util.Debug.println("too few points for triangle at " + loc);
815	}
816
817	public List getTriangles() {
818	return triCoords;
819	}
820	}
821
822	/**
823	* Gets the geometry for the edges in the subdivision as a {@link MultiLineString}
824	* containing 2-point lines.
825	*
826	* @param geomFact the GeometryFactory to use
827	* @return a MultiLineString
828	*/
829	public Geometry getEdges(GeometryFactory geomFact) {
830	List quadEdges = getPrimaryEdges(false);
831	LineString[] edges = new LineString[quadEdges.size()];
832	int i = 0;
833	for (Iterator it = quadEdges.iterator(); it.hasNext();) {
834	QuadEdge qe = (QuadEdge) it.next();
835	edges[i++] = geomFact.createLineString(new Coordinate[] {
836	qe.orig().getCoordinate(), qe.dest().getCoordinate() });
837	}
838	return geomFact.createMultiLineString(edges);
839	}
840
841	/**
842	* Gets the geometry for the triangles in a triangulated subdivision as a {@link GeometryCollection}
843	* of triangular {@link Polygon}s.
844	*
845	* @param geomFact the GeometryFactory to use
846	* @return a GeometryCollection of triangular Polygons
847	*/
848	public Geometry getTriangles(GeometryFactory geomFact) {
849	List triPtsList = getTriangleCoordinates(false);
850	Polygon[] tris = new Polygon[triPtsList.size()];
851	int i = 0;
852	for (Iterator it = triPtsList.iterator(); it.hasNext();) {
853	Coordinate[] triPt = (Coordinate[]) it.next();
854	tris[i++] = geomFact
855	.createPolygon(geomFact.createLinearRing(triPt));
856	}
857	return geomFact.createGeometryCollection(tris);
858	}
859
860	/**
861	* Gets the cells in the Voronoi diagram for this triangulation.
862	* The cells are returned as a {@link GeometryCollection} of {@link Polygon}s
863	* <p>
864	* The userData of each polygon is set to be the {@link Coordinate}
865	* of the cell site. This allows easily associating external
866	* data associated with the sites to the cells.
867	*
868	* @param geomFact a geometry factory
869	* @return a GeometryCollection of Polygons
870	*/
871	public Geometry getVoronoiDiagram(GeometryFactory geomFact)
872	{
873	List vorCells = getVoronoiCellPolygons(geomFact);
874	return geomFact.createGeometryCollection(GeometryFactory.toGeometryArray(vorCells));
875	}
876
877	/**
878	* Gets a List of {@link Polygon}s for the Voronoi cells
879	* of this triangulation.
880	* <p>
881	* The userData of each polygon is set to be the {@link Coordinate}
882	* of the cell site. This allows easily associating external
883	* data associated with the sites to the cells.
884	*
885	* @param geomFact a geometry factory
886	* @return a List of Polygons
887	*/
888	public List getVoronoiCellPolygons(GeometryFactory geomFact)
889	{
890	/*
891	* Compute circumcentres of triangles as vertices for dual edges.
892	* Precomputing the circumcentres is more efficient,
893	* and more importantly ensures that the computed centres
894	* are consistent across the Voronoi cells.
895	*/
896	visitTriangles(new TriangleCircumcentreVisitor(), true);
897
898	List cells = new ArrayList();
899	Collection edges = getVertexUniqueEdges(false);
900	for (Iterator i = edges.iterator(); i.hasNext(); ) {
901	QuadEdge qe = (QuadEdge) i.next();
902	cells.add(getVoronoiCellPolygon(qe, geomFact));
903	}
904	return cells;
905	}
906
907	/**
908	* Gets the Voronoi cell around a site specified
909	* by the origin of a QuadEdge.
910	* <p>
911	* The userData of the polygon is set to be the {@link Coordinate}
912	* of the site. This allows attaching external
913	* data associated with the site to this cell polygon.
914	*
915	* @param qe a quadedge originating at the cell site
916	* @param geomFact a factory for building the polygon
917	* @return a polygon indicating the cell extent
918	*/
919	public Polygon getVoronoiCellPolygon(QuadEdge qe, GeometryFactory geomFact)
920	{
921	List cellPts = new ArrayList();
922	QuadEdge startQE = qe;
923	do {
924	// Coordinate cc = circumcentre(qe);
925	// use previously computed circumcentre
926	Coordinate cc = qe.rot().orig().getCoordinate();
927	cellPts.add(cc);
928
929	// move to next triangle CW around vertex
930	qe = qe.oPrev();
931	} while (qe != startQE);
932
933	CoordinateList coordList = new CoordinateList();
934	coordList.addAll(cellPts, false);
935	coordList.closeRing();
936
937	if (coordList.size() < 4) {
938	System.out.println(coordList);
939	coordList.add(coordList.get(coordList.size()-1), true);
940	}
941
942	Coordinate[] pts = coordList.toCoordinateArray();
943	Polygon cellPoly = geomFact.createPolygon(geomFact.createLinearRing(pts));
944
945	Vertex v = startQE.orig();
946	cellPoly.setUserData(v.getCoordinate());
947	return cellPoly;
948	}
949
950	}
951