Class PlanarGraph

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	package org.locationtech.jts.geomgraph;
13
14	/**
15	* @version 1.7
16	*/
17	import java.io.PrintStream;
18	import java.util.ArrayList;
19	import java.util.Collection;
20	import java.util.Iterator;
21	import java.util.List;
22
23	import org.locationtech.jts.algorithm.Orientation;
24	import org.locationtech.jts.geom.Coordinate;
25	import org.locationtech.jts.geom.Location;
26
27	/**
28	* The computation of the <code>IntersectionMatrix</code> relies on the use of a structure
29	* called a "topology graph". The topology graph contains nodes and edges
30	* corresponding to the nodes and line segments of a <code>Geometry</code>. Each
31	* node and edge in the graph is labeled with its topological location relative to
32	* the source geometry.
33	* <P>
34	* Note that there is no requirement that points of self-intersection be a vertex.
35	* Thus to obtain a correct topology graph, <code>Geometry</code>s must be
36	* self-noded before constructing their graphs.
37	* <P>
38	* Two fundamental operations are supported by topology graphs:
39	* <UL>
40	* <LI>Computing the intersections between all the edges and nodes of a single graph
41	* <LI>Computing the intersections between the edges and nodes of two different graphs
42	* </UL>
43	*
44	* @version 1.7
45	*/
46	public class PlanarGraph
47	{
48	/**
49	* For nodes in the Collection, link the DirectedEdges at the node that are in the result.
50	* This allows clients to link only a subset of nodes in the graph, for
51	* efficiency (because they know that only a subset is of interest).
52	*/
53	public static void linkResultDirectedEdges(Collection nodes)
54	{
55	for (Iterator nodeit = nodes.iterator(); nodeit.hasNext(); ) {
56	Node node = (Node) nodeit.next();
57	((DirectedEdgeStar) node.getEdges()).linkResultDirectedEdges();
58	}
59	}
60
61	protected List edges = new ArrayList();
62	protected NodeMap nodes;
63	protected List edgeEndList = new ArrayList();
64
65	public PlanarGraph(NodeFactory nodeFact) {
66	nodes = new NodeMap(nodeFact);
67	}
68
69	public PlanarGraph() {
70	nodes = new NodeMap(new NodeFactory());
71	}
72
73	public Iterator getEdgeIterator() { return edges.iterator(); }
74	public Collection getEdgeEnds() { return edgeEndList; }
75
76	public boolean isBoundaryNode(int geomIndex, Coordinate coord)
77	{
78	Node node = nodes.find(coord);
79	if (node == null) return false;
80	Label label = node.getLabel();
81	if (label != null && label.getLocation(geomIndex) == Location.BOUNDARY) return true;
82	return false;
83	}
84	protected void insertEdge(Edge e)
85	{
86	edges.add(e);
87	}
88	public void add(EdgeEnd e)
89	{
90	nodes.add(e);
91	edgeEndList.add(e);
92	}
93
94	public Iterator getNodeIterator() { return nodes.iterator(); }
95	public Collection getNodes() { return nodes.values(); }
96	public Node addNode(Node node) { return nodes.addNode(node); }
97	public Node addNode(Coordinate coord) { return nodes.addNode(coord); }
98	/**
99	* @return the node if found; null otherwise
100	*/
101	public Node find(Coordinate coord) { return nodes.find(coord); }
102
103	/**
104	* Add a set of edges to the graph. For each edge two DirectedEdges
105	* will be created. DirectedEdges are NOT linked by this method.
106	*/
107	public void addEdges(List edgesToAdd)
108	{
109	// create all the nodes for the edges
110	for (Iterator it = edgesToAdd.iterator(); it.hasNext(); ) {
111	Edge e = (Edge) it.next();
112	edges.add(e);
113
114	DirectedEdge de1 = new DirectedEdge(e, true);
115	DirectedEdge de2 = new DirectedEdge(e, false);
116	de1.setSym(de2);
117	de2.setSym(de1);
118
119	add(de1);
120	add(de2);
121	}
122	}
123
124	/**
125	* Link the DirectedEdges at the nodes of the graph.
126	* This allows clients to link only a subset of nodes in the graph, for
127	* efficiency (because they know that only a subset is of interest).
128	*/
129	public void linkResultDirectedEdges()
130	{
131	for (Iterator nodeit = nodes.iterator(); nodeit.hasNext(); ) {
132	Node node = (Node) nodeit.next();
133	((DirectedEdgeStar) node.getEdges()).linkResultDirectedEdges();
134	}
135	}
136	/**
137	* Link the DirectedEdges at the nodes of the graph.
138	* This allows clients to link only a subset of nodes in the graph, for
139	* efficiency (because they know that only a subset is of interest).
140	*/
141	public void linkAllDirectedEdges()
142	{
143	for (Iterator nodeit = nodes.iterator(); nodeit.hasNext(); ) {
144	Node node = (Node) nodeit.next();
145	((DirectedEdgeStar) node.getEdges()).linkAllDirectedEdges();
146	}
147	}
148	/**
149	* Returns the EdgeEnd which has edge e as its base edge
150	* (MD 18 Feb 2002 - this should return a pair of edges)
151	*
152	* @return the edge, if found
153	* <code>null</code> if the edge was not found
154	*/
155	public EdgeEnd findEdgeEnd(Edge e)
156	{
157	for (Iterator i = getEdgeEnds().iterator(); i.hasNext(); ) {
158	EdgeEnd ee = (EdgeEnd) i.next();
159	if (ee.getEdge() == e)
160	return ee;
161	}
162	return null;
163	}
164
165	/**
166	* Returns the edge whose first two coordinates are p0 and p1
167	*
168	* @return the edge, if found
169	* <code>null</code> if the edge was not found
170	*/
171	public Edge findEdge(Coordinate p0, Coordinate p1)
172	{
173	for (int i = 0; i < edges.size(); i++) {
174	Edge e = (Edge) edges.get(i);
175	Coordinate[] eCoord = e.getCoordinates();
176	if (p0.equals(eCoord[0]) && p1.equals(eCoord[1]) )
177	return e;
178	}
179	return null;
180	}
181	/**
182	* Returns the edge which starts at p0 and whose first segment is
183	* parallel to p1
184	*
185	* @return the edge, if found
186	* <code>null</code> if the edge was not found
187	*/
188	public Edge findEdgeInSameDirection(Coordinate p0, Coordinate p1)
189	{
190	for (int i = 0; i < edges.size(); i++) {
191	Edge e = (Edge) edges.get(i);
192
193	Coordinate[] eCoord = e.getCoordinates();
194	if (matchInSameDirection(p0, p1, eCoord[0], eCoord[1]) )
195	return e;
196
197	if (matchInSameDirection(p0, p1, eCoord[eCoord.length - 1], eCoord[eCoord.length - 2]) )
198	return e;
199	}
200	return null;
201	}
202
203	/**
204	* The coordinate pairs match if they define line segments lying in the same direction.
205	* E.g. the segments are parallel and in the same quadrant
206	* (as opposed to parallel and opposite!).
207	*/
208	private boolean matchInSameDirection(Coordinate p0, Coordinate p1, Coordinate ep0, Coordinate ep1)
209	{
210	if (! p0.equals(ep0))
211	return false;
212
213	if (Orientation.index(p0, p1, ep1) == Orientation.COLLINEAR
214	&& Quadrant.quadrant(p0, p1) == Quadrant.quadrant(ep0, ep1) )
215	return true;
216	return false;
217	}
218
219	public void printEdges(PrintStream out)
220	{
221	out.println("Edges:");
222	for (int i = 0; i < edges.size(); i++) {
223	out.println("edge " + i + ":");
224	Edge e = (Edge) edges.get(i);
225	e.print(out);
226	e.eiList.print(out);
227	}
228	}
229	void debugPrint(Object o)
230	{
231	System.out.print(o);
232	}
233	void debugPrintln(Object o)
234	{
235	System.out.println(o);
236	}
237
238	}
239