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.io.PrintStream;
037: import java.util.*;
038: import com.vividsolutions.jts.geom.*;
039: import com.vividsolutions.jts.algorithm.*;
040: import com.vividsolutions.jts.util.*;
041:
042: /**
043: * A EdgeEndStar is an ordered list of EdgeEnds around a node.
044: * They are maintained in CCW order (starting with the positive x-axis) around the node
045: * for efficient lookup and topology building.
046: *
047: * @version 1.7
048: */
049: abstract public class EdgeEndStar {
050:
051: /**
052: * A map which maintains the edges in sorted order around the node
053: */
054: protected Map edgeMap = new TreeMap();
055: /**
056: * A list of all outgoing edges in the result, in CCW order
057: */
058: protected List edgeList;
059: /**
060: * The location of the point for this star in Geometry i Areas
061: */
062: private int[] ptInAreaLocation = { Location.NONE, Location.NONE };
063:
064: public EdgeEndStar() {
065:
066: }
067:
068: /**
069: * Insert a EdgeEnd into this EdgeEndStar
070: */
071: abstract public void insert(EdgeEnd e);
072:
073: /**
074: * Insert an EdgeEnd into the map, and clear the edgeList cache,
075: * since the list of edges has now changed
076: */
077: protected void insertEdgeEnd(EdgeEnd e, Object obj) {
078: edgeMap.put(e, obj);
079: edgeList = null; // edge list has changed - clear the cache
080: }
081:
082: /**
083: * @return the coordinate for the node this star is based at
084: */
085: public Coordinate getCoordinate() {
086: Iterator it = iterator();
087: if (!it.hasNext())
088: return null;
089: EdgeEnd e = (EdgeEnd) it.next();
090: return e.getCoordinate();
091: }
092:
093: public int getDegree() {
094: return edgeMap.size();
095: }
096:
097: /**
098: * Iterator access to the ordered list of edges is optimized by
099: * copying the map collection to a list. (This assumes that
100: * once an iterator is requested, it is likely that insertion into
101: * the map is complete).
102: */
103: public Iterator iterator() {
104: return getEdges().iterator();
105: }
106:
107: public List getEdges() {
108: if (edgeList == null) {
109: edgeList = new ArrayList(edgeMap.values());
110: }
111: return edgeList;
112: }
113:
114: public EdgeEnd getNextCW(EdgeEnd ee) {
115: getEdges();
116: int i = edgeList.indexOf(ee);
117: int iNextCW = i - 1;
118: if (i == 0)
119: iNextCW = edgeList.size() - 1;
120: return (EdgeEnd) edgeList.get(iNextCW);
121: }
122:
123: public void computeLabelling(GeometryGraph[] geomGraph) {
124: computeEdgeEndLabels(geomGraph[0].getBoundaryNodeRule());
125: // Propagate side labels around the edges in the star
126: // for each parent Geometry
127: //Debug.print(this);
128: propagateSideLabels(0);
129: //Debug.print(this);
130: //Debug.printIfWatch(this);
131: propagateSideLabels(1);
132: //Debug.print(this);
133: //Debug.printIfWatch(this);
134:
135: /**
136: * If there are edges that still have null labels for a geometry
137: * this must be because there are no area edges for that geometry incident on this node.
138: * In this case, to label the edge for that geometry we must test whether the
139: * edge is in the interior of the geometry.
140: * To do this it suffices to determine whether the node for the edge is in the interior of an area.
141: * If so, the edge has location INTERIOR for the geometry.
142: * In all other cases (e.g. the node is on a line, on a point, or not on the geometry at all) the edge
143: * has the location EXTERIOR for the geometry.
144: * <p>
145: * Note that the edge cannot be on the BOUNDARY of the geometry, since then
146: * there would have been a parallel edge from the Geometry at this node also labelled BOUNDARY
147: * and this edge would have been labelled in the previous step.
148: * <p>
149: * This code causes a problem when dimensional collapses are present, since it may try and
150: * determine the location of a node where a dimensional collapse has occurred.
151: * The point should be considered to be on the EXTERIOR
152: * of the polygon, but locate() will return INTERIOR, since it is passed
153: * the original Geometry, not the collapsed version.
154: *
155: * If there are incident edges which are Line edges labelled BOUNDARY,
156: * then they must be edges resulting from dimensional collapses.
157: * In this case the other edges can be labelled EXTERIOR for this Geometry.
158: *
159: * MD 8/11/01 - NOT TRUE! The collapsed edges may in fact be in the interior of the Geometry,
160: * which means the other edges should be labelled INTERIOR for this Geometry.
161: * Not sure how solve this... Possibly labelling needs to be split into several phases:
162: * area label propagation, symLabel merging, then finally null label resolution.
163: */
164: boolean[] hasDimensionalCollapseEdge = { false, false };
165: for (Iterator it = iterator(); it.hasNext();) {
166: EdgeEnd e = (EdgeEnd) it.next();
167: Label label = e.getLabel();
168: for (int geomi = 0; geomi < 2; geomi++) {
169: if (label.isLine(geomi)
170: && label.getLocation(geomi) == Location.BOUNDARY)
171: hasDimensionalCollapseEdge[geomi] = true;
172: }
173: }
174: //Debug.print(this);
175: for (Iterator it = iterator(); it.hasNext();) {
176: EdgeEnd e = (EdgeEnd) it.next();
177: Label label = e.getLabel();
178: //Debug.println(e);
179: for (int geomi = 0; geomi < 2; geomi++) {
180: if (label.isAnyNull(geomi)) {
181: int loc = Location.NONE;
182: if (hasDimensionalCollapseEdge[geomi]) {
183: loc = Location.EXTERIOR;
184: } else {
185: Coordinate p = e.getCoordinate();
186: loc = getLocation(geomi, p, geomGraph);
187: }
188: label.setAllLocationsIfNull(geomi, loc);
189: }
190: }
191: //Debug.println(e);
192: }
193: //Debug.print(this);
194: //Debug.printIfWatch(this);
195: }
196:
197: private void computeEdgeEndLabels(BoundaryNodeRule boundaryNodeRule) {
198: // Compute edge label for each EdgeEnd
199: for (Iterator it = iterator(); it.hasNext();) {
200: EdgeEnd ee = (EdgeEnd) it.next();
201: ee.computeLabel(boundaryNodeRule);
202: }
203: }
204:
205: int getLocation(int geomIndex, Coordinate p, GeometryGraph[] geom) {
206: // compute location only on demand
207: if (ptInAreaLocation[geomIndex] == Location.NONE) {
208: ptInAreaLocation[geomIndex] = SimplePointInAreaLocator
209: .locate(p, geom[geomIndex].getGeometry());
210: }
211: return ptInAreaLocation[geomIndex];
212: }
213:
214: public boolean isAreaLabelsConsistent(GeometryGraph geomGraph) {
215: computeEdgeEndLabels(geomGraph.getBoundaryNodeRule());
216: return checkAreaLabelsConsistent(0);
217: }
218:
219: private boolean checkAreaLabelsConsistent(int geomIndex) {
220: // Since edges are stored in CCW order around the node,
221: // As we move around the ring we move from the right to the left side of the edge
222: List edges = getEdges();
223: // if no edges, trivially consistent
224: if (edges.size() <= 0)
225: return true;
226: // initialize startLoc to location of last L side (if any)
227: int lastEdgeIndex = edges.size() - 1;
228: Label startLabel = ((EdgeEnd) edges.get(lastEdgeIndex))
229: .getLabel();
230: int startLoc = startLabel.getLocation(geomIndex, Position.LEFT);
231: Assert.isTrue(startLoc != Location.NONE,
232: "Found unlabelled area edge");
233:
234: int currLoc = startLoc;
235: for (Iterator it = iterator(); it.hasNext();) {
236: EdgeEnd e = (EdgeEnd) it.next();
237: Label label = e.getLabel();
238: // we assume that we are only checking a area
239: Assert.isTrue(label.isArea(geomIndex),
240: "Found non-area edge");
241: int leftLoc = label.getLocation(geomIndex, Position.LEFT);
242: int rightLoc = label.getLocation(geomIndex, Position.RIGHT);
243: //System.out.println(leftLoc + " " + rightLoc);
244: //Debug.print(this);
245: // check that edge is really a boundary between inside and outside!
246: if (leftLoc == rightLoc) {
247: return false;
248: }
249: // check side location conflict
250: //Assert.isTrue(rightLoc == currLoc, "side location conflict " + locStr);
251: if (rightLoc != currLoc) {
252: //Debug.print(this);
253: return false;
254: }
255: currLoc = leftLoc;
256: }
257: return true;
258: }
259:
260: void propagateSideLabels(int geomIndex) {
261: // Since edges are stored in CCW order around the node,
262: // As we move around the ring we move from the right to the left side of the edge
263: int startLoc = Location.NONE;
264: // initialize loc to location of last L side (if any)
265: //System.out.println("finding start location");
266: for (Iterator it = iterator(); it.hasNext();) {
267: EdgeEnd e = (EdgeEnd) it.next();
268: Label label = e.getLabel();
269: if (label.isArea(geomIndex)
270: && label.getLocation(geomIndex, Position.LEFT) != Location.NONE)
271: startLoc = label.getLocation(geomIndex, Position.LEFT);
272: }
273: // no labelled sides found, so no labels to propagate
274: if (startLoc == Location.NONE)
275: return;
276:
277: int currLoc = startLoc;
278: for (Iterator it = iterator(); it.hasNext();) {
279: EdgeEnd e = (EdgeEnd) it.next();
280: Label label = e.getLabel();
281: // set null ON values to be in current location
282: if (label.getLocation(geomIndex, Position.ON) == Location.NONE)
283: label.setLocation(geomIndex, Position.ON, currLoc);
284: // set side labels (if any)
285: // if (label.isArea()) { //ORIGINAL
286: if (label.isArea(geomIndex)) {
287: int leftLoc = label.getLocation(geomIndex,
288: Position.LEFT);
289: int rightLoc = label.getLocation(geomIndex,
290: Position.RIGHT);
291: // if there is a right location, that is the next location to propagate
292: if (rightLoc != Location.NONE) {
293: //Debug.print(rightLoc != currLoc, this);
294: if (rightLoc != currLoc)
295: throw new TopologyException(
296: "side location conflict", e
297: .getCoordinate());
298: if (leftLoc == Location.NONE) {
299: Assert
300: .shouldNeverReachHere("found single null side (at "
301: + e.getCoordinate() + ")");
302: }
303: currLoc = leftLoc;
304: } else {
305: /** RHS is null - LHS must be null too.
306: * This must be an edge from the other geometry, which has no location
307: * labelling for this geometry. This edge must lie wholly inside or outside
308: * the other geometry (which is determined by the current location).
309: * Assign both sides to be the current location.
310: */
311: Assert.isTrue(label.getLocation(geomIndex,
312: Position.LEFT) == Location.NONE,
313: "found single null side");
314: label.setLocation(geomIndex, Position.RIGHT,
315: currLoc);
316: label
317: .setLocation(geomIndex, Position.LEFT,
318: currLoc);
319: }
320: }
321: }
322: }
323:
324: public int findIndex(EdgeEnd eSearch) {
325: iterator(); // force edgelist to be computed
326: for (int i = 0; i < edgeList.size(); i++) {
327: EdgeEnd e = (EdgeEnd) edgeList.get(i);
328: if (e == eSearch)
329: return i;
330: }
331: return -1;
332: }
333:
334: public void print(PrintStream out) {
335: System.out.println("EdgeEndStar: " + getCoordinate());
336: for (Iterator it = iterator(); it.hasNext();) {
337: EdgeEnd e = (EdgeEnd) it.next();
338: e.print(out);
339: }
340: }
341: }
|