lucene-java-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From r...@apache.org
Subject svn commit: r732400 - in /lucene/java/trunk/contrib/spatial/src: java/org/apache/lucene/spatial/geohash/ java/org/apache/lucene/spatial/tier/ test/org/apache/lucene/spatial/tier/
Date Wed, 07 Jan 2009 17:10:59 GMT
Author: ryan
Date: Wed Jan  7 09:10:58 2009
New Revision: 732400

URL: http://svn.apache.org/viewvc?rev=732400&view=rev
Log:
LUCENE-1512 -- adding GeoHash implementaion

Added:
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geohash/
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geohash/GeoHashDistanceFilter.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geohash/GeoHashUtils.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/LatLongDistanceFilter.java
Modified:
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/DistanceFilter.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/DistanceQueryBuilder.java
    lucene/java/trunk/contrib/spatial/src/test/org/apache/lucene/spatial/tier/TestCartesian.java
    lucene/java/trunk/contrib/spatial/src/test/org/apache/lucene/spatial/tier/TestDistance.java

Added: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geohash/GeoHashDistanceFilter.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geohash/GeoHashDistanceFilter.java?rev=732400&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geohash/GeoHashDistanceFilter.java
(added)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geohash/GeoHashDistanceFilter.java
Wed Jan  7 09:10:58 2009
@@ -0,0 +1,246 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.geohash;
+
+import java.io.IOException;
+import java.util.BitSet;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.WeakHashMap;
+import java.util.logging.Logger;
+
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.search.FieldCache;
+
+import org.apache.lucene.spatial.tier.DistanceFilter;
+import org.apache.lucene.spatial.tier.DistanceUtils;
+import org.apache.lucene.spatial.tier.DistanceHandler.Precision;
+
+import org.apache.lucene.spatial.NumberUtils;
+
+
+
+public class GeoHashDistanceFilter extends DistanceFilter {
+
+  /**
+   * 
+   */
+  private static final long serialVersionUID = 1L;
+  
+  private double distance;
+  private double lat;
+  private double lng;
+  private String geoHashField;
+  
+  private Logger log = Logger.getLogger(getClass().getName());
+  
+  private Map<Integer,Double> distances = null;
+  private Precision precise = null;
+  
+  /**
+   * Provide a distance filter based from a center point with a radius
+   * in miles
+   * @param lat
+   * @param lng
+   * @param miles
+   * @param latField
+   * @param lngField
+   */
+  public GeoHashDistanceFilter(double lat, double lng, double miles, String geoHashField){
+    distance = miles;
+    this.lat = lat;
+    this.lng = lng;
+    this.geoHashField = geoHashField;
+    
+  }
+  
+  
+  public Map<Integer,Double> getDistances(){
+    return distances;
+  }
+  
+  public Double getDistance(int docid){
+    return distances.get(docid);
+  }
+  
+  @Override
+  public BitSet bits(IndexReader reader) throws IOException {
+
+    /* Create a BitSet to store the result */
+    int maxdocs = reader.numDocs();
+    BitSet bits = new BitSet(maxdocs);
+    
+    setPrecision(maxdocs);
+    // create an intermediate cache to avoid recomputing
+    //   distances for the same point 
+    //   TODO: Why is this a WeakHashMap? 
+    WeakHashMap<String,Double> cdistance = new WeakHashMap<String,Double>(maxdocs);
+    
+    String[] geoHashCache = FieldCache.DEFAULT.getStrings(reader, geoHashField);
+    
+
+    /* store calculated distances for reuse by other components */
+    distances = new HashMap<Integer,Double>(maxdocs);
+    for (int i = 0 ; i < maxdocs; i++) {
+      
+      String geoHash = geoHashCache[i];
+      double[] coords = GeoHashUtils.decode(geoHash);
+      double x = coords[0];
+      double y = coords[1];
+      
+      // round off lat / longs if necessary
+//      x = DistanceHandler.getPrecision(x, precise);
+//      y = DistanceHandler.getPrecision(y, precise);
+      
+      
+      Double cachedDistance = cdistance.get(geoHash);
+      
+      
+      double d;
+      
+      if(cachedDistance != null){
+        d = cachedDistance.doubleValue();
+      } else {
+        d = DistanceUtils.getInstance().getDistanceMi(lat, lng, x, y);
+        cdistance.put(geoHash, d);
+      }
+      distances.put(i, d);
+      
+      if (d < distance){
+        bits.set(i);
+      }
+      
+    }
+    
+    return bits;
+  }
+
+  
+  @Override
+  public BitSet bits(IndexReader reader, BitSet bits) throws Exception {
+
+  
+    /* Create a BitSet to store the result */
+    int size = bits.cardinality();
+    BitSet result = new BitSet(size);
+    
+
+    /* create an intermediate cache to avoid recomputing
+         distances for the same point  */
+    HashMap<String,Double> cdistance = new HashMap<String,Double>(size);
+    
+
+    /* store calculated distances for reuse by other components */
+    distances = new HashMap<Integer,Double>(size);
+    
+    long start = System.currentTimeMillis();
+    String[] geoHashCache = FieldCache.DEFAULT.getStrings(reader, geoHashField);
+ 
+    /* loop over all set bits (hits from the boundary box filters) */
+    int i = bits.nextSetBit(0);
+    while (i >= 0){
+      
+      // if we have a completed
+      // filter chain, lat / lngs can be retrived from 
+      // memory rather than document base.
+
+      String geoHash = geoHashCache[i];
+      double[] coords = GeoHashUtils.decode(geoHash);
+      double x = coords[0];
+      double y = coords[1];
+      
+      // round off lat / longs if necessary
+//      x = DistanceHandler.getPrecision(x, precise);
+//      y = DistanceHandler.getPrecision(y, precise);
+
+      
+      Double cachedDistance = cdistance.get(geoHash);
+      double d;
+      
+      if(cachedDistance != null){
+        d = cachedDistance.doubleValue();
+        
+      } else {
+        d = DistanceUtils.getInstance().getDistanceMi(lat, lng, x, y);
+        //d = DistanceUtils.getLLMDistance(lat, lng, x, y);
+        cdistance.put(geoHash, d);
+      }
+      
+      distances.put(i, d);
+        
+      if (d < distance){
+        result.set(i);
+      }
+      i = bits.nextSetBit(i+1);
+    }
+    
+    long end = System.currentTimeMillis();
+    log.fine("Time taken : "+ (end - start) + 
+        ", results : "+ distances.size() + 
+        ", cached : "+ cdistance.size() +
+        ", incoming size: "+ size);
+  
+
+    cdistance = null;
+    
+    return result;
+  }
+
+  /** Returns true if <code>o</code> is equal to this. */
+  @Override
+  public boolean equals(Object o) {
+    if (this == o) return true;
+    if (!(o instanceof GeoHashDistanceFilter)) return false;
+    GeoHashDistanceFilter other = (GeoHashDistanceFilter) o;
+
+    if (this.distance != other.distance ||
+        this.lat != other.lat ||
+        this.lng != other.lng ||
+        !this.geoHashField.equals(other.geoHashField) ) {
+      return false;
+    }
+    return true;
+  }
+
+  /** Returns a hash code value for this object.*/
+  @Override
+  public int hashCode() {
+    int h = new Double(distance).hashCode();
+    h ^= new Double(lat).hashCode();
+    h ^= new Double(lng).hashCode();
+    h ^= geoHashField.hashCode();
+    
+    return h;
+  }
+  
+  private void setPrecision(int maxDocs) {
+    precise = Precision.EXACT;
+    
+    if (maxDocs > 1000 && distance > 10) {
+      precise = Precision.TWENTYFEET;
+    }
+    
+    if (maxDocs > 10000 && distance > 10){
+      precise = Precision.TWOHUNDREDFEET;
+    }
+  }
+
+  public void setDistances(Map<Integer, Double> distances) {
+    this.distances = distances;
+  }
+}

Added: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geohash/GeoHashUtils.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geohash/GeoHashUtils.java?rev=732400&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geohash/GeoHashUtils.java
(added)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geohash/GeoHashUtils.java
Wed Jan  7 09:10:58 2009
@@ -0,0 +1,170 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.geohash;
+
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * Based on http://en.wikipedia.org/wiki/Geohash
+ */
+public class GeoHashUtils {
+
+	// geohash's char map
+	// no a's i's l's o's
+	// old MacDonal wouldn't be happy
+	private static char[] _base32 = {'0','1','2','3','4','5','6','7','8','9',
+							'b','c','d','e','f','g','h','j','k','m',
+							'n','p','q','r','s','t','u','v','w','x',
+							'y','z'} ;
+	
+	private final static Map<Character, Integer> _decodemap = new HashMap<Character,
Integer>();
+	static {
+		int sz = _base32.length;
+		for (int i = 0; i < sz; i++ ){
+			_decodemap.put(_base32[i], i);
+		}
+	}
+	
+	private static int precision = 12;
+	private static int[] bits = {16, 8, 4, 2, 1};
+	
+	public static void main(String[] args) {
+		GeoHashUtils ghf = new GeoHashUtils();
+		String gc1 = ghf.encode(30, -90.0);
+		String gc2 = ghf.encode(51.4797, -0.0124);
+		
+		System.out.println(gc1);
+		System.out.println(gc2);
+		
+		double [] gd1 = ghf.decode(gc1);
+		double [] gd2 = ghf.decode(gc2);
+		System.out.println(gd1[0]+ ", "+ gd1[1]);
+		System.out.println(gd2[0]+ ", "+ gd2[1]);
+		
+	}
+	
+	public static String encode(double latitude, double longitude){
+		double[] lat_interval = {-90.0 ,  90.0};
+		double[] lon_interval = {-180.0, 180.0};
+			
+		StringBuilder geohash = new StringBuilder();
+		boolean is_even = true;
+		int bit = 0, ch = 0;
+		
+		while(geohash.length() < precision){
+			double mid = 0.0;
+			if(is_even){
+				mid = (lon_interval[0] + lon_interval[1]) / 2;
+				if (longitude > mid){
+					ch |= bits[bit];
+					lon_interval[0] = mid;
+				} else {
+					lon_interval[1] = mid;
+				}
+				
+			} else {
+				mid = (lat_interval[0] + lat_interval[1]) / 2;
+				if(latitude > mid){
+					ch |= bits[bit];
+					lat_interval[0] = mid;
+				} else {
+					lat_interval[1] = mid;
+				}
+			}
+			
+			is_even = is_even ? false : true;
+			
+			if (bit  < 4){
+				bit ++;
+			} else {
+				geohash.append(_base32[ch]);
+				bit =0;
+				ch = 0;
+			}
+		}
+		
+		return geohash.toString();
+	}
+	
+	public static double[] decode(String geohash) {
+		double[] ge = decode_exactly(geohash);
+		double lat, lon, lat_err, lon_err;
+		lat = ge[0];
+		lon = ge[1];
+		lat_err = ge[2];
+		lon_err = ge[3];
+		
+		double lat_precision = Math.max(1, Math.round(- Math.log10(lat_err))) - 1;
+		double lon_precision = Math.max(1, Math.round(- Math.log10(lon_err))) - 1;
+		
+		lat = getPrecision(lat, lat_precision);
+		lon = getPrecision(lon, lon_precision);
+		
+		return new double[] {lat, lon};
+	}
+	
+	public static double[] decode_exactly (String geohash){
+		double[] lat_interval = {-90.0 , 90.0};
+		double[] lon_interval = {-180.0, 180.0};
+		
+		double lat_err =  90.0;
+		double lon_err = 180.0;
+		boolean is_even = true;
+		int sz = geohash.length();
+		int bsz = bits.length;
+		double latitude, longitude;
+		for (int i = 0; i < sz; i++){
+			
+			int cd = _decodemap.get(geohash.charAt(i));
+			
+			for (int z = 0; z< bsz; z++){
+				int mask = bits[z];
+				if (is_even){
+					lon_err /= 2;
+					if ((cd & mask) != 0){
+						lon_interval[0] = (lon_interval[0]+lon_interval[1])/2;
+					} else {
+						lon_interval[1] = (lon_interval[0]+lon_interval[1])/2;
+					}
+					
+				} else {
+					lat_err /=2;
+				
+					if ( (cd & mask) != 0){
+						lat_interval[0] = (lat_interval[0]+lat_interval[1])/2;
+					} else {
+						lat_interval[1] = (lat_interval[0]+lat_interval[1])/2;
+					}
+				}
+				is_even = is_even ? false : true;
+			}
+		
+		}
+		latitude  = (lat_interval[0] + lat_interval[1]) / 2;
+		longitude = (lon_interval[0] + lon_interval[1]) / 2;
+
+		return new double []{latitude, longitude, lat_err, lon_err};
+	}
+	
+	static double getPrecision(double x, double precision) {
+		double base = Math.pow(10,- precision);
+		double diff = x % base;
+		return x - diff;
+	}
+}

Modified: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/DistanceFilter.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/DistanceFilter.java?rev=732400&r1=732399&r2=732400&view=diff
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/DistanceFilter.java
(original)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/DistanceFilter.java
Wed Jan  7 09:10:58 2009
@@ -1,5 +1,4 @@
-/**
- * Licensed to the Apache Software Foundation (ASF) under one or more
+/** Licensed to the Apache Software Foundation (ASF) under one or more
  * contributor license agreements.  See the NOTICE file distributed with
  * this work for additional information regarding copyright ownership.
  * The ASF licenses this file to You under the Apache License, Version 2.0
@@ -19,230 +18,36 @@
 
 import java.io.IOException;
 import java.util.BitSet;
-import java.util.HashMap;
 import java.util.Map;
-import java.util.WeakHashMap;
-import java.util.logging.Logger;
 
 import org.apache.lucene.index.IndexReader;
-import org.apache.lucene.search.FieldCache;
 import org.apache.lucene.spatial.ISerialChainFilter;
-import org.apache.lucene.spatial.tier.DistanceHandler.Precision;
 
-import org.apache.lucene.spatial.NumberUtils;
 
+public abstract class DistanceFilter extends ISerialChainFilter {
 
+	public DistanceFilter() {
+		super();
+	}
 
-public class DistanceFilter extends ISerialChainFilter {
+	public abstract Map<Integer,Double> getDistances();
 
-  /**
-   * 
-   */
-  private static final long serialVersionUID = 1L;
-  
-  private double distance;
-  private double lat;
-  private double lng;
-  private String latField;
-  private String lngField;
-  private Logger log = Logger.getLogger(getClass().getName());
-  
-  private Map<Integer,Double> distances = null;
-  private Precision precise = null;
-  
-  /**
-   * Provide a distance filter based from a center point with a radius
-   * in miles
-   * @param lat
-   * @param lng
-   * @param miles
-   * @param latField
-   * @param lngField
-   */
-  public DistanceFilter(double lat, double lng, double miles, String latField, String lngField){
-    distance = miles;
-    this.lat = lat;
-    this.lng = lng;
-    this.latField = latField;
-    this.lngField = lngField;
-  }
-  
-  
-  public Map<Integer,Double> getDistances(){
-    return distances;
-  }
-  
-  public Double getDistance(int docid){
-    return distances.get(docid);
-  }
-  
-  @Override
-  public BitSet bits(IndexReader reader) throws IOException {
-
-    /* Create a BitSet to store the result */
-    int maxdocs = reader.numDocs();
-    BitSet bits = new BitSet(maxdocs);
-    
-    setPrecision(maxdocs);
-    // create an intermediate cache to avoid recomputing
-    //   distances for the same point 
-    //   TODO: Why is this a WeakHashMap? 
-    WeakHashMap<String,Double> cdistance = new WeakHashMap<String,Double>(maxdocs);
-    
-    String[] latIndex = FieldCache.DEFAULT.getStrings(reader, latField);
-    String[] lngIndex = FieldCache.DEFAULT.getStrings(reader, lngField);
-
-    /* store calculated distances for reuse by other components */
-    distances = new HashMap<Integer,Double>(maxdocs);
-    for (int i = 0 ; i < maxdocs; i++) {
-      
-      String sx = latIndex[i];
-      String sy = lngIndex[i];
-  
-      double x = NumberUtils.SortableStr2double(sx);
-      double y = NumberUtils.SortableStr2double(sy);
-      
-      // round off lat / longs if necessary
-//      x = DistanceHandler.getPrecision(x, precise);
-//      y = DistanceHandler.getPrecision(y, precise);
-      
-      String ck = new Double(x).toString()+","+new Double(y).toString();
-      Double cachedDistance = cdistance.get(ck);
-      
-      
-      double d;
-      
-      if(cachedDistance != null){
-        d = cachedDistance.doubleValue();
-      } else {
-        d = DistanceUtils.getInstance().getDistanceMi(lat, lng, x, y);
-        cdistance.put(ck, d);
-      }
-      distances.put(i, d);
-      
-      if (d < distance){
-        bits.set(i);
-      }
-      
-    }
-    
-    return bits;
-  }
-
-  
-  @Override
-  public BitSet bits(IndexReader reader, BitSet bits) throws Exception {
-
-  
-    /* Create a BitSet to store the result */
-    int size = bits.cardinality();
-    BitSet result = new BitSet(size);
-    
-
-    /* create an intermediate cache to avoid recomputing
-         distances for the same point  */
-    HashMap<String,Double> cdistance = new HashMap<String,Double>(size);
-    
-
-    /* store calculated distances for reuse by other components */
-    distances = new HashMap<Integer,Double>(size);
-    
-    long start = System.currentTimeMillis();
-    String[] latIndex = FieldCache.DEFAULT.getStrings(reader, latField);
-    String[] lngIndex = FieldCache.DEFAULT.getStrings(reader, lngField);
-    
-    /* loop over all set bits (hits from the boundary box filters) */
-    int i = bits.nextSetBit(0);
-    while (i >= 0){
-      double x,y;
-      
-      // if we have a completed
-      // filter chain, lat / lngs can be retrived from 
-      // memory rather than document base.
-
-      String sx = latIndex[i];
-      String sy = lngIndex[i];
-      x = NumberUtils.SortableStr2double(sx);
-      y = NumberUtils.SortableStr2double(sy);
-      
-      // round off lat / longs if necessary
-//      x = DistanceHandler.getPrecision(x, precise);
-//      y = DistanceHandler.getPrecision(y, precise);
-
-      String ck = new Double(x).toString()+","+new Double(y).toString();
-      Double cachedDistance = cdistance.get(ck);
-      double d;
-      
-      if(cachedDistance != null){
-        d = cachedDistance.doubleValue();
-        
-      } else {
-        d = DistanceUtils.getInstance().getDistanceMi(lat, lng, x, y);
-        //d = DistanceUtils.getLLMDistance(lat, lng, x, y);
-        cdistance.put(ck, d);
-      }
-      
-      distances.put(i, d);
-        
-      if (d < distance){
-        result.set(i);
-      }
-      i = bits.nextSetBit(i+1);
-    }
-    
-    long end = System.currentTimeMillis();
-    log.fine("Time taken : "+ (end - start) + 
-        ", results : "+ distances.size() + 
-        ", cached : "+ cdistance.size() +
-        ", incoming size: "+ size);
-  
-
-    cdistance = null;
-    
-    return result;
-  }
-
-  /** Returns true if <code>o</code> is equal to this. */
-  @Override
-  public boolean equals(Object o) {
-    if (this == o) return true;
-    if (!(o instanceof DistanceFilter)) return false;
-    DistanceFilter other = (DistanceFilter) o;
-
-    if (this.distance != other.distance ||
-        this.lat != other.lat ||
-        this.lng != other.lng ||
-        !this.latField.equals(other.latField) ||
-        !this.lngField.equals(other.lngField)) {
-      return false;
-    }
-    return true;
-  }
-
-  /** Returns a hash code value for this object.*/
-  @Override
-  public int hashCode() {
-    int h = new Double(distance).hashCode();
-    h ^= new Double(lat).hashCode();
-    h ^= new Double(lng).hashCode();
-    h ^= latField.hashCode();
-    h ^= lngField.hashCode();
-    return h;
-  }
-  
-  private void setPrecision(int maxDocs) {
-    precise = Precision.EXACT;
-    
-    if (maxDocs > 1000 && distance > 10) {
-      precise = Precision.TWENTYFEET;
-    }
-    
-    if (maxDocs > 10000 && distance > 10){
-      precise = Precision.TWOHUNDREDFEET;
-    }
-  }
-
-  public void setDistances(Map<Integer, Double> distances) {
-    this.distances = distances;
-  }
-}
+	public abstract Double getDistance(int docid);
+
+	@Override
+	public abstract BitSet bits(IndexReader reader) throws IOException;
+
+	@Override
+	public abstract BitSet bits(IndexReader reader, BitSet bits) throws Exception;
+
+	/** Returns true if <code>o</code> is equal to this. */
+	@Override
+	public abstract boolean equals(Object o);
+
+	/** Returns a hash code value for this object.*/
+	@Override
+	public abstract int hashCode();
+
+	public abstract void setDistances(Map<Integer, Double> distances);
+
+}
\ No newline at end of file

Modified: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/DistanceQueryBuilder.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/DistanceQueryBuilder.java?rev=732400&r1=732399&r2=732400&view=diff
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/DistanceQueryBuilder.java
(original)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/DistanceQueryBuilder.java
Wed Jan  7 09:10:58 2009
@@ -19,9 +19,11 @@
 
 import org.apache.lucene.search.ConstantScoreQuery;
 import org.apache.lucene.search.Filter;
+import org.apache.lucene.spatial.ISerialChainFilter;
 import org.apache.lucene.search.Query;
 import org.apache.lucene.search.QueryWrapperFilter;
 import org.apache.lucene.spatial.SerialChainFilter;
+import org.apache.lucene.spatial.geohash.GeoHashDistanceFilter;
 
 
 public class DistanceQueryBuilder {
@@ -48,7 +50,7 @@
    * @param miles
    */
   public DistanceQueryBuilder (double lat, double lng, double miles, 
-      String latField, String lngField, String tierFieldPrefix, boolean needPrecise){
+      String latField, String lngField, String tierFieldPrefix,boolean needPrecise){
 
     this.lat = lat;
     this.lng = lng;
@@ -60,10 +62,38 @@
 
     /* create precise distance filter */
     if( needPrecise)
-    	distanceFilter = new DistanceFilter(lat, lng, miles, latField, lngField);
+    	distanceFilter = new LatLongDistanceFilter(lat, lng, miles, latField, lngField);
     
   }
 
+  /**
+   * Create a distance query using
+   * a boundary box wrapper around a more precise
+   * DistanceFilter.
+   * 
+   * @see SerialChainFilter
+   * @param lat
+   * @param lng
+   * @param miles
+   */
+  public DistanceQueryBuilder (double lat, double lng, double miles, 
+      String geoHashFieldPrefix, String tierFieldPrefix,boolean needPrecise){
+
+    this.lat = lat;
+    this.lng = lng;
+    this.miles = miles;
+    
+    
+    CartesianPolyFilterBuilder cpf = new CartesianPolyFilterBuilder(tierFieldPrefix);
+    cartesianFilter = cpf.getBoundingArea(lat, lng, (int)miles);
+
+    /* create precise distance filter */
+    if( needPrecise)
+    	distanceFilter = new GeoHashDistanceFilter(lat, lng, miles, geoHashFieldPrefix);
+    
+  }
+
+  
    /**
   * Create a distance query using
   * a boundary box wrapper around a more precise

Added: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/LatLongDistanceFilter.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/LatLongDistanceFilter.java?rev=732400&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/LatLongDistanceFilter.java
(added)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/LatLongDistanceFilter.java
Wed Jan  7 09:10:58 2009
@@ -0,0 +1,249 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.tier;
+
+import java.io.IOException;
+import java.util.BitSet;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.WeakHashMap;
+import java.util.logging.Logger;
+
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.search.FieldCache;
+import org.apache.lucene.spatial.NumberUtils;
+import org.apache.lucene.spatial.tier.DistanceHandler.Precision;
+
+
+
+
+public class LatLongDistanceFilter extends DistanceFilter {
+
+  /**
+   * 
+   */
+  private static final long serialVersionUID = 1L;
+  
+  double distance;
+  double lat;
+  double lng;
+  String latField;
+  String lngField;
+  Logger log = Logger.getLogger(getClass().getName());
+  
+  Map<Integer,Double> distances = null;
+  private Precision precise = null;
+  
+  /**
+   * Provide a distance filter based from a center point with a radius
+   * in miles
+   * @param lat
+   * @param lng
+   * @param miles
+   * @param latField
+   * @param lngField
+   */
+  public LatLongDistanceFilter(double lat, double lng, double miles, String latField, String
lngField){
+    distance = miles;
+    this.lat = lat;
+    this.lng = lng;
+    this.latField = latField;
+    this.lngField = lngField;
+  }
+  
+  
+  public Map<Integer,Double> getDistances(){
+    return distances;
+  }
+  
+  public Double getDistance(int docid){
+    return distances.get(docid);
+  }
+  
+  @Override
+  public BitSet bits(IndexReader reader) throws IOException {
+
+    /* Create a BitSet to store the result */
+    int maxdocs = reader.numDocs();
+    BitSet bits = new BitSet(maxdocs);
+    
+    setPrecision(maxdocs);
+    // create an intermediate cache to avoid recomputing
+    //   distances for the same point 
+    //   TODO: Why is this a WeakHashMap? 
+    WeakHashMap<String,Double> cdistance = new WeakHashMap<String,Double>(maxdocs);
+    
+    String[] latIndex = FieldCache.DEFAULT.getStrings(reader, latField);
+    String[] lngIndex = FieldCache.DEFAULT.getStrings(reader, lngField);
+
+    /* store calculated distances for reuse by other components */
+    distances = new HashMap<Integer,Double>(maxdocs);
+    for (int i = 0 ; i < maxdocs; i++) {
+      
+      String sx = latIndex[i];
+      String sy = lngIndex[i];
+  
+      double x = NumberUtils.SortableStr2double(sx);
+      double y = NumberUtils.SortableStr2double(sy);
+      
+      // round off lat / longs if necessary
+//      x = DistanceHandler.getPrecision(x, precise);
+//      y = DistanceHandler.getPrecision(y, precise);
+      
+      String ck = new Double(x).toString()+","+new Double(y).toString();
+      Double cachedDistance = cdistance.get(ck);
+      
+      
+      double d;
+      
+      if(cachedDistance != null){
+        d = cachedDistance.doubleValue();
+      } else {
+        d = DistanceUtils.getInstance().getDistanceMi(lat, lng, x, y);
+        cdistance.put(ck, d);
+      }
+      distances.put(i, d);
+      
+      if (d < distance){
+        bits.set(i);
+      }
+      
+    }
+    
+    return bits;
+  }
+
+  
+  @Override
+  public BitSet bits(IndexReader reader, BitSet bits) throws Exception {
+
+  
+    /* Create a BitSet to store the result */
+    int size = bits.cardinality();
+    BitSet result = new BitSet(size);
+    
+
+    /* create an intermediate cache to avoid recomputing
+         distances for the same point  */
+    HashMap<String,Double> cdistance = new HashMap<String,Double>(size);
+    
+
+    /* store calculated distances for reuse by other components */
+    distances = new HashMap<Integer,Double>(size);
+    
+    long start = System.currentTimeMillis();
+    String[] latIndex = FieldCache.DEFAULT.getStrings(reader, latField);
+    String[] lngIndex = FieldCache.DEFAULT.getStrings(reader, lngField);
+    
+    /* loop over all set bits (hits from the boundary box filters) */
+    int i = bits.nextSetBit(0);
+    while (i >= 0){
+      double x,y;
+      
+      // if we have a completed
+      // filter chain, lat / lngs can be retrived from 
+      // memory rather than document base.
+
+      String sx = latIndex[i];
+      String sy = lngIndex[i];
+      x = NumberUtils.SortableStr2double(sx);
+      y = NumberUtils.SortableStr2double(sy);
+      
+      // round off lat / longs if necessary
+//      x = DistanceHandler.getPrecision(x, precise);
+//      y = DistanceHandler.getPrecision(y, precise);
+
+      String ck = new Double(x).toString()+","+new Double(y).toString();
+      Double cachedDistance = cdistance.get(ck);
+      double d;
+      
+      if(cachedDistance != null){
+        d = cachedDistance.doubleValue();
+        
+      } else {
+        d = DistanceUtils.getInstance().getDistanceMi(lat, lng, x, y);
+        //d = DistanceUtils.getLLMDistance(lat, lng, x, y);
+        cdistance.put(ck, d);
+      }
+      
+      distances.put(i, d);
+        
+      if (d < distance){
+        result.set(i);
+      }
+      i = bits.nextSetBit(i+1);
+    }
+    
+    long end = System.currentTimeMillis();
+    log.fine("Time taken : "+ (end - start) + 
+        ", results : "+ distances.size() + 
+        ", cached : "+ cdistance.size() +
+        ", incoming size: "+ size);
+  
+
+    cdistance = null;
+    
+    return result;
+  }
+
+  /** Returns true if <code>o</code> is equal to this. */
+  @Override
+  public boolean equals(Object o) {
+    if (this == o) return true;
+    if (!(o instanceof LatLongDistanceFilter)) return false;
+    LatLongDistanceFilter other = (LatLongDistanceFilter) o;
+
+    if (this.distance != other.distance ||
+        this.lat != other.lat ||
+        this.lng != other.lng ||
+        !this.latField.equals(other.latField) ||
+        !this.lngField.equals(other.lngField)) {
+      return false;
+    }
+    return true;
+  }
+
+  /** Returns a hash code value for this object.*/
+  @Override
+  public int hashCode() {
+    int h = new Double(distance).hashCode();
+    h ^= new Double(lat).hashCode();
+    h ^= new Double(lng).hashCode();
+    h ^= latField.hashCode();
+    h ^= lngField.hashCode();
+    return h;
+  }
+  
+
+
+  public void setDistances(Map<Integer, Double> distances) {
+    this.distances = distances;
+  }
+
+  void setPrecision(int maxDocs) {
+    precise = Precision.EXACT;
+    
+    if (maxDocs > 1000 && distance > 10) {
+      precise = Precision.TWENTYFEET;
+    }
+    
+    if (maxDocs > 10000 && distance > 10){
+      precise = Precision.TWOHUNDREDFEET;
+    }
+  }
+}

Modified: lucene/java/trunk/contrib/spatial/src/test/org/apache/lucene/spatial/tier/TestCartesian.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/test/org/apache/lucene/spatial/tier/TestCartesian.java?rev=732400&r1=732399&r2=732400&view=diff
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/test/org/apache/lucene/spatial/tier/TestCartesian.java
(original)
+++ lucene/java/trunk/contrib/spatial/src/test/org/apache/lucene/spatial/tier/TestCartesian.java
Wed Jan  7 09:10:58 2009
@@ -35,6 +35,7 @@
 import org.apache.lucene.search.Sort;
 import org.apache.lucene.search.SortField;
 import org.apache.lucene.search.TermQuery;
+import org.apache.lucene.spatial.geohash.GeoHashUtils;
 import org.apache.lucene.spatial.tier.DistanceQueryBuilder;
 import org.apache.lucene.spatial.tier.DistanceSortSource;
 import org.apache.lucene.spatial.tier.DistanceUtils;
@@ -67,12 +68,12 @@
   private String latField = "lat";
   private String lngField = "lng";
   private List<CartesianTierPlotter> ctps = new LinkedList<CartesianTierPlotter>();
+  private String geoHashPrefix = "_geoHash_";
   
   private IProjector project = new SinusoidalProjector();
   
 
 
-  @Override
   protected void setUp() throws IOException {
     directory = new RAMDirectory();
 
@@ -113,6 +114,10 @@
           NumberUtils.double2sortableStr(ctp.getTierBoxId(lat,lng)),
           Field.Store.YES, 
           Field.Index.NO_NORMS));
+      
+      doc.add(new Field(geoHashPrefix, GeoHashUtils.encode(lat,lng), 
+    		  Field.Store.YES, 
+    		  Field.Index.NO_NORMS));
     }
     writer.addDocument(doc);
     
@@ -223,4 +228,86 @@
     }
   }
   
+  
+  
+  public void testGeoHashRange() throws IOException, InvalidGeoException {
+	    searcher = new IndexSearcher(directory);
+	    
+	    final double miles = 6.0;
+	    
+	    // create a distance query
+	    final DistanceQueryBuilder dq = new DistanceQueryBuilder(lat, lng, miles, 
+	        geoHashPrefix, CartesianTierPlotter.DEFALT_FIELD_PREFIX, true);
+	     
+	    System.out.println(dq);
+	    //create a term query to search against all documents
+	    Query tq = new TermQuery(new Term("metafile", "doc"));
+	    
+	    FieldScoreQuery fsQuery = new FieldScoreQuery("geo_distance", Type.FLOAT);
+	    CustomScoreQuery customScore = new CustomScoreQuery(tq,fsQuery){
+	      
+	      @Override
+	      public float customScore(int doc, float subQueryScore, float valSrcScore){
+	        //System.out.println(doc);
+	        if (dq.distanceFilter.getDistance(doc) == null)
+	          return 0;
+	        
+	        double distance = dq.distanceFilter.getDistance(doc);
+	        // boost score shouldn't exceed 1
+	        if (distance < 1.0d)
+	          distance = 1.0d;
+	        //boost by distance is invertly proportional to
+	        // to distance from center point to location
+	        float score = new Float((miles - distance) / miles ).floatValue();
+	        return score * subQueryScore;
+	      }
+	    };
+	    // Create a distance sort
+	    // As the radius filter has performed the distance calculations
+	    // already, pass in the filter to reuse the results.
+	    // 
+	    DistanceSortSource dsort = new DistanceSortSource(dq.distanceFilter);
+	    Sort sort = new Sort(new SortField("foo", dsort));
+	    
+	    // Perform the search, using the term query, the serial chain filter, and the
+	    // distance sort
+	    Hits hits = searcher.search(customScore, dq.getFilter()); //,sort);
+
+	    int results = hits.length();
+	    
+	    // Get a list of distances 
+	    Map<Integer,Double> distances = dq.distanceFilter.getDistances();
+	    
+	    // distances calculated from filter first pass must be less than total
+	    // docs, from the above test of 20 items, 12 will come from the boundary box
+	    // filter, but only 5 are actually in the radius of the results.
+	    
+	    // Note Boundary Box filtering, is not accurate enough for most systems.
+	    
+	    
+	    System.out.println("Distance Filter filtered: " + distances.size());
+	    System.out.println("Results: " + results);
+	    System.out.println("=============================");
+	    System.out.println("Distances should be 14 "+ distances.size());
+	    System.out.println("Results should be 7 "+ results);
+
+	    assertEquals(14, distances.size());
+	    assertEquals(7, results);
+	    
+	    for(int i =0 ; i < results; i++){
+	      Document d = hits.doc(i);
+	      
+	      String name = d.get("name");
+	      double rsLat = NumberUtils.SortableStr2double(d.get(latField));
+	      double rsLng = NumberUtils.SortableStr2double(d.get(lngField)); 
+	      Double geo_distance = distances.get(hits.id(i));
+	      
+	      double distance = DistanceUtils.getInstance().getDistanceMi(lat, lng, rsLat, rsLng);
+	      double llm = DistanceUtils.getInstance().getLLMDistance(lat, lng, rsLat, rsLng);
+	      System.out.println("Name: "+ name +", Distance (res, ortho, harvesine):"+ distance
+" |"+ geo_distance +"|"+ llm +" | score "+ hits.score(i));
+	      assertTrue(Math.abs((distance - llm)) < 1);
+	      assertTrue((distance < miles ));
+	    }
+	  }
+  
 }

Modified: lucene/java/trunk/contrib/spatial/src/test/org/apache/lucene/spatial/tier/TestDistance.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/test/org/apache/lucene/spatial/tier/TestDistance.java?rev=732400&r1=732399&r2=732400&view=diff
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/test/org/apache/lucene/spatial/tier/TestDistance.java
(original)
+++ lucene/java/trunk/contrib/spatial/src/test/org/apache/lucene/spatial/tier/TestDistance.java
Wed Jan  7 09:10:58 2009
@@ -17,7 +17,6 @@
 package org.apache.lucene.spatial.tier;
 
 import java.io.IOException;
-import java.util.Map;
 
 import junit.framework.TestCase;
 
@@ -25,19 +24,9 @@
 import org.apache.lucene.document.Document;
 import org.apache.lucene.document.Field;
 import org.apache.lucene.index.IndexWriter;
-import org.apache.lucene.index.Term;
-import org.apache.lucene.search.Hits;
 import org.apache.lucene.search.IndexSearcher;
-import org.apache.lucene.search.Query;
-import org.apache.lucene.search.Sort;
-import org.apache.lucene.search.SortField;
-import org.apache.lucene.search.TermQuery;
-import org.apache.lucene.spatial.tier.DistanceQueryBuilder;
-import org.apache.lucene.spatial.tier.DistanceSortSource;
-import org.apache.lucene.spatial.tier.DistanceUtils;
-import org.apache.lucene.spatial.tier.InvalidGeoException;
-import org.apache.lucene.store.RAMDirectory;
 import org.apache.lucene.spatial.NumberUtils;
+import org.apache.lucene.store.RAMDirectory;
 
 
 /**



Mime
View raw message