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 mi...@apache.org on 2009/09/22 02:08:21 UTC
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/
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);