lucene-java-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From mikemcc...@apache.org
Subject svn commit: r817456 - in /lucene/java/trunk/contrib: ./ spatial/src/java/org/apache/lucene/spatial/geometry/shape/ spatial/src/java/org/apache/lucene/spatial/tier/ spatial/src/test/org/apache/lucene/spatial/tier/
Date Tue, 22 Sep 2009 00:08:21 GMT
Author: mikemccand
Date: Tue Sep 22 00:08:21 2009
New Revision: 817456

URL: http://svn.apache.org/viewvc?rev=817456&view=rev
Log:
LUCENE-1781: fix various issues with lat/lng bounding box computation for contrib/spatial

Modified:
    lucene/java/trunk/contrib/CHANGES.txt
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/DistanceApproximation.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/LLRect.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/CartesianPolyFilterBuilder.java
    lucene/java/trunk/contrib/spatial/src/test/org/apache/lucene/spatial/tier/TestCartesian.java

Modified: lucene/java/trunk/contrib/CHANGES.txt
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/CHANGES.txt?rev=817456&r1=817455&r2=817456&view=diff
==============================================================================
--- lucene/java/trunk/contrib/CHANGES.txt (original)
+++ lucene/java/trunk/contrib/CHANGES.txt Tue Sep 22 00:08:21 2009
@@ -90,6 +90,10 @@
  * LUCENE-1912: Fix fast-vector-highlighter issue when two or more
    terms are concatenated (Koji Sekiguchi via Mike McCandless)
 
+ * LUCENE-1781: Fixed various issues with the lat/lng bounding box
+   distance filter created for radius search in contrib/spatial.
+   (Bill Bell via Mike McCandless)
+
 New features
 
  * LUCENE-1531: Added support for BoostingTermQuery to XML query parser. (Karl Wettin)

Modified: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/DistanceApproximation.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/DistanceApproximation.java?rev=817456&r1=817455&r2=817456&view=diff
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/DistanceApproximation.java
(original)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/DistanceApproximation.java
Tue Sep 22 00:08:21 2009
@@ -23,6 +23,9 @@
  * <p><font color="red"><b>NOTE:</b> This API is still in
  * flux and might change in incompatible ways in the next
  * release.</font>
+ *
+ * @deprecated This has been replaced with more accurate
+ * math in {@link LLRect}.
  */
 public class DistanceApproximation
 {

Modified: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/LLRect.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/LLRect.java?rev=817456&r1=817455&r2=817456&view=diff
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/LLRect.java
(original)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/LLRect.java
Tue Sep 22 00:08:21 2009
@@ -74,16 +74,13 @@
    * @param heightMi
    */
   public static LLRect createBox(LatLng center, double widthMi, double heightMi) {
-    double miplatdeg=DistanceApproximation.getMilesPerLngDeg(center.getLat());
-    double miplngdeg=DistanceApproximation.getMilesPerLatDeg();
-    
-    double lngDelta=(widthMi/2)/miplngdeg;
-    double latDelta=(heightMi/2)/miplatdeg;
-    
-    // TODO: Prob only works in northern hemisphere?
-    LatLng ll=new FloatLatLng(center.getLat()-latDelta, center.getLng()-lngDelta);
-    LatLng ur=new FloatLatLng(center.getLat()+latDelta, center.getLng()+lngDelta);
-    
+    double d = widthMi;
+    LatLng ur = boxCorners(center, d, 45.0); // assume right angles
+    LatLng ll = boxCorners(center, d, 225.0);
+
+    //System.err.println("boxCorners: ur " + ur.getLat() + ',' + ur.getLng());
+    //System.err.println("boxCorners: cnt " + center.getLat() + ',' + center.getLng());
+    //System.err.println("boxCorners: ll " + ll.getLat() + ',' + ll.getLng());
     return new LLRect(ll, ur);
   }
   
@@ -94,6 +91,71 @@
     return new Rectangle(ll.getLng(), ll.getLat(), ur.getLng(), ur.getLat());
   }
 
+  private static LatLng boxCorners(LatLng center, double d, double brngdeg) {
+    double a = center.getLat();
+    double b = center.getLng();
+    double R = 3963.0; // radius of earth in miles
+    double brng = (Math.PI*brngdeg/180);
+    double lat1 = (Math.PI*a/180);
+    double lon1 = (Math.PI*b/180);
+
+    // Haversine formula
+    double lat2 = Math.asin( Math.sin(lat1)*Math.cos(d/R) +
+                             Math.cos(lat1)*Math.sin(d/R)*Math.cos(brng) );
+    double lon2 = lon1 + Math.atan2(Math.sin(brng)*Math.sin(d/R)*Math.cos(lat1),
+                                    Math.cos(d/R)-Math.sin(lat1)*Math.sin(lat2));
+
+    lat2 = (lat2*180)/Math.PI;
+    lon2 = (lon2*180)/Math.PI;
+
+    // normalize long first
+    LatLng ll = normLng(lat2,lon2);
+
+    // normalize lat - could flip poles
+    ll = normLat(ll.getLat(),ll.getLng());
+
+    return ll;
+}
+
+  /**
+   * Returns a normalized Lat rectangle shape for the bounding box
+   * If you go over the poles, you need to flip the lng value too
+   */
+  private static LatLng normLat(double lat, double lng) {
+    if (lat > 90.0) {
+        lat = 90.0 - (lat - 90.0);
+        if (lng < 0) {
+                lng = lng+180;
+        } else {
+                lng=lng-180;
+        }
+    }
+    else if (lat < -90.0) {
+        lat = -90.0 - (lat + 90.0);
+        if (lng < 0) {
+                lng = lng+180;
+        } else {
+                lng=lng-180;
+        }
+    }
+    LatLng ll=new FloatLatLng(lat, lng);
+    return ll;
+  }
+
+  /**
+   * Returns a normalized Lng rectangle shape for the bounding box
+   */
+  private static LatLng normLng(double lat,double lng) {
+    if (lng > 180.0) {
+        lng = -1.0*(180.0 - (lng - 180.0));
+    }
+    else if (lng < -180.0) {
+        lng = (lng + 180.0)+180.0;
+    }
+    LatLng ll=new FloatLatLng(lat, lng);
+    return ll;
+  }
+
   @Override
   public int hashCode() {
     final int prime = 31;

Modified: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/CartesianPolyFilterBuilder.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/CartesianPolyFilterBuilder.java?rev=817456&r1=817455&r2=817456&view=diff
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/CartesianPolyFilterBuilder.java
(original)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/CartesianPolyFilterBuilder.java
Tue Sep 22 00:08:21 2009
@@ -27,6 +27,9 @@
 import org.apache.lucene.spatial.tier.projections.CartesianTierPlotter;
 import org.apache.lucene.spatial.tier.projections.IProjector;
 import org.apache.lucene.spatial.tier.projections.SinusoidalProjector;
+import org.apache.lucene.spatial.geometry.LatLng;
+import org.apache.lucene.spatial.geometry.FloatLatLng;
+import org.apache.lucene.spatial.geometry.shape.LLRect;
 
 
 /**
@@ -57,12 +60,27 @@
       miles = MILES_FLOOR;
     }
     Rectangle box = DistanceUtils.getInstance().getBoundary(latitude, longitude, miles);
-    double latY = box.getMaxPoint().getY();//box.getY();
-    double latX = box.getMinPoint().getY() ; //box.getMaxY();
-    
-    double longY = box.getMaxPoint().getX(); ///box.getX();
-    double longX = box.getMinPoint().getX();//box.getMaxX();
+    LLRect box1 = LLRect.createBox( new FloatLatLng( latitude, longitude ), miles, miles
);
+    LatLng ll = box1.getLowerLeft();
+    LatLng ur = box1.getUpperRight();
+
+    double latY = ur.getLat();
+    double latX = ll.getLat();
+    double longY = ur.getLng();
+    double longX = ll.getLng();
+    double longX2 = 0.0;
+
+    if (ur.getLng() < 0.0 && ll.getLng() > 0.0) {
+	longX2 = ll.getLng();
+ 	longX = -180.0;	
+    }
+    if (ur.getLng() > 0.0 && ll.getLng() < 0.0) {
+	longX2 = ll.getLng();
+ 	longX = 0.0;	
+    }
     
+    //System.err.println("getBoxShape:"+latY+"," + longY);
+    //System.err.println("getBoxShape:"+latX+"," + longX);
     CartesianTierPlotter ctp = new CartesianTierPlotter(2, projector,tierPrefix);
     int bestFit = ctp.bestFit(miles);
     
@@ -74,13 +92,37 @@
     // iterate from startX->endX
     //     iterate from startY -> endY
     //      shape.add(currentLat.currentLong);
-    
-   
+
+    shape = getShapeLoop(shape,ctp,latX,longX,latY,longY);
+    if (longX2 != 0.0) {
+	if (longX2 != 0.0) {
+		if (longX == 0.0) {
+			longX = longX2;
+			longY = 0.0;
+        		shape = getShapeLoop(shape,ctp,latX,longX,latY,longY);
+		} else {
+			longX = longX2;
+			longY = -180.0;
+        		shape = getShapeLoop(shape,ctp,latY,longY,latX,longX);
+		}
+	}
+        //System.err.println("getBoxShape2:"+latY+"," + longY);
+        //System.err.println("getBoxShape2:"+latX+"," + longX);
+    }
+ 
+    return shape; 
+  } 
+  
+  public Shape getShapeLoop(Shape shape, CartesianTierPlotter ctp, double latX, double longX,
double latY, double longY)
+  {  
+ 
+    //System.err.println("getShapeLoop:"+latY+"," + longY);
+    //System.err.println("getShapeLoop:"+latX+"," + longX);
     double beginAt = ctp.getTierBoxId(latX, longX);
     double endAt = ctp.getTierBoxId(latY, longY);
     
     double tierVert = ctp.getTierVerticalPosDivider();
-    log.fine(" | "+ beginAt+" | "+ endAt);
+    //System.err.println(" | "+ beginAt+" | "+ endAt);
     
     double startX = beginAt - (beginAt %1);
     double startY = beginAt - startX ; //should give a whole number
@@ -97,15 +139,18 @@
     double xInc = 1.0d / tierVert;
     xInc = new BigDecimal(xInc).setScale(scale, RoundingMode.HALF_EVEN).doubleValue();
     
+    //System.err.println("go from startX:"+startX+" to:" + endX);
     for (; startX <= endX; startX++){
       
       double itY = startY;
+      //System.err.println("go from startY:"+startY+" to:" + endY);
       while (itY <= endY){
         //create a boxId
         // startX.startY
         double boxId = startX + itY ;
         shape.addBox(boxId);
-        //System.out.println("----"+boxId);
+        //System.err.println("----"+startX+" and "+itY);
+        //System.err.println("----"+boxId);
         itY += xInc;
         
         // java keeps 0.0001 as 1.0E-1

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=817456&r1=817455&r2=817456&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
Tue Sep 22 00:08:21 2009
@@ -44,7 +44,9 @@
 import org.apache.lucene.spatial.tier.projections.SinusoidalProjector;
 import org.apache.lucene.store.Directory;
 import org.apache.lucene.store.RAMDirectory;
-
+import org.apache.lucene.spatial.geometry.LatLng;
+import org.apache.lucene.spatial.geometry.FloatLatLng;
+import org.apache.lucene.spatial.geometry.DistanceUnits;
 
 /**
  *
@@ -138,10 +140,204 @@
     addPoint(writer,"Iota Club and Cafe",38.8890000,-77.0923000);
     addPoint(writer,"Hilton Washington Embassy Row",38.9103000,-77.0451000);
     addPoint(writer,"HorseFeathers, Bar & Grill", 39.01220000000001, -77.3942);
+    addPoint(writer,"Marshall Island Airfield",7.06, 171.2);
+    addPoint(writer,"Midway Island",25.7, -171.7);
+    addPoint(writer,"North Pole Way",55.0, 4.0);
    
     writer.commit();
     writer.close();
   }
+
+
+  public void testDistances() throws IOException, InvalidGeoException {
+    LatLng p1 = new FloatLatLng( 7.06, 171.2 );
+    LatLng p2 = new FloatLatLng( 21.6032207, -158.0 );
+    double miles = p1.arcDistance( p2, DistanceUnits.MILES );
+    System.out.println("testDistances");
+    System.out.println("miles:" + miles);
+    assertEquals(2288.82495932794, miles); 
+    LatLng p3 = new FloatLatLng( 41.6032207, -73.087749);
+    LatLng p4 = new FloatLatLng( 55.0, 4.0 );
+    miles = p3.arcDistance( p4, DistanceUnits.MILES );
+    System.out.println("miles:" + miles);
+    assertEquals(3474.331719997617, miles); 
+  }
+
+  public void testAntiM() throws IOException, InvalidGeoException {
+    searcher = new IndexSearcher(directory);
+
+    final double miles = 2800.0;
+        // Hawaii
+        // 2300 miles to Marshall Island Airfield
+    lat = 21.6032207;
+    lng = -158.0;
+
+    System.out.println("testAntiM");
+    // create a distance query
+    final DistanceQueryBuilder dq = new DistanceQueryBuilder(lat, lng, miles,
+        latField, lngField, 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(dq.getQuery(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.
+    //
+    DistanceFieldComparatorSource dsort = new DistanceFieldComparatorSource(dq.distanceFilter);
+    Sort sort = new Sort(new SortField("foo", dsort,false));
+
+    // Perform the search, using the term query, the serial chain filter, and the
+    // distance sort
+    Hits hits = searcher.search(customScore,null,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 2 "+ distances.size());
+    System.out.println("Results should be 2 "+ results);
+
+    assertEquals(2, distances.size()); // fixed a store of only needed distances
+    assertEquals(2, results);
+    double lastDistance = 0;
+    for(int i =0 ; i < results; i++){
+      Document d = hits.doc(i);
+
+      String name = d.get("name");
+      double rsLat = NumericUtils.prefixCodedToDouble(d.get(latField));
+      double rsLng = NumericUtils.prefixCodedToDouble(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 "+ distance); //(res, ortho, harvesine):"+
distance +" |"+ geo_distance +"|"+ llm +" | score "+ hits.score(i));
+      assertTrue(Math.abs((distance - llm)) < 1);
+      assertTrue((distance < miles ));
+      assertTrue(geo_distance >= lastDistance);
+      lastDistance = geo_distance;
+    }
+  }
+
+  public void testPoleFlipping() throws IOException, InvalidGeoException {
+    searcher = new IndexSearcher(directory);
+
+    final double miles = 3500.0;
+    lat = 41.6032207;
+    lng = -73.087749;
+
+    System.out.println("testPoleFlipping");
+
+    // create a distance query
+    final DistanceQueryBuilder dq = new DistanceQueryBuilder(lat, lng, miles,
+        latField, lngField, 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(dq.getQuery(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.
+    //
+    DistanceFieldComparatorSource dsort = new DistanceFieldComparatorSource(dq.distanceFilter);
+    Sort sort = new Sort(new SortField("foo", dsort,false));
+
+    // Perform the search, using the term query, the serial chain filter, and the
+    // distance sort
+    Hits hits = searcher.search(customScore,null,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 18 "+ distances.size());
+    System.out.println("Results should be 18 "+ results);
+
+    assertEquals(18, distances.size()); // fixed a store of only needed distances
+    assertEquals(18, results);
+    double lastDistance = 0;
+    for(int i =0 ; i < results; i++){
+      Document d = hits.doc(i);
+      String name = d.get("name");
+      double rsLat = NumericUtils.prefixCodedToDouble(d.get(latField));
+      double rsLng = NumericUtils.prefixCodedToDouble(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 "+ distance); //(res, ortho, harvesine):"+
distance +" |"+ geo_distance +"|"+ llm +" | score "+ hits.score(i));
+      assertTrue(Math.abs((distance - llm)) < 1);
+      System.out.println("checking limit "+ distance + " < " + miles);
+      assertTrue((distance < miles ));
+      System.out.println("checking sort "+ geo_distance + " >= " + lastDistance);
+      assertTrue(geo_distance >= lastDistance);
+      lastDistance = geo_distance;
+    }
+  }
   
   public void testRange() throws IOException, InvalidGeoException {
     searcher = new IndexSearcher(directory);
@@ -207,8 +403,8 @@
       System.out.println("Distance Filter filtered: " + distances.size());
       System.out.println("Results: " + results);
       System.out.println("=============================");
-      System.out.println("Distances should be 7 "+ distances.size());
-      System.out.println("Results should be 7 "+ results);
+      System.out.println("Distances should be 7 "+ expected[x] + ":" + distances.size());
+      System.out.println("Results should be 7 "+ expected[x] + ":" + results);
 
       assertEquals(expected[x], distances.size()); // fixed a store of only needed distances
       assertEquals(expected[x], results);
@@ -296,8 +492,8 @@
       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);
+      System.out.println("Distances should be 14 "+ expected[x] + ":" + distances.size());
+      System.out.println("Results should be 7 "+ expected[x] + ":" + results);
 
       assertEquals(expected[x], distances.size());
       assertEquals(expected[x], results);



Mime
View raw message