Class QuadEdge

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 org.locationtech.jts.geom.Coordinate;
16	import org.locationtech.jts.geom.LineSegment;
17	import org.locationtech.jts.io.WKTWriter;
18
19	/**
20	* A class that represents the edge data structure which implements the quadedge algebra.
21	* The quadedge algebra was described in a well-known paper by Guibas and Stolfi,
22	* "Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams",
23	* <i>ACM Transactions on Graphics</i>, 4(2), 1985, 75-123.
24	* <p>
25	* Each edge object is part of a quartet of 4 edges,
26	* linked via their <tt>rot</tt> references.
27	* Any edge in the group may be accessed using a series of {@link #rot()} operations.
28	* Quadedges in a subdivision are linked together via their <tt>next</tt> references.
29	* The linkage between the quadedge quartets determines the topology
30	* of the subdivision.
31	* <p>
32	* The edge class does not contain separate information for vertices or faces; a vertex is implicitly
33	* defined as a ring of edges (created using the <tt>next</tt> field).
34	*
35	* @author David Skea
36	* @author Martin Davis
37	*/
38	public class QuadEdge
39	{
40	/**
41	* Creates a new QuadEdge quartet from {@link Vertex} o to {@link Vertex} d.
42	*
43	* @param o
44	* the origin Vertex
45	* @param d
46	* the destination Vertex
47	* @return the new QuadEdge quartet
48	*/
49	public static QuadEdge makeEdge(Vertex o, Vertex d) {
50	QuadEdge q0 = new QuadEdge();
51	QuadEdge q1 = new QuadEdge();
52	QuadEdge q2 = new QuadEdge();
53	QuadEdge q3 = new QuadEdge();
54
55	q0.rot = q1;
56	q1.rot = q2;
57	q2.rot = q3;
58	q3.rot = q0;
59
60	q0.setNext(q0);
61	q1.setNext(q3);
62	q2.setNext(q2);
63	q3.setNext(q1);
64
65	QuadEdge base = q0;
66	base.setOrig(o);
67	base.setDest(d);
68	return base;
69	}
70
71	/**
72	* Creates a new QuadEdge connecting the destination of a to the origin of
73	* b, in such a way that all three have the same left face after the
74	* connection is complete. Additionally, the data pointers of the new edge
75	* are set.
76	*
77	* @return the connected edge.
78	*/
79	public static QuadEdge connect(QuadEdge a, QuadEdge b) {
80	QuadEdge e = makeEdge(a.dest(), b.orig());
81	splice(e, a.lNext());
82	splice(e.sym(), b);
83	return e;
84	}
85
86	/**
87	* Splices two edges together or apart.
88	* Splice affects the two edge rings around the origins of a and b, and, independently, the two
89	* edge rings around the left faces of <tt>a</tt> and <tt>b</tt>.
90	* In each case, (i) if the two rings are distinct,
91	* Splice will combine them into one, or (ii) if the two are the same ring, Splice will break it
92	* into two separate pieces. Thus, Splice can be used both to attach the two edges together, and
93	* to break them apart.
94	*
95	* @param a an edge to splice
96	* @param b an edge to splice
97	*
98	*/
99	public static void splice(QuadEdge a, QuadEdge b) {
100	QuadEdge alpha = a.oNext().rot();
101	QuadEdge beta = b.oNext().rot();
102
103	QuadEdge t1 = b.oNext();
104	QuadEdge t2 = a.oNext();
105	QuadEdge t3 = beta.oNext();
106	QuadEdge t4 = alpha.oNext();
107
108	a.setNext(t1);
109	b.setNext(t2);
110	alpha.setNext(t3);
111	beta.setNext(t4);
112	}
113
114	/**
115	* Turns an edge counterclockwise inside its enclosing quadrilateral.
116	*
117	* @param e the quadedge to turn
118	*/
119	public static void swap(QuadEdge e) {
120	QuadEdge a = e.oPrev();
121	QuadEdge b = e.sym().oPrev();
122	splice(e, a);
123	splice(e.sym(), b);
124	splice(e, a.lNext());
125	splice(e.sym(), b.lNext());
126	e.setOrig(a.dest());
127	e.setDest(b.dest());
128	}
129
130	// the dual of this edge, directed from right to left
131	private QuadEdge rot;
132	private Vertex vertex; // The vertex that this edge represents
133	private QuadEdge next; // A reference to a connected edge
134	private Object data = null;
135	// private int visitedKey = 0;
136
137	/**
138	* Quadedges must be made using {@link makeEdge},
139	* to ensure proper construction.
140	*/
141	private QuadEdge()
142	{
143
144	}
145
146	/**
147	* Gets the primary edge of this quadedge and its <tt>sym</tt>.
148	* The primary edge is the one for which the origin
149	* and destination coordinates are ordered
150	* according to the standard {@link Coordinate} ordering
151	*
152	* @return the primary quadedge
153	*/
154	public QuadEdge getPrimary()
155	{
156	if (orig().getCoordinate().compareTo(dest().getCoordinate()) <= 0)
157	return this;
158	else
159	return sym();
160	}
161
162	/**
163	* Sets the external data value for this edge.
164	*
165	* @param data an object containing external data
166	*/
167	public void setData(Object data) {
168	this.data = data;
169	}
170
171	/**
172	* Gets the external data value for this edge.
173	*
174	* @return the data object
175	*/
176	public Object getData() {
177	return data;
178	}
179
180	/**
181	* Marks this quadedge as being deleted.
182	* This does not free the memory used by
183	* this quadedge quartet, but indicates
184	* that this edge no longer participates
185	* in a subdivision.
186	*
187	*/
188	public void delete() {
189	rot = null;
190	}
191
192	/**
193	* Tests whether this edge has been deleted.
194	*
195	* @return true if this edge has not been deleted.
196	*/
197	public boolean isLive() {
198	return rot != null;
199	}
200
201
202	/**
203	* Sets the connected edge
204	*
205	* @param next edge
206	*/
207	public void setNext(QuadEdge next) {
208	this.next = next;
209	}
210
211	/***************************************************************************
212	* QuadEdge Algebra
213	***************************************************************************
214	*/
215
216	/**
217	* Gets the dual of this edge, directed from its right to its left.
218	*
219	* @return the rotated edge
220	*/
221	public final QuadEdge rot() {
222	return rot;
223	}
224
225	/**
226	* Gets the dual of this edge, directed from its left to its right.
227	*
228	* @return the inverse rotated edge.
229	*/
230	public final QuadEdge invRot() {
231	return rot.sym();
232	}
233
234	/**
235	* Gets the edge from the destination to the origin of this edge.
236	*
237	* @return the sym of the edge
238	*/
239	public final QuadEdge sym() {
240	return rot.rot;
241	}
242
243	/**
244	* Gets the next CCW edge around the origin of this edge.
245	*
246	* @return the next linked edge.
247	*/
248	public final QuadEdge oNext() {
249	return next;
250	}
251
252	/**
253	* Gets the next CW edge around (from) the origin of this edge.
254	*
255	* @return the previous edge.
256	*/
257	public final QuadEdge oPrev() {
258	return rot.next.rot;
259	}
260
261	/**
262	* Gets the next CCW edge around (into) the destination of this edge.
263	*
264	* @return the next destination edge.
265	*/
266	public final QuadEdge dNext() {
267	return this.sym().oNext().sym();
268	}
269
270	/**
271	* Gets the next CW edge around (into) the destination of this edge.
272	*
273	* @return the previous destination edge.
274	*/
275	public final QuadEdge dPrev() {
276	return this.invRot().oNext().invRot();
277	}
278
279	/**
280	* Gets the CCW edge around the left face following this edge.
281	*
282	* @return the next left face edge.
283	*/
284	public final QuadEdge lNext() {
285	return this.invRot().oNext().rot();
286	}
287
288	/**
289	* Gets the CCW edge around the left face before this edge.
290	*
291	* @return the previous left face edge.
292	*/
293	public final QuadEdge lPrev() {
294	return next.sym();
295	}
296
297	/**
298	* Gets the edge around the right face ccw following this edge.
299	*
300	* @return the next right face edge.
301	*/
302	public final QuadEdge rNext() {
303	return rot.next.invRot();
304	}
305
306	/**
307	* Gets the edge around the right face ccw before this edge.
308	*
309	* @return the previous right face edge.
310	*/
311	public final QuadEdge rPrev() {
312	return this.sym().oNext();
313	}
314
315	/***********************************************************************************************
316	* Data Access
317	**********************************************************************************************/
318	/**
319	* Sets the vertex for this edge's origin
320	*
321	* @param o the origin vertex
322	*/
323	void setOrig(Vertex o) {
324	vertex = o;
325	}
326
327	/**
328	* Sets the vertex for this edge's destination
329	*
330	* @param d the destination vertex
331	*/
332	void setDest(Vertex d) {
333	sym().setOrig(d);
334	}
335
336	/**
337	* Gets the vertex for the edge's origin
338	*
339	* @return the origin vertex
340	*/
341	public final Vertex orig() {
342	return vertex;
343	}
344
345	/**
346	* Gets the vertex for the edge's destination
347	*
348	* @return the destination vertex
349	*/
350	public final Vertex dest() {
351	return sym().orig();
352	}
353
354	/**
355	* Gets the length of the geometry of this quadedge.
356	*
357	* @return the length of the quadedge
358	*/
359	public double getLength() {
360	return orig().getCoordinate().distance(dest().getCoordinate());
361	}
362
363	/**
364	* Tests if this quadedge and another have the same line segment geometry,
365	* regardless of orientation.
366	*
367	* @param qe a quadedge
368	* @return true if the quadedges are based on the same line segment regardless of orientation
369	*/
370	public boolean equalsNonOriented(QuadEdge qe) {
371	if (equalsOriented(qe))
372	return true;
373	if (equalsOriented(qe.sym()))
374	return true;
375	return false;
376	}
377
378	/**
379	* Tests if this quadedge and another have the same line segment geometry
380	* with the same orientation.
381	*
382	* @param qe a quadedge
383	* @return true if the quadedges are based on the same line segment
384	*/
385	public boolean equalsOriented(QuadEdge qe) {
386	if (orig().getCoordinate().equals2D(qe.orig().getCoordinate())
387	&& dest().getCoordinate().equals2D(qe.dest().getCoordinate()))
388	return true;
389	return false;
390	}
391
392	/**
393	* Creates a {@link LineSegment} representing the
394	* geometry of this edge.
395	*
396	* @return a LineSegment
397	*/
398	public LineSegment toLineSegment()
399	{
400	return new LineSegment(vertex.getCoordinate(), dest().getCoordinate());
401	}
402
403	/**
404	* Converts this edge to a WKT two-point <tt>LINESTRING</tt> indicating
405	* the geometry of this edge.
406	*
407	* @return a String representing this edge's geometry
408	*/
409	public String toString() {
410	Coordinate p0 = vertex.getCoordinate();
411	Coordinate p1 = dest().getCoordinate();
412	return WKTWriter.toLineString(p0, p1);
413	}
414	}
415