Class Envelope

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	package org.locationtech.jts.geom;
13
14	import java.io.Serializable;
15
16	/**
17	* Defines a rectangular region of the 2D coordinate plane.
18	* It is often used to represent the bounding box of a {@link Geometry},
19	* e.g. the minimum and maximum x and y values of the {@link Coordinate}s.
20	* <p>
21	* Envelopes support infinite or half-infinite regions, by using the values of
22	* <code>Double.POSITIVE_INFINITY</code> and <code>Double.NEGATIVE_INFINITY</code>.
23	* Envelope objects may have a null value.
24	* <p>
25	* When Envelope objects are created or initialized,
26	* the supplies extent values are automatically sorted into the correct order.
27	*
28	*@version 1.7
29	*/
30	public class Envelope
31	implements Comparable, Serializable
32	{
33	private static final long serialVersionUID = 5873921885273102420L;
34
35	public int hashCode() {
36	//Algorithm from Effective Java by Joshua Bloch [Jon Aquino]
37	int result = 17;
38	result = 37 * result + Coordinate.hashCode(minx);
39	result = 37 * result + Coordinate.hashCode(maxx);
40	result = 37 * result + Coordinate.hashCode(miny);
41	result = 37 * result + Coordinate.hashCode(maxy);
42	return result;
43	}
44
45	/**
46	* Test the point q to see whether it intersects the Envelope defined by p1-p2
47	* @param p1 one extremal point of the envelope
48	* @param p2 another extremal point of the envelope
49	* @param q the point to test for intersection
50	* @return <code>true</code> if q intersects the envelope p1-p2
51	*/
52	public static boolean intersects(Coordinate p1, Coordinate p2, Coordinate q)
53	{
54	//OptimizeIt shows that Math#min and Math#max here are a bottleneck.
55	//Replace with direct comparisons. [Jon Aquino]
56	if (((q.x >= (p1.x < p2.x ? p1.x : p2.x)) && (q.x <= (p1.x > p2.x ? p1.x : p2.x))) &&
57	((q.y >= (p1.y < p2.y ? p1.y : p2.y)) && (q.y <= (p1.y > p2.y ? p1.y : p2.y)))) {
58	return true;
59	}
60	return false;
61	}
62
63	/**
64	* Tests whether the envelope defined by p1-p2
65	* and the envelope defined by q1-q2
66	* intersect.
67	*
68	* @param p1 one extremal point of the envelope P
69	* @param p2 another extremal point of the envelope P
70	* @param q1 one extremal point of the envelope Q
71	* @param q2 another extremal point of the envelope Q
72	* @return <code>true</code> if Q intersects P
73	*/
74	public static boolean intersects(Coordinate p1, Coordinate p2, Coordinate q1, Coordinate q2)
75	{
76	double minq = Math.min(q1.x, q2.x);
77	double maxq = Math.max(q1.x, q2.x);
78	double minp = Math.min(p1.x, p2.x);
79	double maxp = Math.max(p1.x, p2.x);
80
81	if( minp > maxq )
82	return false;
83	if( maxp < minq )
84	return false;
85
86	minq = Math.min(q1.y, q2.y);
87	maxq = Math.max(q1.y, q2.y);
88	minp = Math.min(p1.y, p2.y);
89	maxp = Math.max(p1.y, p2.y);
90
91	if( minp > maxq )
92	return false;
93	if( maxp < minq )
94	return false;
95	return true;
96	}
97
98	/**
99	* the minimum x-coordinate
100	*/
101	private double minx;
102
103	/**
104	* the maximum x-coordinate
105	*/
106	private double maxx;
107
108	/**
109	* the minimum y-coordinate
110	*/
111	private double miny;
112
113	/**
114	* the maximum y-coordinate
115	*/
116	private double maxy;
117
118	/**
119	* Creates a null <code>Envelope</code>.
120	*/
121	public Envelope() {
122	init();
123	}
124
125	/**
126	* Creates an <code>Envelope</code> for a region defined by maximum and minimum values.
127	*
128	*@param x1 the first x-value
129	*@param x2 the second x-value
130	*@param y1 the first y-value
131	*@param y2 the second y-value
132	*/
133	public Envelope(double x1, double x2, double y1, double y2)
134	{
135	init(x1, x2, y1, y2);
136	}
137
138	/**
139	* Creates an <code>Envelope</code> for a region defined by two Coordinates.
140	*
141	*@param p1 the first Coordinate
142	*@param p2 the second Coordinate
143	*/
144	public Envelope(Coordinate p1, Coordinate p2)
145	{
146	init(p1.x, p2.x, p1.y, p2.y);
147	}
148
149	/**
150	* Creates an <code>Envelope</code> for a region defined by a single Coordinate.
151	*
152	*@param p the Coordinate
153	*/
154	public Envelope(Coordinate p)
155	{
156	init(p.x, p.x, p.y, p.y);
157	}
158
159	/**
160	* Create an <code>Envelope</code> from an existing Envelope.
161	*
162	*@param env the Envelope to initialize from
163	*/
164	public Envelope(Envelope env)
165	{
166	init(env);
167	}
168
169	/**
170	* Initialize to a null <code>Envelope</code>.
171	*/
172	public void init()
173	{
174	setToNull();
175	}
176
177	/**
178	* Initialize an <code>Envelope</code> for a region defined by maximum and minimum values.
179	*
180	*@param x1 the first x-value
181	*@param x2 the second x-value
182	*@param y1 the first y-value
183	*@param y2 the second y-value
184	*/
185	public void init(double x1, double x2, double y1, double y2)
186	{
187	if (x1 < x2) {
188	minx = x1;
189	maxx = x2;
190	}
191	else {
192	minx = x2;
193	maxx = x1;
194	}
195	if (y1 < y2) {
196	miny = y1;
197	maxy = y2;
198	}
199	else {
200	miny = y2;
201	maxy = y1;
202	}
203	}
204
205	/**
206	* Creates a copy of this envelope object.
207	*
208	* @return a copy of this envelope
209	*/
210	public Envelope copy() {
211	return new Envelope(this);
212	}
213
214	/**
215	* Initialize an <code>Envelope</code> to a region defined by two Coordinates.
216	*
217	*@param p1 the first Coordinate
218	*@param p2 the second Coordinate
219	*/
220	public void init(Coordinate p1, Coordinate p2)
221	{
222	init(p1.x, p2.x, p1.y, p2.y);
223	}
224
225	/**
226	* Initialize an <code>Envelope</code> to a region defined by a single Coordinate.
227	*
228	*@param p the coordinate
229	*/
230	public void init(Coordinate p)
231	{
232	init(p.x, p.x, p.y, p.y);
233	}
234
235	/**
236	* Initialize an <code>Envelope</code> from an existing Envelope.
237	*
238	*@param env the Envelope to initialize from
239	*/
240	public void init(Envelope env)
241	{
242	this.minx = env.minx;
243	this.maxx = env.maxx;
244	this.miny = env.miny;
245	this.maxy = env.maxy;
246	}
247
248
249	/**
250	* Makes this <code>Envelope</code> a "null" envelope, that is, the envelope
251	* of the empty geometry.
252	*/
253	public void setToNull() {
254	minx = 0;
255	maxx = -1;
256	miny = 0;
257	maxy = -1;
258	}
259
260	/**
261	* Returns <code>true</code> if this <code>Envelope</code> is a "null"
262	* envelope.
263	*
264	*@return <code>true</code> if this <code>Envelope</code> is uninitialized
265	* or is the envelope of the empty geometry.
266	*/
267	public boolean isNull() {
268	return maxx < minx;
269	}
270
271	/**
272	* Returns the difference between the maximum and minimum x values.
273	*
274	*@return max x - min x, or 0 if this is a null <code>Envelope</code>
275	*/
276	public double getWidth() {
277	if (isNull()) {
278	return 0;
279	}
280	return maxx - minx;
281	}
282
283	/**
284	* Returns the difference between the maximum and minimum y values.
285	*
286	*@return max y - min y, or 0 if this is a null <code>Envelope</code>
287	*/
288	public double getHeight() {
289	if (isNull()) {
290	return 0;
291	}
292	return maxy - miny;
293	}
294
295	/**
296	* Gets the length of the diameter (diagonal) of the envelope.
297	*
298	* @return the diameter length
299	*/
300	public double getDiameter() {
301	if (isNull()) {
302	return 0;
303	}
304	double w = getWidth();
305	double h = getHeight();
306	return Math.sqrt(ww + hh);
307	}
308	/**
309	* Returns the <code>Envelope</code>s minimum x-value. min x > max x
310	* indicates that this is a null <code>Envelope</code>.
311	*
312	*@return the minimum x-coordinate
313	*/
314	public double getMinX() {
315	return minx;
316	}
317
318	/**
319	* Returns the <code>Envelope</code>s maximum x-value. min x > max x
320	* indicates that this is a null <code>Envelope</code>.
321	*
322	*@return the maximum x-coordinate
323	*/
324	public double getMaxX() {
325	return maxx;
326	}
327
328	/**
329	* Returns the <code>Envelope</code>s minimum y-value. min y > max y
330	* indicates that this is a null <code>Envelope</code>.
331	*
332	*@return the minimum y-coordinate
333	*/
334	public double getMinY() {
335	return miny;
336	}
337
338	/**
339	* Returns the <code>Envelope</code>s maximum y-value. min y > max y
340	* indicates that this is a null <code>Envelope</code>.
341	*
342	*@return the maximum y-coordinate
343	*/
344	public double getMaxY() {
345	return maxy;
346	}
347
348	/**
349	* Gets the area of this envelope.
350	*
351	* @return the area of the envelope
352	* @return 0.0 if the envelope is null
353	*/
354	public double getArea()
355	{
356	return getWidth() * getHeight();
357	}
358
359	/**
360	* Gets the minimum extent of this envelope across both dimensions.
361	*
362	* @return the minimum extent of this envelope
363	*/
364	public double minExtent()
365	{
366	if (isNull()) return 0.0;
367	double w = getWidth();
368	double h = getHeight();
369	if (w < h) return w;
370	return h;
371	}
372
373	/**
374	* Gets the maximum extent of this envelope across both dimensions.
375	*
376	* @return the maximum extent of this envelope
377	*/
378	public double maxExtent()
379	{
380	if (isNull()) return 0.0;
381	double w = getWidth();
382	double h = getHeight();
383	if (w > h) return w;
384	return h;
385	}
386
387	/**
388	* Enlarges this <code>Envelope</code> so that it contains
389	* the given {@link Coordinate}.
390	* Has no effect if the point is already on or within the envelope.
391	*
392	*@param p the Coordinate to expand to include
393	*/
394	public void expandToInclude(Coordinate p)
395	{
396	expandToInclude(p.x, p.y);
397	}
398
399	/**
400	* Expands this envelope by a given distance in all directions.
401	* Both positive and negative distances are supported.
402	*
403	* @param distance the distance to expand the envelope
404	*/
405	public void expandBy(double distance)
406	{
407	expandBy(distance, distance);
408	}
409
410	/**
411	* Expands this envelope by a given distance in all directions.
412	* Both positive and negative distances are supported.
413	*
414	* @param deltaX the distance to expand the envelope along the the X axis
415	* @param deltaY the distance to expand the envelope along the the Y axis
416	*/
417	public void expandBy(double deltaX, double deltaY)
418	{
419	if (isNull()) return;
420
421	minx -= deltaX;
422	maxx += deltaX;
423	miny -= deltaY;
424	maxy += deltaY;
425
426	// check for envelope disappearing
427	if (minx > maxx \|\| miny > maxy)
428	setToNull();
429	}
430
431	/**
432	* Enlarges this <code>Envelope</code> so that it contains
433	* the given point.
434	* Has no effect if the point is already on or within the envelope.
435	*
436	*@param x the value to lower the minimum x to or to raise the maximum x to
437	*@param y the value to lower the minimum y to or to raise the maximum y to
438	*/
439	public void expandToInclude(double x, double y) {
440	if (isNull()) {
441	minx = x;
442	maxx = x;
443	miny = y;
444	maxy = y;
445	}
446	else {
447	if (x < minx) {
448	minx = x;
449	}
450	if (x > maxx) {
451	maxx = x;
452	}
453	if (y < miny) {
454	miny = y;
455	}
456	if (y > maxy) {
457	maxy = y;
458	}
459	}
460	}
461
462	/**
463	* Enlarges this <code>Envelope</code> so that it contains
464	* the <code>other</code> Envelope.
465	* Has no effect if <code>other</code> is wholly on or
466	* within the envelope.
467	*
468	*@param other the <code>Envelope</code> to expand to include
469	*/
470	public void expandToInclude(Envelope other) {
471	if (other.isNull()) {
472	return;
473	}
474	if (isNull()) {
475	minx = other.getMinX();
476	maxx = other.getMaxX();
477	miny = other.getMinY();
478	maxy = other.getMaxY();
479	}
480	else {
481	if (other.minx < minx) {
482	minx = other.minx;
483	}
484	if (other.maxx > maxx) {
485	maxx = other.maxx;
486	}
487	if (other.miny < miny) {
488	miny = other.miny;
489	}
490	if (other.maxy > maxy) {
491	maxy = other.maxy;
492	}
493	}
494	}
495
496	/**
497	* Translates this envelope by given amounts in the X and Y direction.
498	*
499	* @param transX the amount to translate along the X axis
500	* @param transY the amount to translate along the Y axis
501	*/
502	public void translate(double transX, double transY) {
503	if (isNull()) {
504	return;
505	}
506	init(getMinX() + transX, getMaxX() + transX,
507	getMinY() + transY, getMaxY() + transY);
508	}
509
510	/**
511	* Computes the coordinate of the centre of this envelope (as long as it is non-null
512	*
513	* @return the centre coordinate of this envelope
514	* <code>null</code> if the envelope is null
515	*/
516	public Coordinate centre() {
517	if (isNull()) return null;
518	return new Coordinate(
519	(getMinX() + getMaxX()) / 2.0,
520	(getMinY() + getMaxY()) / 2.0);
521	}
522
523	/**
524	* Computes the intersection of two {@link Envelope}s.
525	*
526	* @param env the envelope to intersect with
527	* @return a new Envelope representing the intersection of the envelopes (this will be
528	* the null envelope if either argument is null, or they do not intersect
529	*/
530	public Envelope intersection(Envelope env)
531	{
532	if (isNull() \|\| env.isNull() \|\| ! intersects(env)) return new Envelope();
533
534	double intMinX = minx > env.minx ? minx : env.minx;
535	double intMinY = miny > env.miny ? miny : env.miny;
536	double intMaxX = maxx < env.maxx ? maxx : env.maxx;
537	double intMaxY = maxy < env.maxy ? maxy : env.maxy;
538	return new Envelope(intMinX, intMaxX, intMinY, intMaxY);
539	}
540
541	/**
542	* Tests if the region defined by <code>other</code>
543	* intersects the region of this <code>Envelope</code>.
544	*
545	*@param other the <code>Envelope</code> which this <code>Envelope</code> is
546	* being checked for intersecting
547	*@return <code>true</code> if the <code>Envelope</code>s intersect
548	*/
549	public boolean intersects(Envelope other) {
550	if (isNull() \|\| other.isNull()) { return false; }
551	return !(other.minx > maxx \|\|
552	other.maxx < minx \|\|
553	other.miny > maxy \|\|
554	other.maxy < miny);
555	}
556
557
558	/**
559	* Tests if the extent defined by two extremal points
560	* intersects the extent of this <code>Envelope</code>.
561	*
562	*@param a a point
563	*@param b another point
564	*@return <code>true</code> if the extents intersect
565	*/
566	public boolean intersects(Coordinate a, Coordinate b) {
567	if (isNull()) { return false; }
568
569	double envminx = (a.x < b.x) ? a.x : b.x;
570	if (envminx > maxx) return false;
571
572	double envmaxx = (a.x > b.x) ? a.x : b.x;
573	if (envmaxx < minx) return false;
574
575	double envminy = (a.y < b.y) ? a.y : b.y;
576	if (envminy > maxy) return false;
577
578	double envmaxy = (a.y > b.y) ? a.y : b.y;
579	if (envmaxy < miny) return false;
580
581	return true;
582	}
583
584	/**
585	* Tests if the region defined by <code>other</code>
586	* is disjoint from the region of this <code>Envelope</code>.
587	*
588	*@param other the <code>Envelope</code> being checked for disjointness
589	*@return <code>true</code> if the <code>Envelope</code>s are disjoint
590	*
591	*@see #intersects(Envelope)
592	*/
593	public boolean disjoint(Envelope other) {
594	if (isNull() \|\| other.isNull()) { return true; }
595	return other.minx > maxx \|\|
596	other.maxx < minx \|\|
597	other.miny > maxy \|\|
598	other.maxy < miny;
599	}
600
601	/**
602	* @deprecated Use #intersects instead. In the future, #overlaps may be
603	* changed to be a true overlap check; that is, whether the intersection is
604	* two-dimensional.
605	*/
606	public boolean overlaps(Envelope other) {
607	return intersects(other);
608	}
609
610	/**
611	* Tests if the point <code>p</code>
612	* intersects (lies inside) the region of this <code>Envelope</code>.
613	*
614	*@param p the <code>Coordinate</code> to be tested
615	*@return <code>true</code> if the point intersects this <code>Envelope</code>
616	*/
617	public boolean intersects(Coordinate p) {
618	return intersects(p.x, p.y);
619	}
620	/**
621	* @deprecated Use #intersects instead.
622	*/
623	public boolean overlaps(Coordinate p) {
624	return intersects(p);
625	}
626	/**
627	* Check if the point <code>(x, y)</code>
628	* intersects (lies inside) the region of this <code>Envelope</code>.
629	*
630	*@param x the x-ordinate of the point
631	*@param y the y-ordinate of the point
632	*@return <code>true</code> if the point overlaps this <code>Envelope</code>
633	*/
634	public boolean intersects(double x, double y) {
635	if (isNull()) return false;
636	return ! (x > maxx \|\|
637	x < minx \|\|
638	y > maxy \|\|
639	y < miny);
640	}
641	/**
642	* @deprecated Use #intersects instead.
643	*/
644	public boolean overlaps(double x, double y) {
645	return intersects(x, y);
646	}
647
648	/**
649	* Tests if the <code>Envelope other</code>
650	* lies wholely inside this <code>Envelope</code> (inclusive of the boundary).
651	* <p>
652	* Note that this is <b>not</b> the same definition as the SFS <tt>contains</tt>,
653	* which would exclude the envelope boundary.
654	*
655	*@param other the <code>Envelope</code> to check
656	*@return true if <code>other</code> is contained in this <code>Envelope</code>
657	*
658	*@see #covers(Envelope)
659	*/
660	public boolean contains(Envelope other) {
661	return covers(other);
662	}
663
664	/**
665	* Tests if the given point lies in or on the envelope.
666	* <p>
667	* Note that this is <b>not</b> the same definition as the SFS <tt>contains</tt>,
668	* which would exclude the envelope boundary.
669	*
670	*@param p the point which this <code>Envelope</code> is
671	* being checked for containing
672	*@return <code>true</code> if the point lies in the interior or
673	* on the boundary of this <code>Envelope</code>.
674	*
675	*@see #covers(Coordinate)
676	*/
677	public boolean contains(Coordinate p) {
678	return covers(p);
679	}
680
681	/**
682	* Tests if the given point lies in or on the envelope.
683	* <p>
684	* Note that this is <b>not</b> the same definition as the SFS <tt>contains</tt>,
685	* which would exclude the envelope boundary.
686	*
687	*@param x the x-coordinate of the point which this <code>Envelope</code> is
688	* being checked for containing
689	*@param y the y-coordinate of the point which this <code>Envelope</code> is
690	* being checked for containing
691	*@return <code>true</code> if <code>(x, y)</code> lies in the interior or
692	* on the boundary of this <code>Envelope</code>.
693	*
694	*@see #covers(double, double)
695	*/
696	public boolean contains(double x, double y) {
697	return covers(x, y);
698	}
699
700	/**
701	* Tests if the given point lies in or on the envelope.
702	*
703	*@param x the x-coordinate of the point which this <code>Envelope</code> is
704	* being checked for containing
705	*@param y the y-coordinate of the point which this <code>Envelope</code> is
706	* being checked for containing
707	*@return <code>true</code> if <code>(x, y)</code> lies in the interior or
708	* on the boundary of this <code>Envelope</code>.
709	*/
710	public boolean covers(double x, double y) {
711	if (isNull()) return false;
712	return x >= minx &&
713	x <= maxx &&
714	y >= miny &&
715	y <= maxy;
716	}
717
718	/**
719	* Tests if the given point lies in or on the envelope.
720	*
721	*@param p the point which this <code>Envelope</code> is
722	* being checked for containing
723	*@return <code>true</code> if the point lies in the interior or
724	* on the boundary of this <code>Envelope</code>.
725	*/
726	public boolean covers(Coordinate p) {
727	return covers(p.x, p.y);
728	}
729
730	/**
731	* Tests if the <code>Envelope other</code>
732	* lies wholely inside this <code>Envelope</code> (inclusive of the boundary).
733	*
734	*@param other the <code>Envelope</code> to check
735	*@return true if this <code>Envelope</code> covers the <code>other</code>
736	*/
737	public boolean covers(Envelope other) {
738	if (isNull() \|\| other.isNull()) { return false; }
739	return other.getMinX() >= minx &&
740	other.getMaxX() <= maxx &&
741	other.getMinY() >= miny &&
742	other.getMaxY() <= maxy;
743	}
744
745	/**
746	* Computes the distance between this and another
747	* <code>Envelope</code>.
748	* The distance between overlapping Envelopes is 0. Otherwise, the
749	* distance is the Euclidean distance between the closest points.
750	*/
751	public double distance(Envelope env)
752	{
753	if (intersects(env)) return 0;
754
755	double dx = 0.0;
756	if (maxx < env.minx)
757	dx = env.minx - maxx;
758	else if (minx > env.maxx)
759	dx = minx - env.maxx;
760
761	double dy = 0.0;
762	if (maxy < env.miny)
763	dy = env.miny - maxy;
764	else if (miny > env.maxy) dy = miny - env.maxy;
765
766	// if either is zero, the envelopes overlap either vertically or horizontally
767	if (dx == 0.0) return dy;
768	if (dy == 0.0) return dx;
769	return Math.sqrt(dx * dx + dy * dy);
770	}
771
772	public boolean equals(Object other) {
773	if (!(other instanceof Envelope)) {
774	return false;
775	}
776	Envelope otherEnvelope = (Envelope) other;
777	if (isNull()) {
778	return otherEnvelope.isNull();
779	}
780	return maxx == otherEnvelope.getMaxX() &&
781	maxy == otherEnvelope.getMaxY() &&
782	minx == otherEnvelope.getMinX() &&
783	miny == otherEnvelope.getMinY();
784	}
785
786	public String toString()
787	{
788	return "Env[" + minx + " : " + maxx + ", " + miny + " : " + maxy + "]";
789	}
790
791	/**
792	* Compares two envelopes using lexicographic ordering.
793	* The ordering comparison is based on the usual numerical
794	* comparison between the sequence of ordinates.
795	* Null envelopes are less than all non-null envelopes.
796	*
797	* @param o an Envelope object
798	*/
799	public int compareTo(Object o) {
800	Envelope env = (Envelope) o;
801	// compare nulls if present
802	if (isNull()) {
803	if (env.isNull()) return 0;
804	return -1;
805	}
806	else {
807	if (env.isNull()) return 1;
808	}
809	// compare based on numerical ordering of ordinates
810	if (minx < env.minx) return -1;
811	if (minx > env.minx) return 1;
812	if (miny < env.miny) return -1;
813	if (miny > env.miny) return 1;
814	if (maxx < env.maxx) return -1;
815	if (maxx > env.maxx) return 1;
816	if (maxy < env.maxy) return -1;
817	if (maxy > env.maxy) return 1;
818	return 0;
819
820
821	}
822	}
823
824