You are viewing a plain text version of this content. The canonical link for it is here.
Posted to java-commits@lucene.apache.org by ry...@apache.org on 2009/01/07 18:10:59 UTC
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/
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;
/**