Class EdgeRing

1
2
3
4	/*
5	* Copyright (c) 2016 Vivid Solutions.
6	*
7	* All rights reserved. This program and the accompanying materials
8	* are made available under the terms of the Eclipse Public License 2.0
9	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
10	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
11	* and the Eclipse Distribution License is available at
12	*
13	* http://www.eclipse.org/org/documents/edl-v10.php.
14	*/
15	package org.locationtech.jts.geomgraph;
16
17	import java.util.ArrayList;
18	import java.util.Iterator;
19	import java.util.List;
20
21	import org.locationtech.jts.algorithm.Orientation;
22	import org.locationtech.jts.algorithm.PointLocation;
23	import org.locationtech.jts.geom.Coordinate;
24	import org.locationtech.jts.geom.Envelope;
25	import org.locationtech.jts.geom.GeometryFactory;
26	import org.locationtech.jts.geom.LinearRing;
27	import org.locationtech.jts.geom.Location;
28	import org.locationtech.jts.geom.Polygon;
29	import org.locationtech.jts.geom.TopologyException;
30	import org.locationtech.jts.util.Assert;
31
32
33
34	/**
35	* @version 1.7
36	*/
37	public abstract class EdgeRing {
38
39	protected DirectedEdge startDe; // the directed edge which starts the list of edges for this EdgeRing
40	private int maxNodeDegree = -1;
41	private List edges = new ArrayList(); // the DirectedEdges making up this EdgeRing
42	private List pts = new ArrayList();
43	private Label label = new Label(Location.NONE); // label stores the locations of each geometry on the face surrounded by this ring
44	private LinearRing ring; // the ring created for this EdgeRing
45	private boolean isHole;
46	private EdgeRing shell; // if non-null, the ring is a hole and this EdgeRing is its containing shell
47	private ArrayList holes = new ArrayList(); // a list of EdgeRings which are holes in this EdgeRing
48
49	protected GeometryFactory geometryFactory;
50
51	public EdgeRing(DirectedEdge start, GeometryFactory geometryFactory) {
52	this.geometryFactory = geometryFactory;
53	computePoints(start);
54	computeRing();
55	}
56
57	public boolean isIsolated()
58	{
59	return (label.getGeometryCount() == 1);
60	}
61	public boolean isHole()
62	{
63	//computePoints();
64	return isHole;
65	}
66
67	public Coordinate getCoordinate(int i) { return (Coordinate) pts.get(i); }
68	public LinearRing getLinearRing() { return ring; }
69	public Label getLabel() { return label; }
70	public boolean isShell() { return shell == null; }
71	public EdgeRing getShell() { return shell; }
72	public void setShell(EdgeRing shell)
73	{
74	this.shell = shell;
75	if (shell != null) shell.addHole(this);
76	}
77	public void addHole(EdgeRing ring) { holes.add(ring); }
78
79	public Polygon toPolygon(GeometryFactory geometryFactory)
80	{
81	LinearRing[] holeLR = new LinearRing[holes.size()];
82	for (int i = 0; i < holes.size(); i++) {
83	holeLR[i] = ((EdgeRing) holes.get(i)).getLinearRing();
84	}
85	Polygon poly = geometryFactory.createPolygon(getLinearRing(), holeLR);
86	return poly;
87	}
88	/**
89	* Compute a LinearRing from the point list previously collected.
90	* Test if the ring is a hole (i.e. if it is CCW) and set the hole flag
91	* accordingly.
92	*/
93	public void computeRing()
94	{
95	if (ring != null) return; // don't compute more than once
96	Coordinate[] coord = new Coordinate[pts.size()];
97	for (int i = 0; i < pts.size(); i++) {
98	coord[i] = (Coordinate) pts.get(i);
99	}
100	ring = geometryFactory.createLinearRing(coord);
101	isHole = Orientation.isCCW(ring.getCoordinates());
102	//Debug.println( (isHole ? "hole - " : "shell - ") + WKTWriter.toLineString(new CoordinateArraySequence(ring.getCoordinates())));
103	}
104	abstract public DirectedEdge getNext(DirectedEdge de);
105	abstract public void setEdgeRing(DirectedEdge de, EdgeRing er);
106
107	/**
108	* Returns the list of DirectedEdges that make up this EdgeRing
109	*/
110	public List getEdges() { return edges; }
111
112	/**
113	* Collect all the points from the DirectedEdges of this ring into a contiguous list
114	*/
115	protected void computePoints(DirectedEdge start)
116	{
117	//System.out.println("buildRing");
118	startDe = start;
119	DirectedEdge de = start;
120	boolean isFirstEdge = true;
121	do {
122	// Assert.isTrue(de != null, "found null Directed Edge");
123	if (de == null)
124	throw new TopologyException("Found null DirectedEdge");
125	if (de.getEdgeRing() == this)
126	throw new TopologyException("Directed Edge visited twice during ring-building at " + de.getCoordinate());
127
128	edges.add(de);
129	//Debug.println(de);
130	//Debug.println(de.getEdge());
131	Label label = de.getLabel();
132	Assert.isTrue(label.isArea());
133	mergeLabel(label);
134	addPoints(de.getEdge(), de.isForward(), isFirstEdge);
135	isFirstEdge = false;
136	setEdgeRing(de, this);
137	de = getNext(de);
138	} while (de != startDe);
139	}
140
141	public int getMaxNodeDegree()
142	{
143	if (maxNodeDegree < 0) computeMaxNodeDegree();
144	return maxNodeDegree;
145	}
146
147	private void computeMaxNodeDegree()
148	{
149	maxNodeDegree = 0;
150	DirectedEdge de = startDe;
151	do {
152	Node node = de.getNode();
153	int degree = ((DirectedEdgeStar) node.getEdges()).getOutgoingDegree(this);
154	if (degree > maxNodeDegree) maxNodeDegree = degree;
155	de = getNext(de);
156	} while (de != startDe);
157	maxNodeDegree *= 2;
158	}
159
160
161	public void setInResult()
162	{
163	DirectedEdge de = startDe;
164	do {
165	de.getEdge().setInResult(true);
166	de = de.getNext();
167	} while (de != startDe);
168	}
169
170	protected void mergeLabel(Label deLabel)
171	{
172	mergeLabel(deLabel, 0);
173	mergeLabel(deLabel, 1);
174	}
175	/**
176	* Merge the RHS label from a DirectedEdge into the label for this EdgeRing.
177	* The DirectedEdge label may be null. This is acceptable - it results
178	* from a node which is NOT an intersection node between the Geometries
179	* (e.g. the end node of a LinearRing). In this case the DirectedEdge label
180	* does not contribute any information to the overall labelling, and is simply skipped.
181	*/
182	protected void mergeLabel(Label deLabel, int geomIndex)
183	{
184	int loc = deLabel.getLocation(geomIndex, Position.RIGHT);
185	// no information to be had from this label
186	if (loc == Location.NONE) return;
187	// if there is no current RHS value, set it
188	if (label.getLocation(geomIndex) == Location.NONE) {
189	label.setLocation(geomIndex, loc);
190	return;
191	}
192	}
193	protected void addPoints(Edge edge, boolean isForward, boolean isFirstEdge)
194	{
195	Coordinate[] edgePts = edge.getCoordinates();
196	if (isForward) {
197	int startIndex = 1;
198	if (isFirstEdge) startIndex = 0;
199	for (int i = startIndex; i < edgePts.length; i++) {
200	pts.add(edgePts[i]);
201	}
202	}
203	else { // is backward
204	int startIndex = edgePts.length - 2;
205	if (isFirstEdge) startIndex = edgePts.length - 1;
206	for (int i = startIndex; i >= 0; i--) {
207	pts.add(edgePts[i]);
208	}
209	}
210	}
211
212	/**
213	* This method will cause the ring to be computed.
214	* It will also check any holes, if they have been assigned.
215	*/
216	public boolean containsPoint(Coordinate p)
217	{
218	LinearRing shell = getLinearRing();
219	Envelope env = shell.getEnvelopeInternal();
220	if (! env.contains(p)) return false;
221	if (! PointLocation.isInRing(p, shell.getCoordinates()) ) return false;
222
223	for (Iterator i = holes.iterator(); i.hasNext(); ) {
224	EdgeRing hole = (EdgeRing) i.next();
225	if (hole.containsPoint(p) )
226	return false;
227	}
228	return true;
229	}
230
231	}
232