001: /*
002: * The JTS Topology Suite is a collection of Java classes that
003: * implement the fundamental operations required to validate a given
004: * geo-spatial data set to a known topological specification.
005: *
006: * Copyright (C) 2001 Vivid Solutions
007: *
008: * This library is free software; you can redistribute it and/or
009: * modify it under the terms of the GNU Lesser General Public
010: * License as published by the Free Software Foundation; either
011: * version 2.1 of the License, or (at your option) any later version.
012: *
013: * This library is distributed in the hope that it will be useful,
014: * but WITHOUT ANY WARRANTY; without even the implied warranty of
015: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
016: * Lesser General Public License for more details.
017: *
018: * You should have received a copy of the GNU Lesser General Public
019: * License along with this library; if not, write to the Free Software
020: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
021: *
022: * For more information, contact:
023: *
024: * Vivid Solutions
025: * Suite #1A
026: * 2328 Government Street
027: * Victoria BC V8T 5G5
028: * Canada
029: *
030: * (250)385-6040
031: * www.vividsolutions.com
032: */
033: package com.vividsolutions.jts.operation.buffer;
034:
035: import java.util.*;
036: import com.vividsolutions.jts.geom.*;
037: import com.vividsolutions.jts.geomgraph.*;
038: import com.vividsolutions.jts.algorithm.*;
039:
040: /**
041: * Locates a subgraph inside a set of subgraphs,
042: * in order to determine the outside depth of the subgraph.
043: * The input subgraphs are assumed to have had depths
044: * already calculated for their edges.
045: *
046: * @version 1.7
047: */
048: public class SubgraphDepthLocater {
049: private Collection subgraphs;
050: private LineSegment seg = new LineSegment();
051: private CGAlgorithms cga = new RobustCGAlgorithms();
052:
053: public SubgraphDepthLocater(List subgraphs) {
054: this .subgraphs = subgraphs;
055: }
056:
057: public int getDepth(Coordinate p) {
058: List stabbedSegments = findStabbedSegments(p);
059: // if no segments on stabbing line subgraph must be outside all others.
060: if (stabbedSegments.size() == 0)
061: return 0;
062: Collections.sort(stabbedSegments);
063: DepthSegment ds = (DepthSegment) stabbedSegments.get(0);
064: return ds.leftDepth;
065: }
066:
067: /**
068: * Finds all non-horizontal segments intersecting the stabbing line.
069: * The stabbing line is the ray to the right of stabbingRayLeftPt.
070: *
071: * @param stabbingRayLeftPt the left-hand origin of the stabbing line
072: * @return a List of {@link DepthSegments} intersecting the stabbing line
073: */
074: private List findStabbedSegments(Coordinate stabbingRayLeftPt) {
075: List stabbedSegments = new ArrayList();
076: for (Iterator i = subgraphs.iterator(); i.hasNext();) {
077: BufferSubgraph bsg = (BufferSubgraph) i.next();
078:
079: // optimization - don't bother checking subgraphs which the ray does not intersect
080: Envelope env = bsg.getEnvelope();
081: if (stabbingRayLeftPt.y < env.getMinY()
082: || stabbingRayLeftPt.y > env.getMaxY())
083: continue;
084:
085: findStabbedSegments(stabbingRayLeftPt, bsg
086: .getDirectedEdges(), stabbedSegments);
087: }
088: return stabbedSegments;
089: }
090:
091: /**
092: * Finds all non-horizontal segments intersecting the stabbing line
093: * in the list of dirEdges.
094: * The stabbing line is the ray to the right of stabbingRayLeftPt.
095: *
096: * @param stabbingRayLeftPt the left-hand origin of the stabbing line
097: * @param stabbedSegments the current list of {@link DepthSegments} intersecting the stabbing line
098: */
099: private void findStabbedSegments(Coordinate stabbingRayLeftPt,
100: List dirEdges, List stabbedSegments) {
101: /**
102: * Check all forward DirectedEdges only. This is still general,
103: * because each Edge has a forward DirectedEdge.
104: */
105: for (Iterator i = dirEdges.iterator(); i.hasNext();) {
106: DirectedEdge de = (DirectedEdge) i.next();
107: if (!de.isForward())
108: continue;
109: findStabbedSegments(stabbingRayLeftPt, de, stabbedSegments);
110: }
111: }
112:
113: /**
114: * Finds all non-horizontal segments intersecting the stabbing line
115: * in the input dirEdge.
116: * The stabbing line is the ray to the right of stabbingRayLeftPt.
117: *
118: * @param stabbingRayLeftPt the left-hand origin of the stabbing line
119: * @param stabbedSegments the current list of {@link DepthSegments} intersecting the stabbing line
120: */
121: private void findStabbedSegments(Coordinate stabbingRayLeftPt,
122: DirectedEdge dirEdge, List stabbedSegments) {
123: Coordinate[] pts = dirEdge.getEdge().getCoordinates();
124: for (int i = 0; i < pts.length - 1; i++) {
125: seg.p0 = pts[i];
126: seg.p1 = pts[i + 1];
127: // ensure segment always points upwards
128: if (seg.p0.y > seg.p1.y)
129: seg.reverse();
130:
131: // skip segment if it is left of the stabbing line
132: double maxx = Math.max(seg.p0.x, seg.p1.x);
133: if (maxx < stabbingRayLeftPt.x)
134: continue;
135:
136: // skip horizontal segments (there will be a non-horizontal one carrying the same depth info
137: if (seg.isHorizontal())
138: continue;
139:
140: // skip if segment is above or below stabbing line
141: if (stabbingRayLeftPt.y < seg.p0.y
142: || stabbingRayLeftPt.y > seg.p1.y)
143: continue;
144:
145: // skip if stabbing ray is right of the segment
146: if (cga.computeOrientation(seg.p0, seg.p1,
147: stabbingRayLeftPt) == CGAlgorithms.RIGHT)
148: continue;
149:
150: // stabbing line cuts this segment, so record it
151: int depth = dirEdge.getDepth(Position.LEFT);
152: // if segment direction was flipped, use RHS depth instead
153: if (!seg.p0.equals(pts[i]))
154: depth = dirEdge.getDepth(Position.RIGHT);
155: DepthSegment ds = new DepthSegment(seg, depth);
156: stabbedSegments.add(ds);
157: }
158: }
159:
160: /**
161: * A segment from a directed edge which has been assigned a depth value
162: * for its sides.
163: */
164: private class DepthSegment implements Comparable {
165: private LineSegment upwardSeg;
166: private int leftDepth;
167:
168: public DepthSegment(LineSegment seg, int depth) {
169: // input seg is assumed to be normalized
170: upwardSeg = new LineSegment(seg);
171: //upwardSeg.normalize();
172: this .leftDepth = depth;
173: }
174:
175: /**
176: * Defines a comparision operation on DepthSegments
177: * which orders them left to right
178: *
179: * <pre>
180: * DS1 < DS2 if DS1.seg is left of DS2.seg
181: * DS1 > DS2 if DS1.seg is right of DS2.seg
182: * </pre>
183: *
184: * @param obj
185: * @return
186: */
187: public int compareTo(Object obj) {
188: DepthSegment other = (DepthSegment) obj;
189: /**
190: * try and compute a determinate orientation for the segments.
191: * Test returns 1 if other is left of this (i.e. this > other)
192: */
193: int orientIndex = upwardSeg
194: .orientationIndex(other.upwardSeg);
195:
196: /**
197: * If comparison between this and other is indeterminate,
198: * try the opposite call order.
199: * orientationIndex value is 1 if this is left of other,
200: * so have to flip sign to get proper comparison value of
201: * -1 if this is leftmost
202: */
203: if (orientIndex == 0)
204: orientIndex = -1
205: * other.upwardSeg.orientationIndex(upwardSeg);
206:
207: // if orientation is determinate, return it
208: if (orientIndex != 0)
209: return orientIndex;
210:
211: // otherwise, segs must be collinear - sort based on minimum X value
212: return compareX(this .upwardSeg, other.upwardSeg);
213: }
214:
215: /**
216: * Compare two collinear segments for left-most ordering.
217: * If segs are vertical, use vertical ordering for comparison.
218: * If segs are equal, return 0.
219: * Segments are assumed to be directed so that the second coordinate is >= to the first
220: * (e.g. up and to the right).
221: *
222: * @param seg0 a segment to compare
223: * @param seg1 a segment to compare
224: * @return
225: */
226: private int compareX(LineSegment seg0, LineSegment seg1) {
227: int compare0 = seg0.p0.compareTo(seg1.p0);
228: if (compare0 != 0)
229: return compare0;
230: return seg0.p1.compareTo(seg1.p1);
231:
232: }
233:
234: }
235: }
|