You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by rm...@apache.org on 2016/04/13 16:33:38 UTC
lucene-solr:master: LUCENE-7185: add proper tests for grid bugs found
here, and fix related bugs still lurking
Repository: lucene-solr
Updated Branches:
refs/heads/master 744b419b4 -> cd673ebec
LUCENE-7185: add proper tests for grid bugs found here, and fix related bugs still lurking
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/cd673ebe
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/cd673ebe
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/cd673ebe
Branch: refs/heads/master
Commit: cd673ebec93cbdf37d14b3984552cec4388cea0f
Parents: 744b419
Author: Robert Muir <rm...@apache.org>
Authored: Wed Apr 13 10:32:42 2016 -0400
Committer: Robert Muir <rm...@apache.org>
Committed: Wed Apr 13 10:33:26 2016 -0400
----------------------------------------------------------------------
.../org/apache/lucene/document/LatLonGrid.java | 10 ++--
.../apache/lucene/document/TestLatLonGrid.java | 53 +++++++++++++++++++-
2 files changed, 58 insertions(+), 5 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/cd673ebe/lucene/sandbox/src/java/org/apache/lucene/document/LatLonGrid.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonGrid.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonGrid.java
index 7cb047a..e5718e2 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonGrid.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonGrid.java
@@ -22,8 +22,6 @@ import org.apache.lucene.util.FixedBitSet;
import static org.apache.lucene.geo.GeoEncodingUtils.decodeLatitude;
import static org.apache.lucene.geo.GeoEncodingUtils.decodeLongitude;
-import static org.apache.lucene.geo.GeoEncodingUtils.encodeLatitude;
-import static org.apache.lucene.geo.GeoEncodingUtils.encodeLongitude;
/**
* This is a temporary hack, until some polygon methods have better performance!
@@ -80,8 +78,10 @@ final class LatLonGrid {
long latitudeRange = maxLat - (long) minLat;
long longitudeRange = maxLon - (long) minLon;
- if (latitudeRange < GRID_SIZE || longitudeRange < GRID_SIZE) {
- // don't complicate fill right now if you pass e.g. emptyish stuff: make an "empty grid"
+ // if the range is too small, we can't divide it up in our grid nicely.
+ // in this case of a tiny polygon, we just make an empty grid instead of complicating/slowing down code.
+ final long minRange = (GRID_SIZE - 1) * (GRID_SIZE - 1);
+ if (latitudeRange < minRange || longitudeRange < minRange) {
latPerCell = lonPerCell = Long.MAX_VALUE;
} else {
// we spill over the edge of the bounding box in each direction a bit,
@@ -160,7 +160,9 @@ final class LatLonGrid {
long lonRel = longitude - (long) minLon;
int latIndex = (int) (latRel / latPerCell);
+ assert latIndex < GRID_SIZE;
int lonIndex = (int) (lonRel / lonPerCell);
+ assert lonIndex < GRID_SIZE;
return latIndex * GRID_SIZE + lonIndex;
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/cd673ebe/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonGrid.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonGrid.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonGrid.java
index 0b739ae..891e3d5 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonGrid.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonGrid.java
@@ -17,6 +17,7 @@
package org.apache.lucene.document;
import org.apache.lucene.geo.GeoTestUtil;
+import org.apache.lucene.geo.GeoUtils;
import org.apache.lucene.geo.Polygon;
import org.apache.lucene.geo.Rectangle;
import org.apache.lucene.util.LuceneTestCase;
@@ -32,7 +33,7 @@ public class TestLatLonGrid extends LuceneTestCase {
/** If the grid returns true, then any point in that cell should return true as well */
public void testRandom() throws Exception {
- for (int i = 0; i < 100; i++) {
+ for (int i = 0; i < 1000; i++) {
Polygon polygon = GeoTestUtil.nextPolygon();
Rectangle box = Rectangle.fromPolygon(new Polygon[] { polygon });
int minLat = encodeLatitude(box.minLat);
@@ -52,4 +53,54 @@ public class TestLatLonGrid extends LuceneTestCase {
}
}
}
+
+ public void testGrowingPolygon() {
+ double centerLat = -80.0 + random().nextDouble() * 160.0;
+ double centerLon = -170.0 + random().nextDouble() * 340.0;
+ double radiusMeters = 0.0;
+ for(int i=0;i<10;i++) {
+ radiusMeters = Math.nextUp(radiusMeters);
+ }
+
+ // Start with a miniscule polygon, and grow it:
+ int gons = TestUtil.nextInt(random(), 4, 10);
+ while (radiusMeters < GeoUtils.EARTH_MEAN_RADIUS_METERS * Math.PI / 2.0 + 1.0) {
+ Polygon polygon;
+ try {
+ polygon = GeoTestUtil.createRegularPolygon(centerLat, centerLon, radiusMeters, gons);
+ } catch (IllegalArgumentException iae) {
+ // OK: we made a too-big poly and it crossed a pole or dateline
+ break;
+ }
+ radiusMeters *= 1.1;
+
+ Rectangle box = Rectangle.fromPolygon(new Polygon[] { polygon });
+ int minLat = encodeLatitude(box.minLat);
+ int maxLat = encodeLatitude(box.maxLat);
+ int minLon = encodeLongitude(box.minLon);
+ int maxLon = encodeLongitude(box.maxLon);
+ LatLonGrid grid = new LatLonGrid(minLat, maxLat, minLon, maxLon, polygon);
+ // we are in integer space... but exhaustive testing is slow!
+ for (int j = 0; j < 1000; j++) {
+ int lat = TestUtil.nextInt(random(), minLat, maxLat);
+ int lon = TestUtil.nextInt(random(), minLon, maxLon);
+
+ boolean expected = polygon.contains(decodeLatitude(lat),
+ decodeLongitude(lon));
+ boolean actual = grid.contains(lat, lon);
+ assertEquals(expected, actual);
+ }
+ }
+ }
+
+ /** create ever-increasing grids and check that too-small polygons don't blow it up */
+ public void testTinyGrids() {
+ double ZERO = decodeLatitude(0);
+ double ONE = decodeLatitude(1);
+ Polygon tiny = new Polygon(new double[] { ZERO, ZERO, ONE, ONE, ZERO }, new double[] { ZERO, ONE, ONE, ZERO, ZERO });
+ for (int max = 1; max < 500000; max++) {
+ LatLonGrid grid = new LatLonGrid(0, max, 0, max, tiny);
+ assertEquals(tiny.contains(decodeLatitude(max), decodeLongitude(max)), grid.contains(max, max));
+ }
+ }
}