1 /* 2 * This file is part of ELKI: 3 * Environment for Developing KDD-Applications Supported by Index-Structures 4 * 5 * Copyright (C) 2018 6 * ELKI Development Team 7 * 8 * This program is free software: you can redistribute it and/or modify 9 * it under the terms of the GNU Affero General Public License as published by 10 * the Free Software Foundation, either version 3 of the License, or 11 * (at your option) any later version. 12 * 13 * This program is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 * GNU Affero General Public License for more details. 17 * 18 * You should have received a copy of the GNU Affero General Public License 19 * along with this program. If not, see <http://www.gnu.org/licenses/>. 20 */ 21 package de.lmu.ifi.dbs.elki.distance.distancefunction.geo; 22 23 import de.lmu.ifi.dbs.elki.data.NumberVector; 24 import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; 25 import de.lmu.ifi.dbs.elki.data.type.SimpleTypeInformation; 26 import de.lmu.ifi.dbs.elki.distance.distancefunction.NumberVectorDistanceFunction; 27 import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction; 28 import de.lmu.ifi.dbs.elki.math.geodesy.EarthModel; 29 import de.lmu.ifi.dbs.elki.math.geodesy.SphericalVincentyEarthModel; 30 import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; 31 import de.lmu.ifi.dbs.elki.utilities.exceptions.NotImplementedException; 32 import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; 33 import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; 34 import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter; 35 36 /** 37 * Distance function for 2D vectors in Longitude, Latitude form. 38 * <p> 39 * The input data must be in degrees (not radians), and the output distance will 40 * be in meters (see {@link EarthModel#distanceDeg}). 41 * <p> 42 * This implementation allows index accelerated queries using R*-trees (by 43 * providing a point-to-rectangle minimum distance). 44 * <p> 45 * Reference: 46 * <p> 47 * Erich Schubert, Arthur Zimek, Hans-Peter Kriegel<br> 48 * Geodetic Distance Queries on R-Trees for Indexing Geographic Data<br> 49 * Int. Symp. Advances in Spatial and Temporal Databases (SSTD'2013) 50 * 51 * @author Erich Schubert 52 * @since 0.4.0 53 * 54 * @composed - - - EarthModel 55 */ 56 @Reference(authors = "Erich Schubert, Arthur Zimek, Hans-Peter Kriegel", // 57 title = "Geodetic Distance Queries on R-Trees for Indexing Geographic Data", // 58 booktitle = "Int. Symp. Advances in Spatial and Temporal Databases (SSTD'2013)", // 59 url = "https://doi.org/10.1007/978-3-642-40235-7_9", // 60 bibkey = "DBLP:conf/ssd/SchubertZK13") 61 public class LngLatDistanceFunction implements SpatialPrimitiveDistanceFunction<NumberVector>, NumberVectorDistanceFunction<NumberVector> { 62 /** 63 * Earth model to use. 64 */ 65 private EarthModel model; 66 67 /** 68 * Constructor. 69 */ LngLatDistanceFunction(EarthModel model)70 public LngLatDistanceFunction(EarthModel model) { 71 super(); 72 this.model = model; 73 } 74 75 @Override distance(NumberVector o1, NumberVector o2)76 public double distance(NumberVector o1, NumberVector o2) { 77 return model.distanceDeg(o1.doubleValue(1), o1.doubleValue(0), o2.doubleValue(1), o2.doubleValue(0)); 78 } 79 80 @Override minDist(SpatialComparable mbr1, SpatialComparable mbr2)81 public double minDist(SpatialComparable mbr1, SpatialComparable mbr2) { 82 if(mbr1 instanceof NumberVector) { 83 if(mbr2 instanceof NumberVector) { 84 return distance((NumberVector) mbr1, (NumberVector) mbr2); 85 } 86 else { 87 NumberVector o1 = (NumberVector) mbr1; 88 return model.minDistDeg(o1.doubleValue(1), o1.doubleValue(0), mbr2.getMin(1), mbr2.getMin(0), mbr2.getMax(1), mbr2.getMax(0)); 89 } 90 } 91 else { 92 if(mbr2 instanceof NumberVector) { 93 NumberVector o2 = (NumberVector) mbr2; 94 return model.minDistDeg(o2.doubleValue(1), o2.doubleValue(0), mbr1.getMin(1), mbr1.getMin(0), mbr1.getMax(1), mbr1.getMax(0)); 95 } 96 else { 97 throw new NotImplementedException("This distance function cannot - yet - be used with this algorithm, as the lower bound rectangle to rectangle distances have not yet been formalized for geodetic data."); 98 } 99 } 100 } 101 102 @Override getInputTypeRestriction()103 public SimpleTypeInformation<? super NumberVector> getInputTypeRestriction() { 104 return NumberVector.FIELD_2D; 105 } 106 107 @Override isMetric()108 public boolean isMetric() { 109 return true; 110 } 111 112 @Override hashCode()113 public int hashCode() { 114 return model.hashCode() + getClass().hashCode(); 115 } 116 117 @Override equals(Object obj)118 public boolean equals(Object obj) { 119 return (this == obj) || (obj != null && obj instanceof LngLatDistanceFunction && // 120 this.model.equals(((LngLatDistanceFunction) obj).model)); 121 } 122 123 @Override toString()124 public String toString() { 125 return "LngLatDistanceFunction [model=" + model + "]"; 126 } 127 128 /** 129 * Parameterization class. 130 * 131 * @author Erich Schubert 132 */ 133 public static class Parameterizer extends AbstractParameterizer { 134 /** 135 * Earth model used. 136 */ 137 EarthModel model; 138 139 @Override makeOptions(Parameterization config)140 protected void makeOptions(Parameterization config) { 141 super.makeOptions(config); 142 ObjectParameter<EarthModel> modelP = new ObjectParameter<>(EarthModel.MODEL_ID, EarthModel.class, SphericalVincentyEarthModel.class); 143 if(config.grab(modelP)) { 144 model = modelP.instantiateClass(config); 145 } 146 } 147 148 @Override makeInstance()149 protected LngLatDistanceFunction makeInstance() { 150 return new LngLatDistanceFunction(model); 151 } 152 } 153 } 154