Class HalfEdge

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.edgegraph;
14
15	import org.locationtech.jts.algorithm.Orientation;
16	import org.locationtech.jts.geom.Coordinate;
17	import org.locationtech.jts.geomgraph.Quadrant;
18	import org.locationtech.jts.io.WKTWriter;
19	import org.locationtech.jts.util.Assert;
20
21	/**
22	* Represents a directed component of an edge in an {@link EdgeGraph}.
23	* HalfEdges link vertices whose locations are defined by {@link Coordinate}s.
24	* HalfEdges start at an <b>origin</b> vertex,
25	* and terminate at a <b>destination</b> vertex.
26	* HalfEdges always occur in symmetric pairs, with the {@link #sym()} method
27	* giving access to the oppositely-oriented component.
28	* HalfEdges and the methods on them form an edge algebra,
29	* which can be used to traverse and query the topology
30	* of the graph formed by the edges.
31	* <p>
32	* To support graphs where the edges are sequences of coordinates
33	* each edge may also have a direction point supplied.
34	* This is used to determine the ordering
35	* of the edges around the origin.
36	* HalfEdges with the same origin are ordered
37	* so that the ring of edges formed by them is oriented CCW.
38	* <p>
39	* By design HalfEdges carry minimal information
40	* about the actual usage of the graph they represent.
41	* They can be subclassed to carry more information if required.
42	* <p>
43	* HalfEdges form a complete and consistent data structure by themselves,
44	* but an {@link EdgeGraph} is useful to allow retrieving edges
45	* by vertex and edge location, as well as ensuring
46	* edges are created and linked appropriately.
47	*
48	* @author Martin Davis
49	*
50	*/
51	public class HalfEdge {
52
53	/**
54	* Creates a HalfEdge pair representing an edge
55	* between two vertices located at coordinates p0 and p1.
56	*
57	* @param p0 a vertex coordinate
58	* @param p1 a vertex coordinate
59	* @return the HalfEdge with origin at p0
60	*/
61	public static HalfEdge create(Coordinate p0, Coordinate p1) {
62	HalfEdge e0 = new HalfEdge(p0);
63	HalfEdge e1 = new HalfEdge(p1);
64	e0.link(e1);
65	return e0;
66	}
67
68	private Coordinate orig;
69	private HalfEdge sym;
70	private HalfEdge next;
71
72	/**
73	* Creates a half-edge originating from a given coordinate.
74	*
75	* @param orig the origin coordinate
76	*/
77	public HalfEdge(Coordinate orig) {
78	this.orig = orig;
79	}
80
81	/**
82	* Links this edge with its sym (opposite) edge.
83	* This must be done for each pair of edges created.
84	*
85	* @param e the sym edge to link.
86	*/
87	public void link(HalfEdge sym)
88	{
89	setSym(sym);
90	sym.setSym(this);
91	// set next ptrs for a single segment
92	setNext(sym);
93	sym.setNext(this);
94	}
95
96	/**
97	* Gets the origin coordinate of this edge.
98	*
99	* @return the origin coordinate
100	*/
101	public Coordinate orig() { return orig; }
102
103	/**
104	* Gets the destination coordinate of this edge.
105	*
106	* @return the destination coordinate
107	*/
108	public Coordinate dest() { return sym.orig; }
109
110	/**
111	* The X component of the direction vector.
112	*
113	* @return the X component of the direction vector
114	*/
115	double directionX() { return directionPt().getX() - orig.getX(); }
116
117	/**
118	* The Y component of the direction vector.
119	*
120	* @return the Y component of the direction vector
121	*/
122	double directionY() { return directionPt().getY() - orig.getY(); }
123
124	/**
125	* Gets the direction point of this edge.
126	* In the base case this is the dest coordinate
127	* of the edge.
128	* Subclasses may override to
129	* allow a HalfEdge to represent an edge with more than two coordinates.
130	*
131	* @return the direction point for the edge
132	*/
133	protected Coordinate directionPt() {
134	// default is to assume edges have only 2 vertices
135	// subclasses may override to provide an internal direction point
136	return dest();
137	}
138
139	/**
140	* Gets the symmetric pair edge of this edge.
141	*
142	* @return the symmetric pair edge
143	*/
144	public HalfEdge sym()
145	{
146	return sym;
147	}
148
149	/**
150	* Sets the symmetric (opposite) edge to this edge.
151	*
152	* @param e the sym edge to set
153	*/
154	private void setSym(HalfEdge e) {
155	sym = e;
156	}
157
158	/**
159	* Gets the next edge CCW around the
160	* destination vertex of this edge,
161	* with the dest vertex as its origin.
162	* If the vertex has degree 1 then this is the <b>sym</b> edge.
163	*
164	* @return the next edge
165	*/
166	public HalfEdge next()
167	{
168	return next;
169	}
170
171	/**
172	* Gets the edge previous to this one
173	* (with dest being the same as this orig).
174	*
175	* @return the previous edge to this one
176	*/
177	public HalfEdge prev() {
178	return sym.next().sym;
179	}
180
181	/**
182	* Gets the next edge CCW around the origin of this edge,
183	* with the same origin.
184	*
185	* @return the next edge around the origin
186	*/
187	public HalfEdge oNext() {
188	return sym.next;
189	}
190
191	/**
192	* Sets the next edge CCW around the destination vertex of this edge.
193	*
194	* @param e the next edge
195	*/
196	public void setNext(HalfEdge e)
197	{
198	next = e;
199	}
200
201	/**
202	* Finds the edge starting at the origin of this edge
203	* with the given dest vertex,
204	* if any.
205	*
206	* @param dest the dest vertex to search for
207	* @return the edge with the required dest vertex, if it exists,
208	* or null
209	*/
210	public HalfEdge find(Coordinate dest) {
211	HalfEdge oNext = this;
212	do {
213	if (oNext == null) return null;
214	if (oNext.dest().equals2D(dest))
215	return oNext;
216	oNext = oNext.oNext();
217	} while (oNext != this);
218	return null;
219	}
220
221	/**
222	* Tests whether this edge has the given orig and dest vertices.
223	*
224	* @param p0 the origin vertex to test
225	* @param p1 the destination vertex to test
226	* @return true if the vertices are equal to the ones of this edge
227	*/
228	public boolean equals(Coordinate p0, Coordinate p1) {
229	return orig.equals2D(p0) && sym.orig.equals(p1);
230	}
231
232	/**
233	* Inserts an edge
234	* into the ring of edges around the origin vertex of this edge,
235	* ensuring that the edges remain ordered CCW.
236	* The inserted edge must have the same origin as this edge.
237	*
238	* @param eAdd the edge to insert
239	*/
240	public void insert(HalfEdge eAdd) {
241	// If this is only edge at origin, insert it after this
242	if (oNext() == this) {
243	// set linkage so ring is correct
244	insertAfter(eAdd);
245	return;
246	}
247
248	// Scan edges
249	// until insertion point is found
250	HalfEdge ePrev = insertionEdge(eAdd);
251	ePrev.insertAfter(eAdd);
252	}
253
254	/**
255	* Finds the insertion edge for a edge
256	* being added to this origin,
257	* ensuring that the star of edges
258	* around the origin remains fully CCW.
259	*
260	* @param eAdd the edge being added
261	* @return the edge to insert after
262	*/
263	private HalfEdge insertionEdge(HalfEdge eAdd) {
264	HalfEdge ePrev = this;
265	do {
266	HalfEdge eNext = ePrev.oNext();
267	/**
268	* Case 1: General case,
269	* with eNext higher than ePrev.
270	*
271	* Insert edge here if it lies between ePrev and eNext.
272	*/
273	if (eNext.compareTo(ePrev) > 0
274	&& eAdd.compareTo(ePrev) >= 0
275	&& eAdd.compareTo(eNext) <= 0) {
276	return ePrev;
277	}
278	/**
279	* Case 2: Origin-crossing case,
280	* indicated by eNext <= ePrev.
281	*
282	* Insert edge here if it lies
283	* in the gap between ePrev and eNext across the origin.
284	*/
285	if (eNext.compareTo(ePrev) <= 0
286	&& (eAdd.compareTo(eNext) <= 0 \|\| eAdd.compareTo(ePrev) >= 0)) {
287	return ePrev;
288	}
289	ePrev = eNext;
290	} while (ePrev != this);
291	Assert.shouldNeverReachHere();
292	return null;
293	}
294
295	/**
296	* Insert an edge with the same origin after this one.
297	* Assumes that the inserted edge is in the correct
298	* position around the ring.
299	*
300	* @param e the edge to insert (with same origin)
301	*/
302	private void insertAfter(HalfEdge e) {
303	Assert.equals(orig, e.orig());
304	HalfEdge save = oNext();
305	sym.setNext(e);
306	e.sym().setNext(save);
307	}
308
309	/**
310	* Tests whether the edges around the origin
311	* are sorted correctly.
312	* Note that edges must be strictly increasing,
313	* which implies no two edges can have the same direction point.
314	*
315	* @return true if the origin edges are sorted correctly
316	*/
317	public boolean isEdgesSorted() {
318	// find lowest edge at origin
319	HalfEdge lowest = findLowest();
320	HalfEdge e = lowest;
321	// check that all edges are sorted
322	do {
323	HalfEdge eNext = e.oNext();
324	if (eNext == lowest) break;
325	boolean isSorted = eNext.compareTo(e) > 0;
326	if (! isSorted) {
327	//int comp = eNext.compareTo(e);
328	return false;
329	}
330	e = eNext;
331	} while (e != lowest);
332	return true;
333	}
334
335	/**
336	* Finds the lowest edge around the origin,
337	* using the standard edge ordering.
338	*
339	* @return the lowest edge around the origin
340	*/
341	private HalfEdge findLowest() {
342	HalfEdge lowest = this;
343	HalfEdge e = this.oNext();
344	do {
345	if (e.compareTo(lowest) < 0)
346	lowest = e;
347	e = e.oNext();
348	} while (e != this);
349	return lowest;
350	}
351
352	/**
353	* Compares edges which originate at the same vertex
354	* based on the angle they make at their origin vertex with the positive X-axis.
355	* This allows sorting edges around their origin vertex in CCW order.
356	*/
357	public int compareTo(Object obj)
358	{
359	HalfEdge e = (HalfEdge) obj;
360	int comp = compareAngularDirection(e);
361	return comp;
362	}
363
364	/**
365	* Implements the total order relation:
366	* <p>
367	* The angle of edge a is greater than the angle of edge b,
368	* where the angle of an edge is the angle made by
369	* the first segment of the edge with the positive x-axis
370	* <p>
371	* When applied to a list of edges originating at the same point,
372	* this produces a CCW ordering of the edges around the point.
373	* <p>
374	* Using the obvious algorithm of computing the angle is not robust,
375	* since the angle calculation is susceptible to roundoff error.
376	* A robust algorithm is:
377	* <ul>
378	* <li>First, compare the quadrants the edge vectors lie in.
379	* If the quadrants are different,
380	* it is trivial to determine which edge has a greater angle.
381	*
382	* <li>if the vectors lie in the same quadrant, the
383	* {@link Orientation#index(Coordinate, Coordinate, Coordinate)} function
384	* can be used to determine the relative orientation of the vectors.
385	* </ul>
386	*/
387	public int compareAngularDirection(HalfEdge e)
388	{
389	double dx = directionX();
390	double dy = directionY();
391	double dx2 = e.directionX();
392	double dy2 = e.directionY();
393
394	// same vector
395	if (dx == dx2 && dy == dy2)
396	return 0;
397
398	int quadrant = Quadrant.quadrant(dx, dy);
399	int quadrant2 = Quadrant.quadrant(dx2, dy2);
400
401	/**
402	* If the direction vectors are in different quadrants,
403	* that determines the ordering
404	*/
405	if (quadrant > quadrant2) return 1;
406	if (quadrant < quadrant2) return -1;
407
408	//--- vectors are in the same quadrant
409	// Check relative orientation of direction vectors
410	// this is > e if it is CCW of e
411	Coordinate dir1 = directionPt();
412	Coordinate dir2 = e.directionPt();
413	return Orientation.index(e.orig, dir2, dir1);
414	}
415
416	/**
417	* Computes a string representation of a HalfEdge.
418	*
419	* @return a string representation
420	*/
421	public String toString()
422	{
423	return "HE("+orig.x + " " + orig.y
424	+ ", "
425	+ sym.orig.x + " " + sym.orig.y
426	+ ")";
427	}
428
429	public String toStringNode() {
430	Coordinate orig = orig();
431	Coordinate dest = dest();
432	StringBuilder sb = new StringBuilder();
433	sb.append("Node( " + WKTWriter.format(orig) + " )" + "\n");
434	HalfEdge e = this;
435	do {
436	sb.append(" -> " + e);
437	sb.append("\n");
438	e = e.oNext();
439	} while (e != this);
440	return sb.toString();
441	}
442
443	private String toStringNodeEdge() {
444	return " -> (" + WKTWriter.format(dest());
445	}
446
447	/**
448	* Computes the degree of the origin vertex.
449	* The degree is the number of edges
450	* originating from the vertex.
451	*
452	* @return the degree of the origin vertex
453	*/
454	public int degree() {
455	int degree = 0;
456	HalfEdge e = this;
457	do {
458	degree++;
459	e = e.oNext();
460	} while (e != this);
461	return degree;
462	}
463
464	/**
465	* Finds the first node previous to this edge, if any.
466	* If no such node exists (i.e. the edge is part of a ring)
467	* then null is returned.
468	*
469	* @return an edge originating at the node prior to this edge, if any,
470	* or null if no node exists
471	*/
472	public HalfEdge prevNode() {
473	HalfEdge e = this;
474	while (e.degree() == 2) {
475	e = e.prev();
476	if (e == this)
477	return null;
478	}
479	return e;
480	}
481
482	}
483