Class RelateNodeGraph

1
2	/*
3	* Copyright (c) 2016 Vivid Solutions.
4	*
5	* All rights reserved. This program and the accompanying materials
6	* are made available under the terms of the Eclipse Public License 2.0
7	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
8	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
9	* and the Eclipse Distribution License is available at
10	*
11	* http://www.eclipse.org/org/documents/edl-v10.php.
12	*/
13	package org.locationtech.jts.operation.relate;
14
15	/**
16	* @version 1.7
17	*/
18	import java.util.Iterator;
19	import java.util.List;
20
21	import org.locationtech.jts.geom.Location;
22	import org.locationtech.jts.geomgraph.Edge;
23	import org.locationtech.jts.geomgraph.EdgeEnd;
24	import org.locationtech.jts.geomgraph.EdgeIntersection;
25	import org.locationtech.jts.geomgraph.GeometryGraph;
26	import org.locationtech.jts.geomgraph.Node;
27	import org.locationtech.jts.geomgraph.NodeMap;
28
29	/**
30	* Implements the simple graph of Nodes and EdgeEnd which is all that is
31	* required to determine topological relationships between Geometries.
32	* Also supports building a topological graph of a single Geometry, to
33	* allow verification of valid topology.
34	* <p>
35	* It is <b>not</b> necessary to create a fully linked
36	* PlanarGraph to determine relationships, since it is sufficient
37	* to know how the Geometries interact locally around the nodes.
38	* In fact, this is not even feasible, since it is not possible to compute
39	* exact intersection points, and hence the topology around those nodes
40	* cannot be computed robustly.
41	* The only Nodes that are created are for improper intersections;
42	* that is, nodes which occur at existing vertices of the Geometries.
43	* Proper intersections (e.g. ones which occur between the interior of line segments)
44	* have their topology determined implicitly, without creating a Node object
45	* to represent them.
46	*
47	* @version 1.7
48	*/
49	public class RelateNodeGraph {
50
51	private NodeMap nodes = new NodeMap(new RelateNodeFactory());
52
53	public RelateNodeGraph() {
54	}
55
56	public Iterator getNodeIterator() { return nodes.iterator(); }
57
58	public void build(GeometryGraph geomGraph)
59	{
60	// compute nodes for intersections between previously noded edges
61	computeIntersectionNodes(geomGraph, 0);
62	/**
63	* Copy the labelling for the nodes in the parent Geometry. These override
64	* any labels determined by intersections.
65	*/
66	copyNodesAndLabels(geomGraph, 0);
67
68	/**
69	* Build EdgeEnds for all intersections.
70	*/
71	EdgeEndBuilder eeBuilder = new EdgeEndBuilder();
72	List eeList = eeBuilder.computeEdgeEnds(geomGraph.getEdgeIterator());
73	insertEdgeEnds(eeList);
74
75	//Debug.println("==== NodeList ===");
76	//Debug.print(nodes);
77	}
78
79	/**
80	* Insert nodes for all intersections on the edges of a Geometry.
81	* Label the created nodes the same as the edge label if they do not already have a label.
82	* This allows nodes created by either self-intersections or
83	* mutual intersections to be labelled.
84	* Endpoint nodes will already be labelled from when they were inserted.
85	* <p>
86	* Precondition: edge intersections have been computed.
87	*/
88	public void computeIntersectionNodes(GeometryGraph geomGraph, int argIndex)
89	{
90	for (Iterator edgeIt = geomGraph.getEdgeIterator(); edgeIt.hasNext(); ) {
91	Edge e = (Edge) edgeIt.next();
92	int eLoc = e.getLabel().getLocation(argIndex);
93	for (Iterator eiIt = e.getEdgeIntersectionList().iterator(); eiIt.hasNext(); ) {
94	EdgeIntersection ei = (EdgeIntersection) eiIt.next();
95	RelateNode n = (RelateNode) nodes.addNode(ei.coord);
96	if (eLoc == Location.BOUNDARY)
97	n.setLabelBoundary(argIndex);
98	else {
99	if (n.getLabel().isNull(argIndex))
100	n.setLabel(argIndex, Location.INTERIOR);
101	}
102	//Debug.println(n);
103	}
104	}
105	}
106
107	/**
108	* Copy all nodes from an arg geometry into this graph.
109	* The node label in the arg geometry overrides any previously computed
110	* label for that argIndex.
111	* (E.g. a node may be an intersection node with
112	* a computed label of BOUNDARY,
113	* but in the original arg Geometry it is actually
114	* in the interior due to the Boundary Determination Rule)
115	*/
116	public void copyNodesAndLabels(GeometryGraph geomGraph, int argIndex)
117	{
118	for (Iterator nodeIt = geomGraph.getNodeIterator(); nodeIt.hasNext(); ) {
119	Node graphNode = (Node) nodeIt.next();
120	Node newNode = nodes.addNode(graphNode.getCoordinate());
121	newNode.setLabel(argIndex, graphNode.getLabel().getLocation(argIndex));
122	//node.print(System.out);
123	}
124	}
125
126	public void insertEdgeEnds(List ee)
127	{
128	for (Iterator i = ee.iterator(); i.hasNext(); ) {
129	EdgeEnd e = (EdgeEnd) i.next();
130	nodes.add(e);
131	}
132	}
133
134
135	}
136