Class RectangleLineIntersector

1	/*
2	* Copyright (c) 2016 Martin Davis.
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	package org.locationtech.jts.algorithm;
13
14	import org.locationtech.jts.geom.Coordinate;
15	import org.locationtech.jts.geom.Envelope;
16
17	/**
18	* Computes whether a rectangle intersects line segments.
19	* <p>
20	* Rectangles contain a large amount of inherent symmetry
21	* (or to put it another way, although they contain four
22	* coordinates they only actually contain 4 ordinates
23	* worth of information).
24	* The algorithm used takes advantage of the symmetry of
25	* the geometric situation
26	* to optimize performance by minimizing the number
27	* of line intersection tests.
28	*
29	* @author Martin Davis
30	*
31	*/
32	public class RectangleLineIntersector
33	{
34	// for intersection testing, don't need to set precision model
35	private LineIntersector li = new RobustLineIntersector();
36
37	private Envelope rectEnv;
38
39	private Coordinate diagUp0;
40	private Coordinate diagUp1;
41	private Coordinate diagDown0;
42	private Coordinate diagDown1;
43
44	/**
45	* Creates a new intersector for the given query rectangle,
46	* specified as an {@link Envelope}.
47	*
48	*
49	* @param rectEnv the query rectangle, specified as an Envelope
50	*/
51	public RectangleLineIntersector(Envelope rectEnv)
52	{
53	this.rectEnv = rectEnv;
54
55	/**
56	* Up and Down are the diagonal orientations
57	* relative to the Left side of the rectangle.
58	* Index 0 is the left side, 1 is the right side.
59	*/
60	diagUp0 = new Coordinate(rectEnv.getMinX(), rectEnv.getMinY());
61	diagUp1 = new Coordinate(rectEnv.getMaxX(), rectEnv.getMaxY());
62	diagDown0 = new Coordinate(rectEnv.getMinX(), rectEnv.getMaxY());
63	diagDown1 = new Coordinate(rectEnv.getMaxX(), rectEnv.getMinY());
64	}
65
66	/**
67	* Tests whether the query rectangle intersects a
68	* given line segment.
69	*
70	* @param p0 the first endpoint of the segment
71	* @param p1 the second endpoint of the segment
72	* @return true if the rectangle intersects the segment
73	*/
74	public boolean intersects(Coordinate p0, Coordinate p1)
75	{
76	// TODO: confirm that checking envelopes first is faster
77
78	/**
79	* If the segment envelope is disjoint from the
80	* rectangle envelope, there is no intersection
81	*/
82	Envelope segEnv = new Envelope(p0, p1);
83	if (! rectEnv.intersects(segEnv))
84	return false;
85
86	/**
87	* If either segment endpoint lies in the rectangle,
88	* there is an intersection.
89	*/
90	if (rectEnv.intersects(p0)) return true;
91	if (rectEnv.intersects(p1)) return true;
92
93	/**
94	* Normalize segment.
95	* This makes p0 less than p1,
96	* so that the segment runs to the right,
97	* or vertically upwards.
98	*/
99	if (p0.compareTo(p1) > 0) {
100	Coordinate tmp = p0;
101	p0 = p1;
102	p1 = tmp;
103	}
104	/**
105	* Compute angle of segment.
106	* Since the segment is normalized to run left to right,
107	* it is sufficient to simply test the Y ordinate.
108	* "Upwards" means relative to the left end of the segment.
109	*/
110	boolean isSegUpwards = false;
111	if (p1.y > p0.y)
112	isSegUpwards = true;
113
114	/**
115	* Since we now know that neither segment endpoint
116	* lies in the rectangle, there are two possible
117	* situations:
118	* 1) the segment is disjoint to the rectangle
119	* 2) the segment crosses the rectangle completely.
120	*
121	* In the case of a crossing, the segment must intersect
122	* a diagonal of the rectangle.
123	*
124	* To distinguish these two cases, it is sufficient
125	* to test intersection with
126	* a single diagonal of the rectangle,
127	* namely the one with slope "opposite" to the slope
128	* of the segment.
129	* (Note that if the segment is axis-parallel,
130	* it must intersect both diagonals, so this is
131	* still sufficient.)
132	*/
133	if (isSegUpwards) {
134	li.computeIntersection(p0, p1, diagDown0, diagDown1);
135	}
136	else {
137	li.computeIntersection(p0, p1, diagUp0, diagUp1);
138	}
139	if (li.hasIntersection())
140	return true;
141	return false;
142
143
144	}
145	}
146