Doc Classic

Class EnvelopeDistance

  1 /*
  2  * Copyright (c) 2019 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.index.strtree;
 13  
 14 import org.locationtech.jts.geom.Envelope;
 15  
 16 /**
 17  * Functions for computing distances between {@link Envelope}s.
 18  * 
 19  * @author mdavis
 20  *
 21  */
 22 public class EnvelopeDistance 
 23 {
 24   /**
 25    * Computes the maximum distance between the points defining two envelopes.
 26    * It is equal to the length of the diagonal of 
 27    * the envelope containing both input envelopes.
 28    * This is a coarse upper bound on the distance between 
 29    * geometries bounded by the envelopes.
 30    * 
 31    * @param env1 an envelope
 32    * @param env2 an envelope
 33    * @return the maximum distance between the points defining the envelopes
 34    */
 35   public static double maximumDistance(Envelope env1, Envelope env2)
 36   {
 37     double minx = Math.min(env1.getMinX(), env2.getMinX());
 38     double miny = Math.min(env1.getMinY(), env2.getMinY());
 39     double maxx = Math.max(env1.getMaxX(), env2.getMaxX());
 40     double maxy = Math.max(env1.getMaxY(), env2.getMaxY());
 41     return distance(minx, miny, maxx, maxy);
 42   }
 43   
 44   private static double distance(double x1, double y1, double x2, double y2) {
 45     double dx = x2 - x1;
 46     double dy = y2 - y1;
 47     return Math.sqrt(dx * dx + dy * dy);    
 48   }
 49   
 50   /**
 51    * Computes the Min-Max Distance between two {@link Envelope}s.
 52    * It is equal to the minimum of the maximum distances between all pairs of
 53    * edge segments from the two envelopes.
 54    * This is the tight upper bound on the distance between 
 55    * geometric items bounded by the envelopes.
 56    * <p>
 57    * Theoretically this bound can be used in the R-tree nearest-neighbour branch-and-bound search
 58    * instead of {@link #maximumDistance(Envelope, Envelope)}.
 59    * However, little performance improvement is observed in practice.
 60    * 
 61    * @param a an envelope
 62    * @param b an envelope
 63    * @return the min-max-distance between the envelopes
 64    */
 65   public static double minMaxDistance(Envelope a, Envelope b)
 66   {
 67     double aminx = a.getMinX();
 68     double aminy = a.getMinY();
 69     double amaxx = a.getMaxX();
 70     double amaxy = a.getMaxY();
 71     double bminx = b.getMinX();
 72     double bminy = b.getMinY();
 73     double bmaxx = b.getMaxX();
 74     double bmaxy = b.getMaxY();
 75     
 76     double dist =         maxDistance(aminx, aminy, aminx, amaxy, bminx, bminy, bminx, bmaxy);
 77     dist = Math.min(dist, maxDistance(aminx, aminy, aminx, amaxy, bminx, bminy, bmaxx, bminy));
 78     dist = Math.min(dist, maxDistance(aminx, aminy, aminx, amaxy, bmaxx, bmaxy, bminx, bmaxy));
 79     dist = Math.min(dist, maxDistance(aminx, aminy, aminx, amaxy, bmaxx, bmaxy, bmaxx, bminy));
 80   
 81     dist = Math.min(dist, maxDistance(aminx, aminy, amaxx, aminy, bminx, bminy, bminx, bmaxy));
 82     dist = Math.min(dist, maxDistance(aminx, aminy, amaxx, aminy, bminx, bminy, bmaxx, bminy));
 83     dist = Math.min(dist, maxDistance(aminx, aminy, amaxx, aminy, bmaxx, bmaxy, bminx, bmaxy));
 84     dist = Math.min(dist, maxDistance(aminx, aminy, amaxx, aminy, bmaxx, bmaxy, bmaxx, bminy));
 85     
 86     dist = Math.min(dist, maxDistance(amaxx, amaxy, aminx, amaxy, bminx, bminy, bminx, bmaxy));
 87     dist = Math.min(dist, maxDistance(amaxx, amaxy, aminx, amaxy, bminx, bminy, bmaxx, bminy));
 88     dist = Math.min(dist, maxDistance(amaxx, amaxy, aminx, amaxy, bmaxx, bmaxy, bminx, bmaxy));
 89     dist = Math.min(dist, maxDistance(amaxx, amaxy, aminx, amaxy, bmaxx, bmaxy, bmaxx, bminy));
 90     
 91     dist = Math.min(dist, maxDistance(amaxx, amaxy, amaxx, aminy, bminx, bminy, bminx, bmaxy));
 92     dist = Math.min(dist, maxDistance(amaxx, amaxy, amaxx, aminy, bminx, bminy, bmaxx, bminy));
 93     dist = Math.min(dist, maxDistance(amaxx, amaxy, amaxx, aminy, bmaxx, bmaxy, bminx, bmaxy));
 94     dist = Math.min(dist, maxDistance(amaxx, amaxy, amaxx, aminy, bmaxx, bmaxy, bmaxx, bminy));
 95     
 96     return dist;
 97   }
 98  
 99   /**
100    * Computes the maximum distance between two line segments.
101    * 
102    * @param ax1 x ordinate of first endpoint of segment 1
103    * @param ay1 y ordinate of first endpoint of segment 1
104    * @param ax2 x ordinate of second endpoint of segment 1
105    * @param ay2 y ordinate of second endpoint of segment 1
106    * @param bx1 x ordinate of first endpoint of segment 2
107    * @param by1 y ordinate of first endpoint of segment 2
108    * @param bx2 x ordinate of second endpoint of segment 2
109    * @param by2 y ordinate of second endpoint of segment 2
110    * @return maximum distance between the segments
111    */
112   private static double maxDistance(double ax1, double ay1, double ax2, double ay2, 
113       double bx1, double by1, double bx2, double by2) {
114     double dist = distance(ax1, ay1, bx1, by1);
115     dist = Math.max(dist, distance(ax1, ay1, bx2, by2));
116     dist = Math.max(dist, distance(ax2, ay2, bx1, by1));
117     dist = Math.max(dist, distance(ax2, ay2, bx2, by2));
118     return dist;
119   }
120 }
121