001: package com.vividsolutions.jts.operation.predicate;
002:
003: import java.util.*;
004: import com.vividsolutions.jts.geom.*;
005: import com.vividsolutions.jts.algorithm.*;
006: import com.vividsolutions.jts.geom.util.*;
007:
008: /**
009: * Optimized implementation of spatial predicate "intersects"
010: * for cases where the first {@link Geometry} is a rectangle.
011: * <p>
012: * As a further optimization,
013: * this class can be used directly to test many geometries against a single
014: * rectangle.
015: *
016: * @version 1.7
017: */
018: public class RectangleIntersects {
019:
020: /**
021: * Crossover size at which brute-force intersection scanning
022: * is slower than indexed intersection detection.
023: * Must be determined empirically. Should err on the
024: * safe side by making value smaller rather than larger.
025: */
026: public static final int MAXIMUM_SCAN_SEGMENT_COUNT = 200;
027:
028: public static boolean intersects(Polygon rectangle, Geometry b) {
029: RectangleIntersects rp = new RectangleIntersects(rectangle);
030: return rp.intersects(b);
031: }
032:
033: private Polygon rectangle;
034: private Envelope rectEnv;
035:
036: /**
037: * Create a new intersects computer for a rectangle.
038: *
039: * @param rectangle a rectangular geometry
040: */
041: public RectangleIntersects(Polygon rectangle) {
042: this .rectangle = rectangle;
043: rectEnv = rectangle.getEnvelopeInternal();
044: }
045:
046: public boolean intersects(Geometry geom) {
047: if (!rectEnv.intersects(geom.getEnvelopeInternal()))
048: return false;
049: // test envelope relationships
050: EnvelopeIntersectsVisitor visitor = new EnvelopeIntersectsVisitor(
051: rectEnv);
052: visitor.applyTo(geom);
053: if (visitor.intersects())
054: return true;
055:
056: // test if any rectangle corner is contained in the target
057: ContainsPointVisitor ecpVisitor = new ContainsPointVisitor(
058: rectangle);
059: ecpVisitor.applyTo(geom);
060: if (ecpVisitor.containsPoint())
061: return true;
062:
063: // test if any lines intersect
064: LineIntersectsVisitor liVisitor = new LineIntersectsVisitor(
065: rectangle);
066: liVisitor.applyTo(geom);
067: if (liVisitor.intersects())
068: return true;
069:
070: return false;
071: }
072: }
073:
074: /**
075: * Tests whether it can be concluded
076: * that a rectangle intersects a geometry,
077: * based on the locations of the envelope(s) of the geometry.
078: *
079: * @author Martin Davis
080: * @version 1.7
081: */
082: class EnvelopeIntersectsVisitor extends ShortCircuitedGeometryVisitor {
083: private Envelope rectEnv;
084: private boolean intersects = false;
085:
086: public EnvelopeIntersectsVisitor(Envelope rectEnv) {
087: this .rectEnv = rectEnv;
088: }
089:
090: /**
091: * Reports whether it can be concluded that an intersection occurs,
092: * or whether further testing is required.
093: *
094: * @return <code>true</code> if an intersection must occur
095: * <code>false</code> if no conclusion can be made
096: */
097: public boolean intersects() {
098: return intersects;
099: }
100:
101: protected void visit(Geometry element) {
102: Envelope elementEnv = element.getEnvelopeInternal();
103: // disjoint
104: if (!rectEnv.intersects(elementEnv)) {
105: return;
106: }
107: // fully contained - must intersect
108: if (rectEnv.contains(elementEnv)) {
109: intersects = true;
110: return;
111: }
112: /**
113: * Since the envelopes intersect and the test element is connected,
114: * if the test envelope is completely bisected by an edge of the rectangle
115: * the element and the rectangle must touch
116: * (This is basically an application of the Jordan Curve Theorem).
117: * The alternative situation is that
118: * the test envelope is "on a corner" of the rectangle envelope,
119: * i.e. is not completely bisected.
120: * In this case it is not possible to make a conclusion
121: * about the presence of an intersection.
122: */
123: if (elementEnv.getMinX() >= rectEnv.getMinX()
124: && elementEnv.getMaxX() <= rectEnv.getMaxX()) {
125: intersects = true;
126: return;
127: }
128: if (elementEnv.getMinY() >= rectEnv.getMinY()
129: && elementEnv.getMaxY() <= rectEnv.getMaxY()) {
130: intersects = true;
131: return;
132: }
133: }
134:
135: protected boolean isDone() {
136: return intersects == true;
137: }
138: }
139:
140: /**
141: * Tests whether it can be concluded
142: * that a geometry contains a corner point of a rectangle.
143: *
144: * @author Martin Davis
145: * @version 1.7
146: */
147: class ContainsPointVisitor extends ShortCircuitedGeometryVisitor {
148: private CoordinateSequence rectSeq;
149: private Envelope rectEnv;
150: private boolean containsPoint = false;
151:
152: public ContainsPointVisitor(Polygon rectangle) {
153: this .rectSeq = rectangle.getExteriorRing()
154: .getCoordinateSequence();
155: rectEnv = rectangle.getEnvelopeInternal();
156: }
157:
158: /**
159: * Reports whether it can be concluded that a corner
160: * point of the rectangle is contained in the geometry,
161: * or whether further testing is required.
162: *
163: * @return <code>true</code> if a corner point is contained
164: * <code>false</code> if no conclusion can be made
165: */
166: public boolean containsPoint() {
167: return containsPoint;
168: }
169:
170: protected void visit(Geometry geom) {
171: if (!(geom instanceof Polygon))
172: return;
173: Envelope elementEnv = geom.getEnvelopeInternal();
174: if (!rectEnv.intersects(elementEnv))
175: return;
176: // test each corner of rectangle for inclusion
177: Coordinate rectPt = new Coordinate();
178: for (int i = 0; i < 4; i++) {
179: rectSeq.getCoordinate(i, rectPt);
180: if (!elementEnv.contains(rectPt))
181: continue;
182: // check rect point in poly (rect is known not to touch polygon at this point)
183: if (SimplePointInAreaLocator.containsPointInPolygon(rectPt,
184: (Polygon) geom)) {
185: containsPoint = true;
186: return;
187: }
188: }
189: }
190:
191: protected boolean isDone() {
192: return containsPoint == true;
193: }
194: }
195:
196: /**
197: * Tests whether any line segment of a geometry intersects a given rectangle.
198: * Optimizes the algorithm used based on the number of line segments in the
199: * test geometry.
200: *
201: * @author Martin Davis
202: * @version 1.7
203: */
204: class LineIntersectsVisitor extends ShortCircuitedGeometryVisitor {
205: private Polygon rectangle;
206: private CoordinateSequence rectSeq;
207: private Envelope rectEnv;
208: private boolean intersects = false;
209:
210: public LineIntersectsVisitor(Polygon rectangle) {
211: this .rectangle = rectangle;
212: this .rectSeq = rectangle.getExteriorRing()
213: .getCoordinateSequence();
214: rectEnv = rectangle.getEnvelopeInternal();
215: }
216:
217: /**
218: * Reports whether any segment intersection exists.
219: *
220: * @return <code>true</code> if a segment intersection exists
221: * <code>false</code> if no segment intersection exists
222: */
223: public boolean intersects() {
224: return intersects;
225: }
226:
227: protected void visit(Geometry geom) {
228: Envelope elementEnv = geom.getEnvelopeInternal();
229: if (!rectEnv.intersects(elementEnv))
230: return;
231: // check if general relate algorithm should be used, since it's faster for large inputs
232: if (geom.getNumPoints() > RectangleIntersects.MAXIMUM_SCAN_SEGMENT_COUNT) {
233: intersects = rectangle.relate(geom).isIntersects();
234: return;
235: }
236: // if small enough, test for segment intersection directly
237: computeSegmentIntersection(geom);
238: }
239:
240: private void computeSegmentIntersection(Geometry geom) {
241: // check segment intersection
242: // get all lines from geom (e.g. if it's a multi-ring polygon)
243: List lines = LinearComponentExtracter.getLines(geom);
244: SegmentIntersectionTester si = new SegmentIntersectionTester();
245: boolean hasIntersection = si.hasIntersectionWithLineStrings(
246: rectSeq, lines);
247: if (hasIntersection) {
248: intersects = true;
249: return;
250: }
251: }
252:
253: protected boolean isDone() {
254: return intersects == true;
255: }
256: }
|