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.util.*;
040:
041: /**
042: * A DirectedEdgeStar is an ordered list of <b>outgoing</b> DirectedEdges around a node.
043: * It supports labelling the edges as well as linking the edges to form both
044: * MaximalEdgeRings and MinimalEdgeRings.
045: *
046: * @version 1.7
047: */
048: public class DirectedEdgeStar extends EdgeEndStar {
049:
050: /**
051: * A list of all outgoing edges in the result, in CCW order
052: */
053: private List resultAreaEdgeList;
054: private Label label;
055:
056: public DirectedEdgeStar() {
057: }
058:
059: /**
060: * Insert a directed edge in the list
061: */
062: public void insert(EdgeEnd ee) {
063: DirectedEdge de = (DirectedEdge) ee;
064: insertEdgeEnd(de, de);
065: }
066:
067: public Label getLabel() {
068: return label;
069: }
070:
071: public int getOutgoingDegree() {
072: int degree = 0;
073: for (Iterator it = iterator(); it.hasNext();) {
074: DirectedEdge de = (DirectedEdge) it.next();
075: if (de.isInResult())
076: degree++;
077: }
078: return degree;
079: }
080:
081: public int getOutgoingDegree(EdgeRing er) {
082: int degree = 0;
083: for (Iterator it = iterator(); it.hasNext();) {
084: DirectedEdge de = (DirectedEdge) it.next();
085: if (de.getEdgeRing() == er)
086: degree++;
087: }
088: return degree;
089: }
090:
091: public DirectedEdge getRightmostEdge() {
092: List edges = getEdges();
093: int size = edges.size();
094: if (size < 1)
095: return null;
096: DirectedEdge de0 = (DirectedEdge) edges.get(0);
097: if (size == 1)
098: return de0;
099: DirectedEdge deLast = (DirectedEdge) edges.get(size - 1);
100:
101: int quad0 = de0.getQuadrant();
102: int quad1 = deLast.getQuadrant();
103: if (Quadrant.isNorthern(quad0) && Quadrant.isNorthern(quad1))
104: return de0;
105: else if (!Quadrant.isNorthern(quad0)
106: && !Quadrant.isNorthern(quad1))
107: return deLast;
108: else {
109: // edges are in different hemispheres - make sure we return one that is non-horizontal
110: //Assert.isTrue(de0.getDy() != 0, "should never return horizontal edge!");
111: DirectedEdge nonHorizontalEdge = null;
112: if (de0.getDy() != 0)
113: return de0;
114: else if (deLast.getDy() != 0)
115: return deLast;
116: }
117: Assert
118: .shouldNeverReachHere("found two horizontal edges incident on node");
119: return null;
120:
121: }
122:
123: /**
124: * Compute the labelling for all dirEdges in this star, as well
125: * as the overall labelling
126: */
127: public void computeLabelling(GeometryGraph[] geom) {
128: //Debug.print(this);
129: super .computeLabelling(geom);
130:
131: // determine the overall labelling for this DirectedEdgeStar
132: // (i.e. for the node it is based at)
133: label = new Label(Location.NONE);
134: for (Iterator it = iterator(); it.hasNext();) {
135: EdgeEnd ee = (EdgeEnd) it.next();
136: Edge e = ee.getEdge();
137: Label eLabel = e.getLabel();
138: for (int i = 0; i < 2; i++) {
139: int eLoc = eLabel.getLocation(i);
140: if (eLoc == Location.INTERIOR
141: || eLoc == Location.BOUNDARY)
142: label.setLocation(i, Location.INTERIOR);
143: }
144: }
145: //Debug.print(this);
146: }
147:
148: /**
149: * For each dirEdge in the star,
150: * merge the label from the sym dirEdge into the label
151: */
152: public void mergeSymLabels() {
153: for (Iterator it = iterator(); it.hasNext();) {
154: DirectedEdge de = (DirectedEdge) it.next();
155: Label label = de.getLabel();
156: label.merge(de.getSym().getLabel());
157: }
158: }
159:
160: /**
161: * Update incomplete dirEdge labels from the labelling for the node
162: */
163: public void updateLabelling(Label nodeLabel) {
164: for (Iterator it = iterator(); it.hasNext();) {
165: DirectedEdge de = (DirectedEdge) it.next();
166: Label label = de.getLabel();
167: label.setAllLocationsIfNull(0, nodeLabel.getLocation(0));
168: label.setAllLocationsIfNull(1, nodeLabel.getLocation(1));
169: }
170: }
171:
172: private List getResultAreaEdges() {
173: //print(System.out);
174: if (resultAreaEdgeList != null)
175: return resultAreaEdgeList;
176: resultAreaEdgeList = new ArrayList();
177: for (Iterator it = iterator(); it.hasNext();) {
178: DirectedEdge de = (DirectedEdge) it.next();
179: if (de.isInResult() || de.getSym().isInResult())
180: resultAreaEdgeList.add(de);
181: }
182: return resultAreaEdgeList;
183: }
184:
185: private final int SCANNING_FOR_INCOMING = 1;
186: private final int LINKING_TO_OUTGOING = 2;
187:
188: /**
189: * Traverse the star of DirectedEdges, linking the included edges together.
190: * To link two dirEdges, the <next> pointer for an incoming dirEdge
191: * is set to the next outgoing edge.
192: * <p>
193: * DirEdges are only linked if:
194: * <ul>
195: * <li>they belong to an area (i.e. they have sides)
196: * <li>they are marked as being in the result
197: * </ul>
198: * <p>
199: * Edges are linked in CCW order (the order they are stored).
200: * This means that rings have their face on the Right
201: * (in other words,
202: * the topological location of the face is given by the RHS label of the DirectedEdge)
203: * <p>
204: * PRECONDITION: No pair of dirEdges are both marked as being in the result
205: */
206: public void linkResultDirectedEdges() {
207: // make sure edges are copied to resultAreaEdges list
208: getResultAreaEdges();
209: // find first area edge (if any) to start linking at
210: DirectedEdge firstOut = null;
211: DirectedEdge incoming = null;
212: int state = SCANNING_FOR_INCOMING;
213: // link edges in CCW order
214: for (int i = 0; i < resultAreaEdgeList.size(); i++) {
215: DirectedEdge nextOut = (DirectedEdge) resultAreaEdgeList
216: .get(i);
217: DirectedEdge nextIn = nextOut.getSym();
218:
219: // skip de's that we're not interested in
220: if (!nextOut.getLabel().isArea())
221: continue;
222:
223: // record first outgoing edge, in order to link the last incoming edge
224: if (firstOut == null && nextOut.isInResult())
225: firstOut = nextOut;
226: // assert: sym.isInResult() == false, since pairs of dirEdges should have been removed already
227:
228: switch (state) {
229: case SCANNING_FOR_INCOMING:
230: if (!nextIn.isInResult())
231: continue;
232: incoming = nextIn;
233: state = LINKING_TO_OUTGOING;
234: break;
235: case LINKING_TO_OUTGOING:
236: if (!nextOut.isInResult())
237: continue;
238: incoming.setNext(nextOut);
239: state = SCANNING_FOR_INCOMING;
240: break;
241: }
242: }
243: //Debug.print(this);
244: if (state == LINKING_TO_OUTGOING) {
245: //Debug.print(firstOut == null, this);
246: if (firstOut == null)
247: throw new TopologyException(
248: "no outgoing dirEdge found", getCoordinate());
249: //Assert.isTrue(firstOut != null, "no outgoing dirEdge found (at " + getCoordinate() );
250: Assert.isTrue(firstOut.isInResult(),
251: "unable to link last incoming dirEdge");
252: incoming.setNext(firstOut);
253: }
254: }
255:
256: public void linkMinimalDirectedEdges(EdgeRing er) {
257: // find first area edge (if any) to start linking at
258: DirectedEdge firstOut = null;
259: DirectedEdge incoming = null;
260: int state = SCANNING_FOR_INCOMING;
261: // link edges in CW order
262: for (int i = resultAreaEdgeList.size() - 1; i >= 0; i--) {
263: DirectedEdge nextOut = (DirectedEdge) resultAreaEdgeList
264: .get(i);
265: DirectedEdge nextIn = nextOut.getSym();
266:
267: // record first outgoing edge, in order to link the last incoming edge
268: if (firstOut == null && nextOut.getEdgeRing() == er)
269: firstOut = nextOut;
270:
271: switch (state) {
272: case SCANNING_FOR_INCOMING:
273: if (nextIn.getEdgeRing() != er)
274: continue;
275: incoming = nextIn;
276: state = LINKING_TO_OUTGOING;
277: break;
278: case LINKING_TO_OUTGOING:
279: if (nextOut.getEdgeRing() != er)
280: continue;
281: incoming.setNextMin(nextOut);
282: state = SCANNING_FOR_INCOMING;
283: break;
284: }
285: }
286: //print(System.out);
287: if (state == LINKING_TO_OUTGOING) {
288: Assert.isTrue(firstOut != null,
289: "found null for first outgoing dirEdge");
290: Assert.isTrue(firstOut.getEdgeRing() == er,
291: "unable to link last incoming dirEdge");
292: incoming.setNextMin(firstOut);
293: }
294: }
295:
296: public void linkAllDirectedEdges() {
297: getEdges();
298: // find first area edge (if any) to start linking at
299: DirectedEdge prevOut = null;
300: DirectedEdge firstIn = null;
301: // link edges in CW order
302: for (int i = edgeList.size() - 1; i >= 0; i--) {
303: DirectedEdge nextOut = (DirectedEdge) edgeList.get(i);
304: DirectedEdge nextIn = nextOut.getSym();
305: if (firstIn == null)
306: firstIn = nextIn;
307: if (prevOut != null)
308: nextIn.setNext(prevOut);
309: // record outgoing edge, in order to link the last incoming edge
310: prevOut = nextOut;
311: }
312: firstIn.setNext(prevOut);
313: //Debug.print(this);
314: }
315:
316: /**
317: * Traverse the star of edges, maintaing the current location in the result
318: * area at this node (if any).
319: * If any L edges are found in the interior of the result, mark them as covered.
320: */
321: public void findCoveredLineEdges() {
322: //Debug.print("findCoveredLineEdges");
323: //Debug.print(this);
324: // Since edges are stored in CCW order around the node,
325: // as we move around the ring we move from the right to the left side of the edge
326:
327: /**
328: * Find first DirectedEdge of result area (if any).
329: * The interior of the result is on the RHS of the edge,
330: * so the start location will be:
331: * - INTERIOR if the edge is outgoing
332: * - EXTERIOR if the edge is incoming
333: */
334: int startLoc = Location.NONE;
335: for (Iterator it = iterator(); it.hasNext();) {
336: DirectedEdge nextOut = (DirectedEdge) it.next();
337: DirectedEdge nextIn = nextOut.getSym();
338: if (!nextOut.isLineEdge()) {
339: if (nextOut.isInResult()) {
340: startLoc = Location.INTERIOR;
341: break;
342: }
343: if (nextIn.isInResult()) {
344: startLoc = Location.EXTERIOR;
345: break;
346: }
347: }
348: }
349: // no A edges found, so can't determine if L edges are covered or not
350: if (startLoc == Location.NONE)
351: return;
352:
353: /**
354: * move around ring, keeping track of the current location
355: * (Interior or Exterior) for the result area.
356: * If L edges are found, mark them as covered if they are in the interior
357: */
358: int currLoc = startLoc;
359: for (Iterator it = iterator(); it.hasNext();) {
360: DirectedEdge nextOut = (DirectedEdge) it.next();
361: DirectedEdge nextIn = nextOut.getSym();
362: if (nextOut.isLineEdge()) {
363: nextOut.getEdge().setCovered(
364: currLoc == Location.INTERIOR);
365: //Debug.println(nextOut);
366: } else { // edge is an Area edge
367: if (nextOut.isInResult())
368: currLoc = Location.EXTERIOR;
369: if (nextIn.isInResult())
370: currLoc = Location.INTERIOR;
371: }
372: }
373: }
374:
375: public void computeDepths(DirectedEdge de) {
376: int edgeIndex = findIndex(de);
377: Label label = de.getLabel();
378: int startDepth = de.getDepth(Position.LEFT);
379: int targetLastDepth = de.getDepth(Position.RIGHT);
380: // compute the depths from this edge up to the end of the edge array
381: int nextDepth = computeDepths(edgeIndex + 1, edgeList.size(),
382: startDepth);
383: // compute the depths for the initial part of the array
384: int lastDepth = computeDepths(0, edgeIndex, nextDepth);
385: //Debug.print(lastDepth != targetLastDepth, this);
386: //Debug.print(lastDepth != targetLastDepth, "mismatch: " + lastDepth + " / " + targetLastDepth);
387: if (lastDepth != targetLastDepth)
388: throw new TopologyException("depth mismatch at "
389: + de.getCoordinate());
390: //Assert.isTrue(lastDepth == targetLastDepth, "depth mismatch at " + de.getCoordinate());
391: }
392:
393: /**
394: * Compute the DirectedEdge depths for a subsequence of the edge array.
395: *
396: * @return the last depth assigned (from the R side of the last edge visited)
397: */
398: private int computeDepths(int startIndex, int endIndex,
399: int startDepth) {
400: int currDepth = startDepth;
401: for (int i = startIndex; i < endIndex; i++) {
402: DirectedEdge nextDe = (DirectedEdge) edgeList.get(i);
403: Label label = nextDe.getLabel();
404: nextDe.setEdgeDepths(Position.RIGHT, currDepth);
405: currDepth = nextDe.getDepth(Position.LEFT);
406: }
407: return currDepth;
408: }
409:
410: public void print(PrintStream out) {
411: System.out.println("DirectedEdgeStar: " + getCoordinate());
412: for (Iterator it = iterator(); it.hasNext();) {
413: DirectedEdge de = (DirectedEdge) it.next();
414: out.print("out ");
415: de.print(out);
416: out.println();
417: out.print("in ");
418: de.getSym().print(out);
419: out.println();
420: }
421: }
422: }
|