Class EdgeGraph

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 java.util.Collection;
16	import java.util.HashMap;
17	import java.util.Map;
18
19	import org.locationtech.jts.geom.Coordinate;
20
21
22	/**
23	* A graph comprised of {@link HalfEdge}s.
24	* It supports tracking the vertices in the graph
25	* via edges incident on them,
26	* to allow efficient lookup of edges and vertices.
27	* <p>
28	* This class may be subclassed to use a
29	* different subclass of HalfEdge,
30	* by overriding {@link #createEdge(Coordinate)}.
31	* If additional logic is required to initialize
32	* edges then {@link EdgeGraph#addEdge(Coordinate, Coordinate)}
33	* can be overridden as well.
34	*
35	* @author Martin Davis
36	*
37	*/
38	public class EdgeGraph
39	{
40	private Map vertexMap = new HashMap();
41
42	public EdgeGraph() {
43	}
44
45	/**
46	* Creates a single HalfEdge.
47	* Override to use a different HalfEdge subclass.
48	*
49	* @param orig the origin location
50	* @return a new HalfEdge with the given origin
51	*/
52	protected HalfEdge createEdge(Coordinate orig)
53	{
54	return new HalfEdge(orig);
55	}
56
57	private HalfEdge create(Coordinate p0, Coordinate p1)
58	{
59	HalfEdge e0 = createEdge(p0);
60	HalfEdge e1 = createEdge(p1);
61	e0.link(e1);
62	return e0;
63	}
64
65	/**
66	* Adds an edge between the coordinates orig and dest
67	* to this graph.
68	* Only valid edges can be added (in particular, zero-length segments cannot be added)
69	*
70	* @param orig the edge origin location
71	* @param dest the edge destination location.
72	* @return the created edge
73	* @return null if the edge was invalid and not added
74	*
75	* @see #isValidEdge(Coordinate, Coordinate)
76	*/
77	public HalfEdge addEdge(Coordinate orig, Coordinate dest) {
78	if (! isValidEdge(orig, dest)) return null;
79
80	/**
81	* Attempt to find the edge already in the graph.
82	* Return it if found.
83	* Otherwise, use a found edge with same origin (if any) to construct new edge.
84	*/
85	HalfEdge eAdj = (HalfEdge) vertexMap.get(orig);
86	HalfEdge eSame = null;
87	if (eAdj != null) {
88	eSame = eAdj.find(dest);
89	}
90	if (eSame != null) {
91	return eSame;
92	}
93
94	HalfEdge e = insert(orig, dest, eAdj);
95	return e;
96	}
97
98	/**
99	* Tests if the given coordinates form a valid edge (with non-zero length).
100	*
101	* @param orig the start coordinate
102	* @param dest the end coordinate
103	* @return true if the edge formed is valid
104	*/
105	public static boolean isValidEdge(Coordinate orig, Coordinate dest) {
106	int cmp = dest.compareTo(orig);
107	return cmp != 0;
108	}
109
110	/**
111	* Inserts an edge not already present into the graph.
112	*
113	* @param orig the edge origin location
114	* @param dest the edge destination location
115	* @param eAdj an existing edge with same orig (if any)
116	* @return the created edge
117	*/
118	private HalfEdge insert(Coordinate orig, Coordinate dest, HalfEdge eAdj) {
119	// edge does not exist, so create it and insert in graph
120	HalfEdge e = create(orig, dest);
121	if (eAdj != null) {
122	eAdj.insert(e);
123	}
124	else {
125	// add halfedges to to map
126	vertexMap.put(orig, e);
127	}
128
129	HalfEdge eAdjDest = (HalfEdge) vertexMap.get(dest);
130	if (eAdjDest != null) {
131	eAdjDest.insert(e.sym());
132	}
133	else {
134	vertexMap.put(dest, e.sym());
135	}
136	return e;
137	}
138
139	public Collection getVertexEdges()
140	{
141	return vertexMap.values();
142	}
143
144	/**
145	* Finds an edge in this graph with the given origin
146	* and destination, if one exists.
147	*
148	* @param orig the origin location
149	* @param dest the destination location.
150	* @return an edge with the given orig and dest, or null if none exists
151	*/
152	public HalfEdge findEdge(Coordinate orig, Coordinate dest) {
153	HalfEdge e = (HalfEdge) vertexMap.get(orig);
154	if (e == null) return null;
155	return e.find(dest);
156	}
157	}
158