Class RectangleIntersects

1	/*
2	* Copyright (c) 2016 Vivid Solutions.
3	*
4	* All rights reserved. This program and the accompanying materials
5	* are made available under the terms of the Eclipse Public License 2.0
6	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
7	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
8	* and the Eclipse Distribution License is available at
9	*
10	* http://www.eclipse.org/org/documents/edl-v10.php.
11	*/
12
13	package org.locationtech.jts.operation.predicate;
14
15	import java.util.Iterator;
16	import java.util.List;
17
18	import org.locationtech.jts.algorithm.RectangleLineIntersector;
19	import org.locationtech.jts.algorithm.locate.SimplePointInAreaLocator;
20	import org.locationtech.jts.geom.Coordinate;
21	import org.locationtech.jts.geom.CoordinateSequence;
22	import org.locationtech.jts.geom.Envelope;
23	import org.locationtech.jts.geom.Geometry;
24	import org.locationtech.jts.geom.GeometryCollection;
25	import org.locationtech.jts.geom.LineString;
26	import org.locationtech.jts.geom.Polygon;
27	import org.locationtech.jts.geom.util.LinearComponentExtracter;
28	import org.locationtech.jts.geom.util.ShortCircuitedGeometryVisitor;
29
30
31	/**
32	* Implementation of the <tt>intersects</tt> spatial predicate
33	* optimized for the case where one {@link Geometry} is a rectangle.
34	* This class works for all
35	* input geometries, including {@link GeometryCollection}s.
36	* <p>
37	* As a further optimization,
38	* this class can be used in batch style
39	* to test many geometries
40	* against a single rectangle.
41	*
42	* @version 1.7
43	*/
44	public class RectangleIntersects
45	{
46	/**
47	* Tests whether a rectangle intersects a given geometry.
48	*
49	* @param rectangle
50	* a rectangular Polygon
51	* @param b
52	* a Geometry of any type
53	* @return true if the geometries intersect
54	*/
55	public static boolean intersects(Polygon rectangle, Geometry b)
56	{
57	RectangleIntersects rp = new RectangleIntersects(rectangle);
58	return rp.intersects(b);
59	}
60
61	private Polygon rectangle;
62
63	private Envelope rectEnv;
64
65	/**
66	* Create a new intersects computer for a rectangle.
67	*
68	* @param rectangle
69	* a rectangular Polygon
70	*/
71	public RectangleIntersects(Polygon rectangle)
72	{
73	this.rectangle = rectangle;
74	rectEnv = rectangle.getEnvelopeInternal();
75	}
76
77	/**
78	* Tests whether the given Geometry intersects
79	* the query rectangle.
80	*
81	* @param geom the Geometry to test (may be of any type)
82	* @return true if the geometry intersects the query rectangle
83	*/
84	public boolean intersects(Geometry geom)
85	{
86	if (!rectEnv.intersects(geom.getEnvelopeInternal()))
87	return false;
88
89	/**
90	* Test if rectangle envelope intersects any component envelope.
91	* This handles Point components as well
92	*/
93	EnvelopeIntersectsVisitor visitor = new EnvelopeIntersectsVisitor(rectEnv);
94	visitor.applyTo(geom);
95	if (visitor.intersects())
96	return true;
97
98	/**
99	* Test if any rectangle vertex is contained in the target geometry
100	*/
101	GeometryContainsPointVisitor ecpVisitor = new GeometryContainsPointVisitor(rectangle);
102	ecpVisitor.applyTo(geom);
103	if (ecpVisitor.containsPoint())
104	return true;
105
106	/**
107	* Test if any target geometry line segment intersects the rectangle
108	*/
109	RectangleIntersectsSegmentVisitor riVisitor = new RectangleIntersectsSegmentVisitor(rectangle);
110	riVisitor.applyTo(geom);
111	if (riVisitor.intersects())
112	return true;
113
114	return false;
115	}
116	}
117
118	/**
119	* Tests whether it can be concluded that a rectangle intersects a geometry,
120	* based on the relationship of the envelope(s) of the geometry.
121	*
122	* @author Martin Davis
123	* @version 1.7
124	*/
125	class EnvelopeIntersectsVisitor extends ShortCircuitedGeometryVisitor
126	{
127	private Envelope rectEnv;
128
129	private boolean intersects = false;
130
131	public EnvelopeIntersectsVisitor(Envelope rectEnv)
132	{
133	this.rectEnv = rectEnv;
134	}
135
136	/**
137	* Reports whether it can be concluded that an intersection occurs,
138	* or whether further testing is required.
139	*
140	* @return true if an intersection must occur
141	* or false if no conclusion about intersection can be made
142	*/
143	public boolean intersects()
144	{
145	return intersects;
146	}
147
148	protected void visit(Geometry element)
149	{
150	Envelope elementEnv = element.getEnvelopeInternal();
151
152	// disjoint => no intersection
153	if (!rectEnv.intersects(elementEnv)) {
154	return;
155	}
156	// rectangle contains target env => must intersect
157	if (rectEnv.contains(elementEnv)) {
158	intersects = true;
159	return;
160	}
161	/**
162	* Since the envelopes intersect and the test element is connected, if the
163	* test envelope is completely bisected by an edge of the rectangle the
164	* element and the rectangle must touch (This is basically an application of
165	* the Jordan Curve Theorem). The alternative situation is that the test
166	* envelope is "on a corner" of the rectangle envelope, i.e. is not
167	* completely bisected. In this case it is not possible to make a conclusion
168	* about the presence of an intersection.
169	*/
170	if (elementEnv.getMinX() >= rectEnv.getMinX()
171	&& elementEnv.getMaxX() <= rectEnv.getMaxX()) {
172	intersects = true;
173	return;
174	}
175	if (elementEnv.getMinY() >= rectEnv.getMinY()
176	&& elementEnv.getMaxY() <= rectEnv.getMaxY()) {
177	intersects = true;
178	return;
179	}
180	}
181
182	protected boolean isDone()
183	{
184	return intersects == true;
185	}
186	}
187
188	/**
189	* A visitor which tests whether it can be
190	* concluded that a geometry contains a vertex of
191	* a query geometry.
192	*
193	* @author Martin Davis
194	* @version 1.7
195	*/
196	class GeometryContainsPointVisitor extends ShortCircuitedGeometryVisitor
197	{
198	private CoordinateSequence rectSeq;
199
200	private Envelope rectEnv;
201
202	private boolean containsPoint = false;
203
204	public GeometryContainsPointVisitor(Polygon rectangle)
205	{
206	this.rectSeq = rectangle.getExteriorRing().getCoordinateSequence();
207	rectEnv = rectangle.getEnvelopeInternal();
208	}
209
210	/**
211	* Reports whether it can be concluded that a corner point of the rectangle is
212	* contained in the geometry, or whether further testing is required.
213	*
214	* @return true if a corner point is contained
215	* or false if no conclusion about intersection can be made
216	*/
217	public boolean containsPoint()
218	{
219	return containsPoint;
220	}
221
222	protected void visit(Geometry geom)
223	{
224	// if test geometry is not polygonal this check is not needed
225	if (!(geom instanceof Polygon))
226	return;
227
228	// skip if envelopes do not intersect
229	Envelope elementEnv = geom.getEnvelopeInternal();
230	if (!rectEnv.intersects(elementEnv))
231	return;
232
233	// test each corner of rectangle for inclusion
234	Coordinate rectPt = new Coordinate();
235	for (int i = 0; i < 4; i++) {
236	rectSeq.getCoordinate(i, rectPt);
237	if (!elementEnv.contains(rectPt))
238	continue;
239	// check rect point in poly (rect is known not to touch polygon at this
240	// point)
241	if (SimplePointInAreaLocator.containsPointInPolygon(rectPt,
242	(Polygon) geom)) {
243	containsPoint = true;
244	return;
245	}
246	}
247	}
248
249	protected boolean isDone()
250	{
251	return containsPoint == true;
252	}
253	}
254
255
256	/**
257	* A visitor to test for intersection between the query
258	* rectangle and the line segments of the geometry.
259	*
260	* @author Martin Davis
261	*
262	*/
263	class RectangleIntersectsSegmentVisitor extends ShortCircuitedGeometryVisitor
264	{
265	private Envelope rectEnv;
266	private RectangleLineIntersector rectIntersector;
267
268	private boolean hasIntersection = false;
269	private Coordinate p0 = new Coordinate();
270	private Coordinate p1 = new Coordinate();
271
272	/**
273	* Creates a visitor for checking rectangle intersection
274	* with segments
275	*
276	* @param rectangle the query rectangle
277	*/
278	public RectangleIntersectsSegmentVisitor(Polygon rectangle)
279	{
280	rectEnv = rectangle.getEnvelopeInternal();
281	rectIntersector = new RectangleLineIntersector(rectEnv);
282	}
283
284	/**
285	* Reports whether any segment intersection exists.
286	*
287	* @return true if a segment intersection exists
288	* or false if no segment intersection exists
289	*/
290	public boolean intersects()
291	{
292	return hasIntersection;
293	}
294
295	protected void visit(Geometry geom)
296	{
297	/**
298	* It may be the case that the rectangle and the
299	* envelope of the geometry component are disjoint,
300	* so it is worth checking this simple condition.
301	*/
302	Envelope elementEnv = geom.getEnvelopeInternal();
303	if (!rectEnv.intersects(elementEnv))
304	return;
305
306	// check segment intersections
307	// get all lines from geometry component
308	// (there may be more than one if it's a multi-ring polygon)
309	List lines = LinearComponentExtracter.getLines(geom);
310	checkIntersectionWithLineStrings(lines);
311	}
312
313	private void checkIntersectionWithLineStrings(List lines)
314	{
315	for (Iterator i = lines.iterator(); i.hasNext(); ) {
316	LineString testLine = (LineString) i.next();
317	checkIntersectionWithSegments(testLine);
318	if (hasIntersection)
319	return;
320	}
321	}
322
323	private void checkIntersectionWithSegments(LineString testLine)
324	{
325	CoordinateSequence seq1 = testLine.getCoordinateSequence();
326	for (int j = 1; j < seq1.size(); j++) {
327	seq1.getCoordinate(j - 1, p0);
328	seq1.getCoordinate(j, p1);
329
330	if (rectIntersector.intersects(p0, p1)) {
331	hasIntersection = true;
332	return;
333	}
334	}
335	}
336
337	protected boolean isDone()
338	{
339	return hasIntersection == true;
340	}
341	}
342