001:
002: /*
003: * The JTS Topology Suite is a collection of Java classes that
004: * implement the fundamental operations required to validate a given
005: * geo-spatial data set to a known topological specification.
006: *
007: * Copyright (C) 2001 Vivid Solutions
008: *
009: * This library is free software; you can redistribute it and/or
010: * modify it under the terms of the GNU Lesser General Public
011: * License as published by the Free Software Foundation; either
012: * version 2.1 of the License, or (at your option) any later version.
013: *
014: * This library is distributed in the hope that it will be useful,
015: * but WITHOUT ANY WARRANTY; without even the implied warranty of
016: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
017: * Lesser General Public License for more details.
018: *
019: * You should have received a copy of the GNU Lesser General Public
020: * License along with this library; if not, write to the Free Software
021: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
022: *
023: * For more information, contact:
024: *
025: * Vivid Solutions
026: * Suite #1A
027: * 2328 Government Street
028: * Victoria BC V8T 5G5
029: * Canada
030: *
031: * (250)385-6040
032: * www.vividsolutions.com
033: */
034: package com.vividsolutions.jts.geomgraph;
035:
036: import java.util.ArrayList;
037: import java.util.Iterator;
038: import java.util.List;
039:
040: import com.vividsolutions.jts.algorithm.CGAlgorithms;
041: import com.vividsolutions.jts.geom.*;
042: import com.vividsolutions.jts.geom.impl.*;
043: import com.vividsolutions.jts.io.*;
044: import com.vividsolutions.jts.util.*;
045:
046: /**
047: * @version 1.7
048: */
049: public abstract class EdgeRing {
050:
051: protected DirectedEdge startDe; // the directed edge which starts the list of edges for this EdgeRing
052: private int maxNodeDegree = -1;
053: private List edges = new ArrayList(); // the DirectedEdges making up this EdgeRing
054: private List pts = new ArrayList();
055: private Label label = new Label(Location.NONE); // label stores the locations of each geometry on the face surrounded by this ring
056: private LinearRing ring; // the ring created for this EdgeRing
057: private boolean isHole;
058: private EdgeRing shell; // if non-null, the ring is a hole and this EdgeRing is its containing shell
059: private ArrayList holes = new ArrayList(); // a list of EdgeRings which are holes in this EdgeRing
060:
061: protected GeometryFactory geometryFactory;
062: protected CGAlgorithms cga;
063:
064: public EdgeRing(DirectedEdge start,
065: GeometryFactory geometryFactory, CGAlgorithms cga) {
066: this .geometryFactory = geometryFactory;
067: this .cga = cga;
068: computePoints(start);
069: computeRing();
070: }
071:
072: public boolean isIsolated() {
073: return (label.getGeometryCount() == 1);
074: }
075:
076: public boolean isHole() {
077: //computePoints();
078: return isHole;
079: }
080:
081: public Coordinate getCoordinate(int i) {
082: return (Coordinate) pts.get(i);
083: }
084:
085: public LinearRing getLinearRing() {
086: return ring;
087: }
088:
089: public Label getLabel() {
090: return label;
091: }
092:
093: public boolean isShell() {
094: return shell == null;
095: }
096:
097: public EdgeRing getShell() {
098: return shell;
099: }
100:
101: public void setShell(EdgeRing shell) {
102: this .shell = shell;
103: if (shell != null)
104: shell.addHole(this );
105: }
106:
107: public void addHole(EdgeRing ring) {
108: holes.add(ring);
109: }
110:
111: public Polygon toPolygon(GeometryFactory geometryFactory) {
112: LinearRing[] holeLR = new LinearRing[holes.size()];
113: for (int i = 0; i < holes.size(); i++) {
114: holeLR[i] = ((EdgeRing) holes.get(i)).getLinearRing();
115: }
116: Polygon poly = geometryFactory.createPolygon(getLinearRing(),
117: holeLR);
118: return poly;
119: }
120:
121: /**
122: * Compute a LinearRing from the point list previously collected.
123: * Test if the ring is a hole (i.e. if it is CCW) and set the hole flag
124: * accordingly.
125: */
126: public void computeRing() {
127: if (ring != null)
128: return; // don't compute more than once
129: Coordinate[] coord = new Coordinate[pts.size()];
130: for (int i = 0; i < pts.size(); i++) {
131: coord[i] = (Coordinate) pts.get(i);
132: }
133: ring = geometryFactory.createLinearRing(coord);
134: isHole = cga.isCCW(ring.getCoordinates());
135: //Debug.println( (isHole ? "hole - " : "shell - ") + WKTWriter.toLineString(new CoordinateArraySequence(ring.getCoordinates())));
136: }
137:
138: abstract public DirectedEdge getNext(DirectedEdge de);
139:
140: abstract public void setEdgeRing(DirectedEdge de, EdgeRing er);
141:
142: /**
143: * Returns the list of DirectedEdges that make up this EdgeRing
144: */
145: public List getEdges() {
146: return edges;
147: }
148:
149: /**
150: * Collect all the points from the DirectedEdges of this ring into a contiguous list
151: */
152: protected void computePoints(DirectedEdge start) {
153: //System.out.println("buildRing");
154: startDe = start;
155: DirectedEdge de = start;
156: boolean isFirstEdge = true;
157: do {
158: // Assert.isTrue(de != null, "found null Directed Edge");
159: if (de == null)
160: throw new TopologyException("Found null DirectedEdge");
161: if (de.getEdgeRing() == this )
162: throw new TopologyException(
163: "Directed Edge visited twice during ring-building at "
164: + de.getCoordinate());
165:
166: edges.add(de);
167: //Debug.println(de);
168: //Debug.println(de.getEdge());
169: Label label = de.getLabel();
170: Assert.isTrue(label.isArea());
171: mergeLabel(label);
172: addPoints(de.getEdge(), de.isForward(), isFirstEdge);
173: isFirstEdge = false;
174: setEdgeRing(de, this );
175: de = getNext(de);
176: } while (de != startDe);
177: }
178:
179: public int getMaxNodeDegree() {
180: if (maxNodeDegree < 0)
181: computeMaxNodeDegree();
182: return maxNodeDegree;
183: }
184:
185: private void computeMaxNodeDegree() {
186: maxNodeDegree = 0;
187: DirectedEdge de = startDe;
188: do {
189: Node node = de.getNode();
190: int degree = ((DirectedEdgeStar) node.getEdges())
191: .getOutgoingDegree(this );
192: if (degree > maxNodeDegree)
193: maxNodeDegree = degree;
194: de = getNext(de);
195: } while (de != startDe);
196: maxNodeDegree *= 2;
197: }
198:
199: public void setInResult() {
200: DirectedEdge de = startDe;
201: do {
202: de.getEdge().setInResult(true);
203: de = de.getNext();
204: } while (de != startDe);
205: }
206:
207: protected void mergeLabel(Label deLabel) {
208: mergeLabel(deLabel, 0);
209: mergeLabel(deLabel, 1);
210: }
211:
212: /**
213: * Merge the RHS label from a DirectedEdge into the label for this EdgeRing.
214: * The DirectedEdge label may be null. This is acceptable - it results
215: * from a node which is NOT an intersection node between the Geometries
216: * (e.g. the end node of a LinearRing). In this case the DirectedEdge label
217: * does not contribute any information to the overall labelling, and is simply skipped.
218: */
219: protected void mergeLabel(Label deLabel, int geomIndex) {
220: int loc = deLabel.getLocation(geomIndex, Position.RIGHT);
221: // no information to be had from this label
222: if (loc == Location.NONE)
223: return;
224: // if there is no current RHS value, set it
225: if (label.getLocation(geomIndex) == Location.NONE) {
226: label.setLocation(geomIndex, loc);
227: return;
228: }
229: }
230:
231: protected void addPoints(Edge edge, boolean isForward,
232: boolean isFirstEdge) {
233: Coordinate[] edgePts = edge.getCoordinates();
234: if (isForward) {
235: int startIndex = 1;
236: if (isFirstEdge)
237: startIndex = 0;
238: for (int i = startIndex; i < edgePts.length; i++) {
239: pts.add(edgePts[i]);
240: }
241: } else { // is backward
242: int startIndex = edgePts.length - 2;
243: if (isFirstEdge)
244: startIndex = edgePts.length - 1;
245: for (int i = startIndex; i >= 0; i--) {
246: pts.add(edgePts[i]);
247: }
248: }
249: }
250:
251: /**
252: * This method will cause the ring to be computed.
253: * It will also check any holes, if they have been assigned.
254: */
255: public boolean containsPoint(Coordinate p) {
256: LinearRing shell = getLinearRing();
257: Envelope env = shell.getEnvelopeInternal();
258: if (!env.contains(p))
259: return false;
260: if (!cga.isPointInRing(p, shell.getCoordinates()))
261: return false;
262:
263: for (Iterator i = holes.iterator(); i.hasNext();) {
264: EdgeRing hole = (EdgeRing) i.next();
265: if (hole.containsPoint(p))
266: return false;
267: }
268: return true;
269: }
270:
271: }
|