You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by mi...@apache.org on 2016/04/07 01:16:49 UTC
lucene-solr:master: LUCENE-7168: improve encode and quantization
testing for geo3d
Repository: lucene-solr
Updated Branches:
refs/heads/master 0163574f9 -> c2289de3c
LUCENE-7168: improve encode and quantization testing for geo3d
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/c2289de3
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/c2289de3
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/c2289de3
Branch: refs/heads/master
Commit: c2289de3c7100619b9476e4ec92ad6d4e89becc7
Parents: 0163574
Author: Mike McCandless <mi...@apache.org>
Authored: Wed Apr 6 19:18:56 2016 -0400
Committer: Mike McCandless <mi...@apache.org>
Committed: Wed Apr 6 19:18:56 2016 -0400
----------------------------------------------------------------------
lucene/CHANGES.txt | 3 +
.../org/apache/lucene/document/LatLonPoint.java | 4 +-
.../org/apache/lucene/spatial3d/Geo3DPoint.java | 5 +-
.../org/apache/lucene/spatial3d/Geo3DUtil.java | 75 +-
.../spatial3d/PointInGeo3DShapeQuery.java | 71 +-
.../spatial3d/PointInShapeIntersectVisitor.java | 107 +++
.../apache/lucene/spatial3d/TestGeo3DPoint.java | 682 +++++++++++++------
7 files changed, 622 insertions(+), 325 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c2289de3/lucene/CHANGES.txt
----------------------------------------------------------------------
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 614e492..d0a16d7 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -66,6 +66,9 @@ Bug Fixes
* LUCENE-7166: Fix corner case bugs in LatLonPoint/GeoPointField bounding box
queries. (Robert Muir)
+* LUCENE-7168: Switch to stable encode for geo3d, remove quantization
+ test leniency, remove dead code (Mike McCandless)
+
Other
* LUCENE-7174: Upgrade randomizedtesting to 2.3.4. (Uwe Schindler, Dawid Weiss)
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c2289de3/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPoint.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPoint.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPoint.java
index 107d83c..b2c39c2 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPoint.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPoint.java
@@ -199,7 +199,7 @@ public class LatLonPoint extends Field {
*/
public static double decodeLatitude(int encoded) {
double result = encoded * LATITUDE_DECODE;
- assert result >= GeoUtils.MIN_LAT_INCL && result <= GeoUtils.MAX_LAT_INCL;
+ assert result >= GeoUtils.MIN_LAT_INCL && result < GeoUtils.MAX_LAT_INCL;
return result;
}
@@ -220,7 +220,7 @@ public class LatLonPoint extends Field {
*/
public static double decodeLongitude(int encoded) {
double result = encoded * LONGITUDE_DECODE;
- assert result >= GeoUtils.MIN_LON_INCL && result <= GeoUtils.MAX_LON_INCL;
+ assert result >= GeoUtils.MIN_LON_INCL && result < GeoUtils.MAX_LON_INCL;
return result;
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c2289de3/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPoint.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPoint.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPoint.java
index be8990f..1e07aa7 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPoint.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPoint.java
@@ -24,7 +24,6 @@ import org.apache.lucene.document.FieldType;
import org.apache.lucene.index.PointValues;
import org.apache.lucene.geo.Polygon;
import org.apache.lucene.geo.GeoUtils;
-import org.apache.lucene.spatial3d.geom.Vector;
import org.apache.lucene.spatial3d.geom.GeoPoint;
import org.apache.lucene.spatial3d.geom.GeoShape;
import org.apache.lucene.spatial3d.geom.PlanetModel;
@@ -231,12 +230,12 @@ public final class Geo3DPoint extends Field {
/** Encode single dimension */
public static void encodeDimension(double value, byte bytes[], int offset) {
- NumericUtils.intToSortableBytes(Geo3DUtil.encodeValue(PlanetModel.WGS84.getMaximumMagnitude(), value), bytes, offset);
+ NumericUtils.intToSortableBytes(Geo3DUtil.encodeValue(value), bytes, offset);
}
/** Decode single dimension */
public static double decodeDimension(byte value[], int offset) {
- return Geo3DUtil.decodeValueCenter(PlanetModel.WGS84.getMaximumMagnitude(), NumericUtils.sortableBytesToInt(value, offset));
+ return Geo3DUtil.decodeValue(NumericUtils.sortableBytesToInt(value, offset));
}
/** Returns a query matching all points inside the provided shape.
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c2289de3/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DUtil.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DUtil.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DUtil.java
index 0a0bf30..cc11294 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DUtil.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DUtil.java
@@ -16,44 +16,59 @@
*/
package org.apache.lucene.spatial3d;
+import org.apache.lucene.spatial3d.geom.PlanetModel;
+
class Geo3DUtil {
- /** Clips the incoming value to the allowed min/max range before encoding, instead of throwing an exception. */
- public static int encodeValueLenient(double planetMax, double x) {
- if (x > planetMax) {
- x = planetMax;
- } else if (x < -planetMax) {
- x = -planetMax;
- }
- return encodeValue(planetMax, x);
- }
+ private static final double MAX_VALUE = PlanetModel.WGS84.getMaximumMagnitude();
+ private static final int BITS = 32;
+ private static final double MUL = (0x1L<<BITS)/(2*MAX_VALUE);
+ static final double DECODE = getNextSafeDouble(1/MUL);
+ private static final int MIN_ENCODED_VALUE = encodeValue(-MAX_VALUE);
- public static int encodeValue(double planetMax, double x) {
- if (x > planetMax) {
- throw new IllegalArgumentException("value=" + x + " is out-of-bounds (greater than planetMax=" + planetMax + ")");
+ public static int encodeValue(double x) {
+ if (x > MAX_VALUE) {
+ throw new IllegalArgumentException("value=" + x + " is out-of-bounds (greater than WGS84's planetMax=" + MAX_VALUE + ")");
}
- if (x < -planetMax) {
- throw new IllegalArgumentException("value=" + x + " is out-of-bounds (less than than -planetMax=" + -planetMax + ")");
+ if (x < -MAX_VALUE) {
+ throw new IllegalArgumentException("value=" + x + " is out-of-bounds (less than than WGS84's -planetMax=" + -MAX_VALUE + ")");
}
- long y = Math.round (x * (Integer.MAX_VALUE / planetMax));
- assert y >= Integer.MIN_VALUE;
- assert y <= Integer.MAX_VALUE;
-
- return (int) y;
+ long result = (long) Math.floor(x / DECODE);
+ //System.out.println(" enc: " + x + " -> " + result);
+ assert result >= Integer.MIN_VALUE;
+ assert result <= Integer.MAX_VALUE;
+ return (int) result;
}
- /** Center decode */
- public static double decodeValueCenter(double planetMax, int x) {
- return x * (planetMax / Integer.MAX_VALUE);
+ public static double decodeValue(int x) {
+ double result;
+ if (x == MIN_ENCODED_VALUE) {
+ // We must special case this, because -MAX_VALUE is not guaranteed to land precisely at a floor value, and we don't ever want to
+ // return a value outside of the planet's range (I think?). The max value is "safe" because we floor during encode:
+ result = -MAX_VALUE;
+ } else {
+ result = x * DECODE;
+ }
+ assert result >= -MAX_VALUE && result <= MAX_VALUE;
+ return result;
}
- /** More negative decode, at bottom of cell */
- public static double decodeValueMin(double planetMax, int x) {
- return (((double)x) - 0.5) * (planetMax / Integer.MAX_VALUE);
- }
-
- /** More positive decode, at top of cell */
- public static double decodeValueMax(double planetMax, int x) {
- return (((double)x) + 0.5) * (planetMax / Integer.MAX_VALUE);
+ /** Returns a double value >= x such that if you multiply that value by an int, and then
+ * divide it by that int again, you get precisely the same value back */
+ private static double getNextSafeDouble(double x) {
+
+ // Move to double space:
+ long bits = Double.doubleToLongBits(x);
+
+ // Make sure we are beyond the actual maximum value:
+ bits += Integer.MAX_VALUE;
+
+ // Clear the bottom 32 bits:
+ bits &= ~((long) Integer.MAX_VALUE);
+
+ // Convert back to double:
+ double result = Double.longBitsToDouble(bits);
+ assert result > x;
+ return result;
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c2289de3/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/PointInGeo3DShapeQuery.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/PointInGeo3DShapeQuery.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/PointInGeo3DShapeQuery.java
index 3cc9530..ef0fe47 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/PointInGeo3DShapeQuery.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/PointInGeo3DShapeQuery.java
@@ -19,13 +19,9 @@ package org.apache.lucene.spatial3d;
import java.io.IOException;
import org.apache.lucene.spatial3d.geom.BasePlanetObject;
-import org.apache.lucene.spatial3d.geom.GeoArea;
-import org.apache.lucene.spatial3d.geom.GeoAreaFactory;
import org.apache.lucene.spatial3d.geom.GeoShape;
import org.apache.lucene.spatial3d.geom.PlanetModel;
-import org.apache.lucene.index.PointValues.IntersectVisitor;
import org.apache.lucene.index.PointValues;
-import org.apache.lucene.index.PointValues.Relation;
import org.apache.lucene.index.LeafReader;
import org.apache.lucene.index.LeafReaderContext;
import org.apache.lucene.search.ConstantScoreScorer;
@@ -35,7 +31,6 @@ import org.apache.lucene.search.Query;
import org.apache.lucene.search.Scorer;
import org.apache.lucene.search.Weight;
import org.apache.lucene.util.DocIdSetBuilder;
-import org.apache.lucene.util.NumericUtils;
/** Finds all previously indexed points that fall within the specified polygon.
*
@@ -98,73 +93,9 @@ final class PointInGeo3DShapeQuery extends Query {
assert xyzSolid.getRelationship(shape) == GeoArea.WITHIN || xyzSolid.getRelationship(shape) == GeoArea.OVERLAPS: "expected WITHIN (1) or OVERLAPS (2) but got " + xyzSolid.getRelationship(shape) + "; shape="+shape+"; XYZSolid="+xyzSolid;
*/
- double planetMax = PlanetModel.WGS84.getMaximumMagnitude();
-
DocIdSetBuilder result = new DocIdSetBuilder(reader.maxDoc());
- values.intersect(field,
- new IntersectVisitor() {
-
- @Override
- public void visit(int docID) {
- result.add(docID);
- }
-
- @Override
- public void visit(int docID, byte[] packedValue) {
- assert packedValue.length == 12;
- double x = Geo3DPoint.decodeDimension(packedValue, 0);
- double y = Geo3DPoint.decodeDimension(packedValue, Integer.BYTES);
- double z = Geo3DPoint.decodeDimension(packedValue, 2 * Integer.BYTES);
- if (shape.isWithin(x, y, z)) {
- result.add(docID);
- }
- }
-
- @Override
- public Relation compare(byte[] minPackedValue, byte[] maxPackedValue) {
- // Because the dimensional format operates in quantized (64 bit -> 32 bit) space, and the cell bounds
- // here are inclusive, we need to extend the bounds to the largest un-quantized values that
- // could quantize into these bounds. The encoding (Geo3DUtil.encodeValue) does
- // a Math.round from double to long, so e.g. 1.4 -> 1, and -1.4 -> -1:
- double xMin = Geo3DUtil.decodeValueMin(planetMax, NumericUtils.sortableBytesToInt(minPackedValue, 0));
- double xMax = Geo3DUtil.decodeValueMax(planetMax, NumericUtils.sortableBytesToInt(maxPackedValue, 0));
- double yMin = Geo3DUtil.decodeValueMin(planetMax, NumericUtils.sortableBytesToInt(minPackedValue, 1 * Integer.BYTES));
- double yMax = Geo3DUtil.decodeValueMax(planetMax, NumericUtils.sortableBytesToInt(maxPackedValue, 1 * Integer.BYTES));
- double zMin = Geo3DUtil.decodeValueMin(planetMax, NumericUtils.sortableBytesToInt(minPackedValue, 2 * Integer.BYTES));
- double zMax = Geo3DUtil.decodeValueMax(planetMax, NumericUtils.sortableBytesToInt(maxPackedValue, 2 * Integer.BYTES));
-
- //System.out.println(" compare: x=" + cellXMin + "-" + cellXMax + " y=" + cellYMin + "-" + cellYMax + " z=" + cellZMin + "-" + cellZMax);
- assert xMin <= xMax;
- assert yMin <= yMax;
- assert zMin <= zMax;
-
- GeoArea xyzSolid = GeoAreaFactory.makeGeoArea(PlanetModel.WGS84, xMin, xMax, yMin, yMax, zMin, zMax);
-
- switch(xyzSolid.getRelationship(shape)) {
- case GeoArea.CONTAINS:
- // Shape fully contains the cell
- //System.out.println(" inside");
- return Relation.CELL_INSIDE_QUERY;
- case GeoArea.OVERLAPS:
- // They do overlap but neither contains the other:
- //System.out.println(" crosses1");
- return Relation.CELL_CROSSES_QUERY;
- case GeoArea.WITHIN:
- // Cell fully contains the shape:
- //System.out.println(" crosses2");
- // return Relation.SHAPE_INSIDE_CELL;
- return Relation.CELL_CROSSES_QUERY;
- case GeoArea.DISJOINT:
- // They do not overlap at all
- //System.out.println(" outside");
- return Relation.CELL_OUTSIDE_QUERY;
- default:
- assert false;
- return Relation.CELL_CROSSES_QUERY;
- }
- }
- });
+ values.intersect(field, new PointInShapeIntersectVisitor(result, shape));
return new ConstantScoreScorer(this, score(), result.build().iterator());
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c2289de3/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/PointInShapeIntersectVisitor.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/PointInShapeIntersectVisitor.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/PointInShapeIntersectVisitor.java
new file mode 100644
index 0000000..25dea72
--- /dev/null
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/PointInShapeIntersectVisitor.java
@@ -0,0 +1,107 @@
+/*
+ * 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.spatial3d;
+
+import org.apache.lucene.index.PointValues.IntersectVisitor;
+import org.apache.lucene.index.PointValues.Relation;
+import org.apache.lucene.spatial3d.geom.GeoArea;
+import org.apache.lucene.spatial3d.geom.GeoAreaFactory;
+import org.apache.lucene.spatial3d.geom.GeoShape;
+import org.apache.lucene.spatial3d.geom.PlanetModel;
+import org.apache.lucene.util.DocIdSetBuilder;
+import org.apache.lucene.util.NumericUtils;
+
+class PointInShapeIntersectVisitor implements IntersectVisitor {
+ private final DocIdSetBuilder hits;
+ private final GeoShape shape;
+
+ public PointInShapeIntersectVisitor(DocIdSetBuilder hits, GeoShape shape) {
+ this.hits = hits;
+ this.shape = shape;
+ }
+
+ @Override
+ public void visit(int docID) {
+ hits.add(docID);
+ }
+
+ @Override
+ public void visit(int docID, byte[] packedValue) {
+ assert packedValue.length == 12;
+ double x = Geo3DPoint.decodeDimension(packedValue, 0);
+ double y = Geo3DPoint.decodeDimension(packedValue, Integer.BYTES);
+ double z = Geo3DPoint.decodeDimension(packedValue, 2 * Integer.BYTES);
+ if (shape.isWithin(x, y, z)) {
+ hits.add(docID);
+ }
+ }
+
+ @Override
+ public Relation compare(byte[] minPackedValue, byte[] maxPackedValue) {
+ // Because the dimensional format operates in quantized (64 bit -> 32 bit) space, and the cell bounds
+ // here are inclusive, we need to extend the bounds to the largest un-quantized values that
+ // could quantize into these bounds. The encoding (Geo3DUtil.encodeValue) does
+ // a Math.round from double to long, so e.g. 1.4 -> 1, and -1.4 -> -1:
+ double xMin = decodeValueMin(NumericUtils.sortableBytesToInt(minPackedValue, 0));
+ double xMax = decodeValueMax(NumericUtils.sortableBytesToInt(maxPackedValue, 0));
+ double yMin = decodeValueMin(NumericUtils.sortableBytesToInt(minPackedValue, 1 * Integer.BYTES));
+ double yMax = decodeValueMax(NumericUtils.sortableBytesToInt(maxPackedValue, 1 * Integer.BYTES));
+ double zMin = decodeValueMin(NumericUtils.sortableBytesToInt(minPackedValue, 2 * Integer.BYTES));
+ double zMax = decodeValueMax(NumericUtils.sortableBytesToInt(maxPackedValue, 2 * Integer.BYTES));
+
+ //System.out.println(" compare: x=" + cellXMin + "-" + cellXMax + " y=" + cellYMin + "-" + cellYMax + " z=" + cellZMin + "-" + cellZMax);
+ assert xMin <= xMax;
+ assert yMin <= yMax;
+ assert zMin <= zMax;
+
+ GeoArea xyzSolid = GeoAreaFactory.makeGeoArea(PlanetModel.WGS84, xMin, xMax, yMin, yMax, zMin, zMax);
+
+ switch(xyzSolid.getRelationship(shape)) {
+ case GeoArea.CONTAINS:
+ // Shape fully contains the cell
+ //System.out.println(" inside");
+ return Relation.CELL_INSIDE_QUERY;
+ case GeoArea.OVERLAPS:
+ // They do overlap but neither contains the other:
+ //System.out.println(" crosses1");
+ return Relation.CELL_CROSSES_QUERY;
+ case GeoArea.WITHIN:
+ // Cell fully contains the shape:
+ //System.out.println(" crosses2");
+ // return Relation.SHAPE_INSIDE_CELL;
+ return Relation.CELL_CROSSES_QUERY;
+ case GeoArea.DISJOINT:
+ // They do not overlap at all
+ //System.out.println(" outside");
+ return Relation.CELL_OUTSIDE_QUERY;
+ default:
+ assert false;
+ return Relation.CELL_CROSSES_QUERY;
+ }
+ }
+
+ /** More negative decode, at bottom of cell */
+ static double decodeValueMin(int x) {
+ return (((double)x) - 0.5) * Geo3DUtil.DECODE;
+ }
+
+ /** More positive decode, at top of cell */
+ static double decodeValueMax(int x) {
+ return (((double)x) + 0.5) * Geo3DUtil.DECODE;
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/c2289de3/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java
index d0d3388..b751125 100644
--- a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java
+++ b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java
@@ -20,11 +20,10 @@ import java.io.IOException;
import java.io.PrintWriter;
import java.io.StringWriter;
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
-import java.util.concurrent.CountDownLatch;
-import java.util.concurrent.atomic.AtomicBoolean;
import org.apache.lucene.codecs.Codec;
import org.apache.lucene.codecs.FilterCodec;
@@ -36,55 +35,52 @@ import org.apache.lucene.codecs.lucene60.Lucene60PointsWriter;
import org.apache.lucene.document.Document;
import org.apache.lucene.document.Field;
import org.apache.lucene.document.NumericDocValuesField;
-import org.apache.lucene.spatial3d.geom.GeoArea;
-import org.apache.lucene.spatial3d.geom.GeoAreaFactory;
-import org.apache.lucene.spatial3d.geom.GeoBBoxFactory;
-import org.apache.lucene.spatial3d.geom.GeoCircleFactory;
-import org.apache.lucene.spatial3d.geom.GeoPathFactory;
-import org.apache.lucene.spatial3d.geom.GeoPoint;
-import org.apache.lucene.spatial3d.geom.GeoPolygonFactory;
-import org.apache.lucene.spatial3d.geom.GeoShape;
-import org.apache.lucene.spatial3d.geom.PlanetModel;
-import org.apache.lucene.spatial3d.geom.XYZBounds;
-import org.apache.lucene.spatial3d.geom.SidedPlane;
-import org.apache.lucene.spatial3d.geom.Plane;
-import org.apache.lucene.spatial3d.geom.GeoPolygon;
+import org.apache.lucene.geo.GeoTestUtil;
+import org.apache.lucene.geo.Polygon;
import org.apache.lucene.index.DirectoryReader;
import org.apache.lucene.index.IndexReader;
import org.apache.lucene.index.IndexWriter;
import org.apache.lucene.index.IndexWriterConfig;
+import org.apache.lucene.index.LeafReader;
import org.apache.lucene.index.LeafReaderContext;
import org.apache.lucene.index.MultiDocValues;
import org.apache.lucene.index.NumericDocValues;
+import org.apache.lucene.index.PointValues.IntersectVisitor;
+import org.apache.lucene.index.PointValues.Relation;
+import org.apache.lucene.index.ReaderUtil;
import org.apache.lucene.index.SegmentReadState;
import org.apache.lucene.index.SegmentWriteState;
import org.apache.lucene.index.Term;
import org.apache.lucene.search.IndexSearcher;
import org.apache.lucene.search.Query;
import org.apache.lucene.search.SimpleCollector;
+import org.apache.lucene.spatial3d.geom.GeoArea;
+import org.apache.lucene.spatial3d.geom.GeoAreaFactory;
+import org.apache.lucene.spatial3d.geom.GeoBBoxFactory;
+import org.apache.lucene.spatial3d.geom.GeoCircleFactory;
+import org.apache.lucene.spatial3d.geom.GeoPathFactory;
+import org.apache.lucene.spatial3d.geom.GeoPoint;
+import org.apache.lucene.spatial3d.geom.GeoPolygon;
+import org.apache.lucene.spatial3d.geom.GeoPolygonFactory;
+import org.apache.lucene.spatial3d.geom.GeoShape;
+import org.apache.lucene.spatial3d.geom.Plane;
+import org.apache.lucene.spatial3d.geom.PlanetModel;
+import org.apache.lucene.spatial3d.geom.SidedPlane;
+import org.apache.lucene.spatial3d.geom.XYZBounds;
import org.apache.lucene.store.Directory;
-import org.apache.lucene.geo.Polygon;
+import org.apache.lucene.util.DocIdSetBuilder;
import org.apache.lucene.util.FixedBitSet;
import org.apache.lucene.util.IOUtils;
import org.apache.lucene.util.LuceneTestCase;
+import org.apache.lucene.util.NumericUtils;
+import org.apache.lucene.util.StringHelper;
import org.apache.lucene.util.TestUtil;
-import org.junit.BeforeClass;
import org.junit.Ignore;
import com.carrotsearch.randomizedtesting.generators.RandomInts;
public class TestGeo3DPoint extends LuceneTestCase {
- private static boolean smallBBox;
-
- @BeforeClass
- public static void beforeClass() {
- smallBBox = random().nextBoolean();
- if (VERBOSE) {
- System.err.println("TEST: smallBBox=" + smallBBox);
- }
- }
-
private static Codec getCodec() {
if (Codec.getDefault().getName().equals("Lucene60")) {
int maxPointsInLeafNode = TestUtil.nextInt(random(), 16, 2048);
@@ -133,22 +129,7 @@ public class TestGeo3DPoint extends LuceneTestCase {
}
private static double toRadians(double degrees) {
- return Math.PI*(degrees/180.0);
- }
-
- private static PlanetModel getPlanetModel() {
- if (random().nextBoolean()) {
- // Use one of the earth models:
- if (random().nextBoolean()) {
- return PlanetModel.WGS84;
- } else {
- return PlanetModel.SPHERE;
- }
- } else {
- // Make a randomly squashed planet:
- double oblateness = random().nextDouble() * 0.5 - 0.25;
- return new PlanetModel(1.0 + oblateness, 1.0 - oblateness);
- }
+ return Math.toRadians(degrees);
}
private static class Cell {
@@ -178,10 +159,10 @@ public class TestGeo3DPoint extends LuceneTestCase {
}
/** Returns true if the quantized point lies within this cell, inclusive on all bounds. */
- public boolean contains(double planetMax, GeoPoint point) {
- int docX = Geo3DUtil.encodeValue(planetMax, point.x);
- int docY = Geo3DUtil.encodeValue(planetMax, point.y);
- int docZ = Geo3DUtil.encodeValue(planetMax, point.z);
+ public boolean contains(GeoPoint point) {
+ int docX = Geo3DUtil.encodeValue(point.x);
+ int docY = Geo3DUtil.encodeValue(point.y);
+ int docZ = Geo3DUtil.encodeValue(point.z);
return docX >= xMinEnc && docX <= xMaxEnc &&
docY >= yMinEnc && docY <= yMaxEnc &&
@@ -194,17 +175,17 @@ public class TestGeo3DPoint extends LuceneTestCase {
}
}
- private static GeoPoint quantize(double planetMax, GeoPoint point) {
- return new GeoPoint(Geo3DUtil.decodeValueCenter(planetMax, Geo3DUtil.encodeValue(planetMax, point.x)),
- Geo3DUtil.decodeValueCenter(planetMax, Geo3DUtil.encodeValue(planetMax, point.y)),
- Geo3DUtil.decodeValueCenter(planetMax, Geo3DUtil.encodeValue(planetMax, point.z)));
+ private static double quantize(double xyzValue) {
+ return Geo3DUtil.decodeValue(Geo3DUtil.encodeValue(xyzValue));
+ }
+
+ private static GeoPoint quantize(GeoPoint point) {
+ return new GeoPoint(quantize(point.x), quantize(point.y), quantize(point.z));
}
/** Tests consistency of GeoArea.getRelationship vs GeoShape.isWithin */
public void testGeo3DRelations() throws Exception {
- PlanetModel planetModel = getPlanetModel();
-
int numDocs = atLeast(1000);
if (VERBOSE) {
System.out.println("TEST: " + numDocs + " docs");
@@ -212,14 +193,12 @@ public class TestGeo3DPoint extends LuceneTestCase {
GeoPoint[] docs = new GeoPoint[numDocs];
for(int docID=0;docID<numDocs;docID++) {
- docs[docID] = new GeoPoint(planetModel, toRadians(randomLat()), toRadians(randomLon()));
+ docs[docID] = quantize(new GeoPoint(PlanetModel.WGS84, toRadians(GeoTestUtil.nextLatitude()), toRadians(GeoTestUtil.nextLongitude())));
if (VERBOSE) {
System.out.println(" doc=" + docID + ": " + docs[docID]);
}
}
- double planetMax = planetModel.getMaximumMagnitude();
-
int iters = atLeast(10);
int recurseDepth = RandomInts.randomIntBetween(random(), 5, 15);
@@ -227,7 +206,7 @@ public class TestGeo3DPoint extends LuceneTestCase {
iters = atLeast(50);
for(int iter=0;iter<iters;iter++) {
- GeoShape shape = randomShape(planetModel);
+ GeoShape shape = randomShape();
StringWriter sw = new StringWriter();
PrintWriter log = new PrintWriter(sw, true);
@@ -241,12 +220,12 @@ public class TestGeo3DPoint extends LuceneTestCase {
// Start with the root cell that fully contains the shape:
Cell root = new Cell(null,
- Geo3DUtil.encodeValueLenient(planetMax, bounds.getMinimumX()),
- Geo3DUtil.encodeValueLenient(planetMax, bounds.getMaximumX()),
- Geo3DUtil.encodeValueLenient(planetMax, bounds.getMinimumY()),
- Geo3DUtil.encodeValueLenient(planetMax, bounds.getMaximumY()),
- Geo3DUtil.encodeValueLenient(planetMax, bounds.getMinimumZ()),
- Geo3DUtil.encodeValueLenient(planetMax, bounds.getMaximumZ()),
+ encodeValueLenient(bounds.getMinimumX()),
+ encodeValueLenient(bounds.getMaximumX()),
+ encodeValueLenient(bounds.getMinimumY()),
+ encodeValueLenient(bounds.getMaximumY()),
+ encodeValueLenient(bounds.getMinimumZ()),
+ encodeValueLenient(bounds.getMaximumZ()),
0);
if (VERBOSE) {
@@ -271,8 +250,8 @@ public class TestGeo3DPoint extends LuceneTestCase {
// Leaf cell: brute force check all docs that fall within this cell:
for(int docID=0;docID<numDocs;docID++) {
GeoPoint point = docs[docID];
- if (cell.contains(planetMax, point)) {
- if (shape.isWithin(quantize(planetMax, point))) {
+ if (cell.contains(point)) {
+ if (shape.isWithin(point)) {
if (VERBOSE) {
log.println(" check doc=" + docID + ": match!");
}
@@ -286,15 +265,15 @@ public class TestGeo3DPoint extends LuceneTestCase {
}
} else {
- GeoArea xyzSolid = GeoAreaFactory.makeGeoArea(planetModel,
- Geo3DUtil.decodeValueMin(planetMax, cell.xMinEnc), Geo3DUtil.decodeValueMax(planetMax, cell.xMaxEnc),
- Geo3DUtil.decodeValueMin(planetMax, cell.yMinEnc), Geo3DUtil.decodeValueMax(planetMax, cell.yMaxEnc),
- Geo3DUtil.decodeValueMin(planetMax, cell.zMinEnc), Geo3DUtil.decodeValueMax(planetMax, cell.zMaxEnc));
+ GeoArea xyzSolid = GeoAreaFactory.makeGeoArea(PlanetModel.WGS84,
+ PointInShapeIntersectVisitor.decodeValueMin(cell.xMinEnc), PointInShapeIntersectVisitor.decodeValueMax(cell.xMaxEnc),
+ PointInShapeIntersectVisitor.decodeValueMin(cell.yMinEnc), PointInShapeIntersectVisitor.decodeValueMax(cell.yMaxEnc),
+ PointInShapeIntersectVisitor.decodeValueMin(cell.zMinEnc), PointInShapeIntersectVisitor.decodeValueMax(cell.zMaxEnc));
if (VERBOSE) {
- log.println(" minx="+Geo3DUtil.decodeValueMin(planetMax, cell.xMinEnc)+" maxx="+Geo3DUtil.decodeValueMax(planetMax, cell.xMaxEnc)+
- " miny="+Geo3DUtil.decodeValueMin(planetMax, cell.yMinEnc)+" maxy="+Geo3DUtil.decodeValueMax(planetMax, cell.yMaxEnc)+
- " minz="+Geo3DUtil.decodeValueMin(planetMax, cell.zMinEnc)+" maxz="+Geo3DUtil.decodeValueMax(planetMax, cell.zMaxEnc));
+ log.println(" minx="+PointInShapeIntersectVisitor.decodeValueMin(cell.xMinEnc)+" maxx="+PointInShapeIntersectVisitor.decodeValueMax(cell.xMaxEnc)+
+ " miny="+PointInShapeIntersectVisitor.decodeValueMin(cell.yMinEnc)+" maxy="+PointInShapeIntersectVisitor.decodeValueMax(cell.yMaxEnc)+
+ " minz="+PointInShapeIntersectVisitor.decodeValueMin(cell.zMinEnc)+" maxz="+PointInShapeIntersectVisitor.decodeValueMax(cell.zMaxEnc));
}
switch (xyzSolid.getRelationship(shape)) {
@@ -304,7 +283,7 @@ public class TestGeo3DPoint extends LuceneTestCase {
log.println(" GeoArea.CONTAINS: now addAll");
}
for(int docID=0;docID<numDocs;docID++) {
- if (cell.contains(planetMax, docs[docID])) {
+ if (cell.contains(docs[docID])) {
if (VERBOSE) {
log.println(" addAll doc=" + docID);
}
@@ -332,7 +311,7 @@ public class TestGeo3DPoint extends LuceneTestCase {
if (VERBOSE) {
log.println(" GeoArea.DISJOINT: drop this cell");
for(int docID=0;docID<numDocs;docID++) {
- if (cell.contains(planetMax, docs[docID])) {
+ if (cell.contains(docs[docID])) {
if (VERBOSE) {
log.println(" skip doc=" + docID);
}
@@ -436,23 +415,15 @@ public class TestGeo3DPoint extends LuceneTestCase {
boolean fail = false;
for(int docID=0;docID<numDocs;docID++) {
GeoPoint point = docs[docID];
- GeoPoint quantized = quantize(planetMax, point);
- boolean expected = shape.isWithin(quantized);
-
- if (expected != shape.isWithin(point)) {
- // Quantization changed the result; skip testing this doc:
- continue;
- }
-
+ boolean expected = shape.isWithin(point);
boolean actual = hits.contains(docID);
if (actual != expected) {
if (actual) {
- log.println("doc=" + docID + " matched but should not");
+ log.println("doc=" + docID + " should not have matched but did");
} else {
- log.println("doc=" + docID + " did not match but should");
+ log.println("doc=" + docID + " should match but did not");
}
log.println(" point=" + docs[docID]);
- log.println(" quantized=" + quantize(planetMax, docs[docID]));
fail = true;
}
}
@@ -513,13 +484,13 @@ public class TestGeo3DPoint extends LuceneTestCase {
if (x == 0) {
// Identical lat to old point
lats[docID] = lats[oldDocID];
- lons[docID] = randomLon();
+ lons[docID] = GeoTestUtil.nextLongitude();
if (VERBOSE) {
System.err.println(" doc=" + docID + " lat=" + lats[docID] + " lon=" + lons[docID] + " (same lat as doc=" + oldDocID + ")");
}
} else if (x == 1) {
// Identical lon to old point
- lats[docID] = randomLat();
+ lats[docID] = GeoTestUtil.nextLatitude();
lons[docID] = lons[oldDocID];
if (VERBOSE) {
System.err.println(" doc=" + docID + " lat=" + lats[docID] + " lon=" + lons[docID] + " (same lon as doc=" + oldDocID + ")");
@@ -534,8 +505,8 @@ public class TestGeo3DPoint extends LuceneTestCase {
}
}
} else {
- lats[docID] = randomLat();
- lons[docID] = randomLon();
+ lats[docID] = GeoTestUtil.nextLatitude();
+ lons[docID] = GeoTestUtil.nextLongitude();
haveRealDoc = true;
if (VERBOSE) {
System.err.println(" doc=" + docID + " lat=" + lats[docID] + " lon=" + lons[docID]);
@@ -546,24 +517,8 @@ public class TestGeo3DPoint extends LuceneTestCase {
verify(lats, lons);
}
- private static double randomLat() {
- if (smallBBox) {
- return 2.0 * (random().nextDouble()-0.5);
- } else {
- return -90 + 180.0 * random().nextDouble();
- }
- }
-
- private static double randomLon() {
- if (smallBBox) {
- return 2.0 * (random().nextDouble()-0.5);
- } else {
- return -180 + 360.0 * random().nextDouble();
- }
- }
-
// Poached from Geo3dRptTest.randomShape:
- private static GeoShape randomShape(PlanetModel planetModel) {
+ private static GeoShape randomShape() {
while (true) {
final int shapeType = random().nextInt(4);
switch (shapeType) {
@@ -572,12 +527,12 @@ public class TestGeo3DPoint extends LuceneTestCase {
final int vertexCount = random().nextInt(3) + 3;
final List<GeoPoint> geoPoints = new ArrayList<>();
while (geoPoints.size() < vertexCount) {
- final GeoPoint gPt = new GeoPoint(planetModel, toRadians(randomLat()), toRadians(randomLon()));
+ final GeoPoint gPt = new GeoPoint(PlanetModel.WGS84, toRadians(GeoTestUtil.nextLatitude()), toRadians(GeoTestUtil.nextLongitude()));
geoPoints.add(gPt);
}
final int convexPointIndex = random().nextInt(vertexCount); //If we get this wrong, hopefully we get IllegalArgumentException
try {
- return GeoPolygonFactory.makeGeoPolygon(planetModel, geoPoints, convexPointIndex);
+ return GeoPolygonFactory.makeGeoPolygon(PlanetModel.WGS84, geoPoints, convexPointIndex);
} catch (IllegalArgumentException e) {
// This is what happens when we create a shape that is invalid. Although it is conceivable that there are cases where
// the exception is thrown incorrectly, we aren't going to be able to do that in this random test.
@@ -588,18 +543,13 @@ public class TestGeo3DPoint extends LuceneTestCase {
case 1: {
// Circles
- double lat = toRadians(randomLat());
- double lon = toRadians(randomLon());
+ double lat = toRadians(GeoTestUtil.nextLatitude());
+ double lon = toRadians(GeoTestUtil.nextLongitude());
- double angle;
- if (smallBBox) {
- angle = random().nextDouble() * Math.PI/360.0;
- } else {
- angle = random().nextDouble() * Math.PI/2.0;
- }
+ double angle = random().nextDouble() * Math.PI/2.0;
try {
- return GeoCircleFactory.makeGeoCircle(planetModel, lat, lon, angle);
+ return GeoCircleFactory.makeGeoCircle(PlanetModel.WGS84, lat, lon, angle);
} catch (IllegalArgumentException iae) {
// angle is too small; try again:
continue;
@@ -608,22 +558,22 @@ public class TestGeo3DPoint extends LuceneTestCase {
case 2: {
// Rectangles
- double lat0 = toRadians(randomLat());
- double lat1 = toRadians(randomLat());
+ double lat0 = toRadians(GeoTestUtil.nextLatitude());
+ double lat1 = toRadians(GeoTestUtil.nextLatitude());
if (lat1 < lat0) {
double x = lat0;
lat0 = lat1;
lat1 = x;
}
- double lon0 = toRadians(randomLon());
- double lon1 = toRadians(randomLon());
+ double lon0 = toRadians(GeoTestUtil.nextLongitude());
+ double lon1 = toRadians(GeoTestUtil.nextLongitude());
if (lon1 < lon0) {
double x = lon0;
lon0 = lon1;
lon1 = x;
}
- return GeoBBoxFactory.makeGeoBBox(planetModel, lat1, lat0, lon0, lon1);
+ return GeoBBoxFactory.makeGeoBBox(PlanetModel.WGS84, lat1, lat0, lon0, lon1);
}
case 3: {
@@ -632,10 +582,10 @@ public class TestGeo3DPoint extends LuceneTestCase {
final double width = toRadians(random().nextInt(89)+1);
final GeoPoint[] points = new GeoPoint[pointCount];
for (int i = 0; i < pointCount; i++) {
- points[i] = new GeoPoint(planetModel, toRadians(randomLat()), toRadians(randomLon()));
+ points[i] = new GeoPoint(PlanetModel.WGS84, toRadians(GeoTestUtil.nextLatitude()), toRadians(GeoTestUtil.nextLongitude()));
}
try {
- return GeoPathFactory.makeGeoPath(planetModel, width, points);
+ return GeoPathFactory.makeGeoPath(PlanetModel.WGS84, width, points);
} catch (IllegalArgumentException e) {
// This is what happens when we create a shape that is invalid. Although it is conceivable that there are cases where
// the exception is thrown incorrectly, we aren't going to be able to do that in this random test.
@@ -652,14 +602,24 @@ public class TestGeo3DPoint extends LuceneTestCase {
private static void verify(double[] lats, double[] lons) throws Exception {
IndexWriterConfig iwc = newIndexWriterConfig();
+ GeoPoint[] points = new GeoPoint[lats.length];
+
+ // Pre-quantize all lat/lons:
+ for(int i=0;i<lats.length;i++) {
+ if (Double.isNaN(lats[i]) == false) {
+ //System.out.println("lats[" + i + "] = " + lats[i]);
+ points[i] = quantize(new GeoPoint(PlanetModel.WGS84, toRadians(lats[i]), toRadians(lons[i])));
+ }
+ }
+
// Else we can get O(N^2) merging:
int mbd = iwc.getMaxBufferedDocs();
- if (mbd != -1 && mbd < lats.length/100) {
- iwc.setMaxBufferedDocs(lats.length/100);
+ if (mbd != -1 && mbd < points.length/100) {
+ iwc.setMaxBufferedDocs(points.length/100);
}
iwc.setCodec(getCodec());
Directory dir;
- if (lats.length > 100000) {
+ if (points.length > 100000) {
dir = newFSDirectory(createTempDir("TestBKDTree"));
} else {
dir = getDirectory();
@@ -667,12 +627,13 @@ public class TestGeo3DPoint extends LuceneTestCase {
Set<Integer> deleted = new HashSet<>();
// RandomIndexWriter is too slow here:
IndexWriter w = new IndexWriter(dir, iwc);
- for(int id=0;id<lats.length;id++) {
+ for(int id=0;id<points.length;id++) {
Document doc = new Document();
doc.add(newStringField("id", ""+id, Field.Store.NO));
doc.add(new NumericDocValuesField("id", id));
- if (Double.isNaN(lats[id]) == false) {
- doc.add(new Geo3DPoint("point", lats[id], lons[id]));
+ GeoPoint point = points[id];
+ if (point != null) {
+ doc.add(new Geo3DPoint("point", point.x, point.y, point.z));
}
w.addDocument(doc);
if (id > 0 && random().nextInt(100) == 42) {
@@ -688,119 +649,89 @@ public class TestGeo3DPoint extends LuceneTestCase {
w.forceMerge(1);
}
final IndexReader r = DirectoryReader.open(w);
+ if (VERBOSE) {
+ System.out.println("TEST: using reader " + r);
+ }
w.close();
// We can't wrap with "exotic" readers because the geo3d query must see the Geo3DDVFormat:
IndexSearcher s = newSearcher(r, false);
- int numThreads = TestUtil.nextInt(random(), 2, 5);
-
- List<Thread> threads = new ArrayList<>();
final int iters = atLeast(100);
- final CountDownLatch startingGun = new CountDownLatch(1);
- final AtomicBoolean failed = new AtomicBoolean();
-
- for(int i=0;i<numThreads;i++) {
- Thread thread = new Thread() {
- @Override
- public void run() {
- try {
- _run();
- } catch (Exception e) {
- failed.set(true);
- throw new RuntimeException(e);
- }
- }
-
- private void _run() throws Exception {
- startingGun.await();
+ NumericDocValues docIDToID = MultiDocValues.getNumericValues(r, "id");
- NumericDocValues docIDToID = MultiDocValues.getNumericValues(r, "id");
+ for (int iter=0;iter<iters;iter++) {
- for (int iter=0;iter<iters && failed.get() == false;iter++) {
+ GeoShape shape = randomShape();
- GeoShape shape = randomShape(PlanetModel.WGS84);
-
- if (VERBOSE) {
- System.err.println("\n" + Thread.currentThread() + ": TEST: iter=" + iter + " shape="+shape);
- }
+ if (VERBOSE) {
+ System.err.println("\nTEST: iter=" + iter + " shape="+shape);
+ }
- Query query = Geo3DPoint.newShapeQuery("point", shape);
+ Query query = Geo3DPoint.newShapeQuery("point", shape);
- if (VERBOSE) {
- System.err.println(" using query: " + query);
- }
+ if (VERBOSE) {
+ System.err.println(" using query: " + query);
+ }
- final FixedBitSet hits = new FixedBitSet(r.maxDoc());
+ final FixedBitSet hits = new FixedBitSet(r.maxDoc());
- s.search(query, new SimpleCollector() {
+ s.search(query, new SimpleCollector() {
- private int docBase;
+ private int docBase;
- @Override
- public boolean needsScores() {
- return false;
- }
+ @Override
+ public boolean needsScores() {
+ return false;
+ }
- @Override
- protected void doSetNextReader(LeafReaderContext context) throws IOException {
- docBase = context.docBase;
- }
+ @Override
+ protected void doSetNextReader(LeafReaderContext context) throws IOException {
+ docBase = context.docBase;
+ }
- @Override
- public void collect(int doc) {
- hits.set(docBase+doc);
- }
- });
+ @Override
+ public void collect(int doc) {
+ hits.set(docBase+doc);
+ }
+ });
- if (VERBOSE) {
- System.err.println(" hitCount: " + hits.cardinality());
- }
+ if (VERBOSE) {
+ System.err.println(" hitCount: " + hits.cardinality());
+ }
- for(int docID=0;docID<r.maxDoc();docID++) {
- int id = (int) docIDToID.get(docID);
- if (Double.isNaN(lats[id]) == false) {
-
- // Accurate point:
- GeoPoint point1 = new GeoPoint(PlanetModel.WGS84, toRadians(lats[id]), toRadians(lons[id]));
-
- // Quantized point (32 bits per dim):
- GeoPoint point2 = quantize(PlanetModel.WGS84.getMaximumMagnitude(), point1);
-
- if (shape.isWithin(point1) != shape.isWithin(point2)) {
- if (VERBOSE) {
- System.out.println(" skip checking docID=" + docID + " quantization changed the expected result from " + shape.isWithin(point1) + " to " + shape.isWithin(point2));
- }
- continue;
- }
-
- boolean expected = ((deleted.contains(id) == false) && shape.isWithin(point2));
- if (hits.get(docID) != expected) {
- fail(Thread.currentThread().getName() + ": iter=" + iter + " id=" + id + " docID=" + docID + " lat=" + lats[id] + " lon=" + lons[id] + " expected " + expected + " but got: " + hits.get(docID) + " deleted?=" + deleted.contains(id) + "\n point1=" + point1 + ", iswithin="+shape.isWithin(point1)+"\n point2=" + point2 + ", iswithin="+shape.isWithin(point2) + "\n query=" + query);
- }
- } else {
- assertFalse(hits.get(docID));
- }
-
- }
+ for(int docID=0;docID<r.maxDoc();docID++) {
+ int id = (int) docIDToID.get(docID);
+ GeoPoint point = points[id];
+ if (point != null) {
+ boolean expected = ((deleted.contains(id) == false) && shape.isWithin(point));
+ if (hits.get(docID) != expected) {
+ StringBuilder b = new StringBuilder();
+ if (expected) {
+ b.append("FAIL: id=" + id + " should have matched but did not\n");
+ } else {
+ b.append("FAIL: id=" + id + " should not have matched but did\n");
}
+ b.append(" shape=" + shape + "\n");
+ b.append(" point=" + point + "\n");
+ b.append(" docID=" + docID + " deleted?=" + deleted.contains(id) + "\n");
+ b.append(" query=" + query + "\n");
+ b.append(" explanation:\n " + explain("point", shape, r, docID).replace("\n", "\n "));
+ fail(b.toString());
}
- };
- thread.setName("T" + i);
- thread.start();
- threads.add(thread);
- }
- startingGun.countDown();
- for(Thread thread : threads) {
- thread.join();
+ } else {
+ assertFalse(hits.get(docID));
+ }
+ }
}
+
IOUtils.close(r, dir);
}
public void testToString() {
Geo3DPoint point = new Geo3DPoint("point", 44.244272, 7.769736);
- assertEquals("Geo3DPoint <point: x=0.709426313149037 y=0.09679758908863707 z=0.6973564619509093>", point.toString());
+ assertEquals("Geo3DPoint <point: x=0.7094263127744131 y=0.09679758888428691 z=0.6973564619016113>", point.toString());
}
public void testShapeQueryToString() {
@@ -813,7 +744,7 @@ public class TestGeo3DPoint extends LuceneTestCase {
}
public void testEquals() {
- GeoShape shape = randomShape(PlanetModel.WGS84);
+ GeoShape shape = randomShape();
Query q = Geo3DPoint.newShapeQuery("point", shape);
assertEquals(q, Geo3DPoint.newShapeQuery("point", shape));
assertFalse(q.equals(Geo3DPoint.newShapeQuery("point2", shape)));
@@ -821,7 +752,7 @@ public class TestGeo3DPoint extends LuceneTestCase {
// make a different random shape:
GeoShape shape2;
do {
- shape2 = randomShape(PlanetModel.WGS84);
+ shape2 = randomShape();
} while (shape.equals(shape2));
assertFalse(q.equals(Geo3DPoint.newShapeQuery("point", shape2)));
@@ -830,12 +761,11 @@ public class TestGeo3DPoint extends LuceneTestCase {
public void testComplexPolygons() {
final PlanetModel pm = PlanetModel.WGS84;
// Pick a random pole
- final GeoPoint randomPole = new GeoPoint(pm, Math.toRadians(randomLat()), Math.toRadians(randomLon()));
+ final GeoPoint randomPole = new GeoPoint(pm, Math.toRadians(GeoTestUtil.nextLatitude()), Math.toRadians(GeoTestUtil.nextLongitude()));
// Create a polygon that's less than 180 degrees
final Polygon clockWise = makePoly(pm, randomPole, true, true);
// Create a polygon that's greater than 180 degrees
final Polygon counterClockWise = makePoly(pm, randomPole, false, true);
-
}
protected static double MINIMUM_EDGE_ANGLE = Math.toRadians(5.0);
@@ -911,7 +841,7 @@ public class TestGeo3DPoint extends LuceneTestCase {
// Choose a pole. The poly has to be within the polygon, but it also cannot be on the polygon edge.
// If we can't find a good pole we have to give it up and not do the hole.
for (int k = 0; k < 500; k++) {
- final GeoPoint poleChoice = new GeoPoint(pm, toRadians(randomLat()), toRadians(randomLon()));
+ final GeoPoint poleChoice = new GeoPoint(pm, toRadians(GeoTestUtil.nextLatitude()), toRadians(GeoTestUtil.nextLongitude()));
if (!poly.isWithin(poleChoice)) {
continue;
}
@@ -1053,4 +983,316 @@ public class TestGeo3DPoint extends LuceneTestCase {
}
return index;
}
+
+ public void testEncodeDecodeCeil() throws Exception {
+
+ // just for testing quantization error
+ final double ENCODING_TOLERANCE = Geo3DUtil.DECODE;
+
+ int iters = atLeast(10000);
+ for(int iter=0;iter<iters;iter++) {
+ GeoPoint point = new GeoPoint(PlanetModel.WGS84, toRadians(GeoTestUtil.nextLatitude()), toRadians(GeoTestUtil.nextLongitude()));
+ double xEnc = Geo3DUtil.decodeValue(Geo3DUtil.encodeValue(point.x));
+ assertEquals("x=" + point.x + " xEnc=" + xEnc + " diff=" + (point.x - xEnc), point.x, xEnc, ENCODING_TOLERANCE);
+
+ double yEnc = Geo3DUtil.decodeValue(Geo3DUtil.encodeValue(point.y));
+ assertEquals("y=" + point.y + " yEnc=" + yEnc + " diff=" + (point.y - yEnc), point.y, yEnc, ENCODING_TOLERANCE);
+
+ double zEnc = Geo3DUtil.decodeValue(Geo3DUtil.encodeValue(point.z));
+ assertEquals("z=" + point.z + " zEnc=" + zEnc + " diff=" + (point.z - zEnc), point.z, zEnc, ENCODING_TOLERANCE);
+ }
+
+ // check edge/interesting cases explicitly
+ double planetMax = PlanetModel.WGS84.getMaximumMagnitude();
+ for (double value : new double[] {0.0, -planetMax, planetMax}) {
+ assertEquals(value, Geo3DUtil.decodeValue(Geo3DUtil.encodeValue(value)), ENCODING_TOLERANCE);
+ }
+ }
+
+ /** make sure values always go down: this is important for edge case consistency */
+ public void testEncodeDecodeRoundsDown() throws Exception {
+
+ int iters = atLeast(1000);
+ for(int iter=0;iter<iters;iter++) {
+ final double latBase = GeoTestUtil.nextLatitude();
+ final double lonBase = GeoTestUtil.nextLongitude();
+
+ // test above the value
+ double lat = latBase;
+ double lon = lonBase;
+ for (int i = 0; i < 1000; i++) {
+ lat = Math.min(90, Math.nextUp(lat));
+ lon = Math.min(180, Math.nextUp(lon));
+ GeoPoint point = new GeoPoint(PlanetModel.WGS84, toRadians(lat), toRadians(lon));
+ GeoPoint pointEnc = new GeoPoint(PointInShapeIntersectVisitor.decodeValueMin(Geo3DUtil.encodeValue(point.x)),
+ PointInShapeIntersectVisitor.decodeValueMin(Geo3DUtil.encodeValue(point.y)),
+ PointInShapeIntersectVisitor.decodeValueMin(Geo3DUtil.encodeValue(point.z)));
+ assertTrue(pointEnc.x <= point.x);
+ assertTrue(pointEnc.y <= point.y);
+ assertTrue(pointEnc.z <= point.z);
+ }
+
+ // test below the value
+ lat = latBase;
+ lon = lonBase;
+ for (int i = 0; i < 1000; i++) {
+ lat = Math.max(-90, Math.nextDown(lat));
+ lon = Math.max(-180, Math.nextDown(lon));
+ GeoPoint point = new GeoPoint(PlanetModel.WGS84, toRadians(lat), toRadians(lon));
+ GeoPoint pointEnc = new GeoPoint(PointInShapeIntersectVisitor.decodeValueMin(Geo3DUtil.encodeValue(point.x)),
+ PointInShapeIntersectVisitor.decodeValueMin(Geo3DUtil.encodeValue(point.y)),
+ PointInShapeIntersectVisitor.decodeValueMin(Geo3DUtil.encodeValue(point.z)));
+ assertTrue(pointEnc.x <= point.x);
+ assertTrue(pointEnc.y <= point.y);
+ assertTrue(pointEnc.z <= point.z);
+ }
+ }
+ }
+
+ public void testEncodeDecodeIsStable() throws Exception {
+
+ int iters = atLeast(1000);
+ for(int iter=0;iter<iters;iter++) {
+ double lat = GeoTestUtil.nextLatitude();
+ double lon = GeoTestUtil.nextLongitude();
+
+ GeoPoint point = new GeoPoint(PlanetModel.WGS84, toRadians(lat), toRadians(lon));
+
+ // encode point
+ GeoPoint pointEnc = new GeoPoint(Geo3DUtil.decodeValue(Geo3DUtil.encodeValue(point.x)),
+ Geo3DUtil.decodeValue(Geo3DUtil.encodeValue(point.y)),
+ Geo3DUtil.decodeValue(Geo3DUtil.encodeValue(point.z)));
+
+ // encode it again (double encode)
+ GeoPoint pointEnc2 = new GeoPoint(Geo3DUtil.decodeValue(Geo3DUtil.encodeValue(pointEnc.x)),
+ Geo3DUtil.decodeValue(Geo3DUtil.encodeValue(pointEnc.y)),
+ Geo3DUtil.decodeValue(Geo3DUtil.encodeValue(pointEnc.z)));
+ //System.out.println("TEST " + iter + ":\n point =" + point + "\n pointEnc =" + pointEnc + "\n pointEnc2=" + pointEnc2);
+
+ assertEquals(pointEnc.x, pointEnc2.x, 0.0);
+ assertEquals(pointEnc.y, pointEnc2.y, 0.0);
+ assertEquals(pointEnc.z, pointEnc2.z, 0.0);
+ }
+ }
+
+ // Takes ~35 seconds on modern-ish 2015 dev box:
+ @Nightly
+ public void testEncodeIsStableFromIntSide() throws Exception {
+ double max = PlanetModel.WGS84.getMaximumMagnitude();
+
+ // We can't test the full space of ints (Integer.MIN_VALUE to Integer.MAX_VALUE) because not all ints are allowed:
+ int start = Geo3DUtil.encodeValue(-max);
+ int end = Geo3DUtil.encodeValue(max);
+ // This prints: 99.99997175764292
+ //System.out.println("PCTG INT SPACE USED: " + 100.*(((long) end)-(long) start)/(1L<<32));
+ for (int i=start;i<=end;i++) {
+ double x = Geo3DUtil.decodeValue(i);
+ assertEquals(i, Geo3DUtil.encodeValue(x));
+ if (i > start+1) {
+ assertEquals(Geo3DUtil.DECODE, x - Geo3DUtil.decodeValue(i-1), 0.0d);
+ }
+ }
+ }
+
+ /** Clips the incoming value to the allowed min/max range before encoding, instead of throwing an exception. */
+ private static int encodeValueLenient(double x) {
+ double planetMax = PlanetModel.WGS84.getMaximumMagnitude();
+ if (x > planetMax) {
+ x = planetMax;
+ } else if (x < -planetMax) {
+ x = -planetMax;
+ }
+ return Geo3DUtil.encodeValue(x);
+ }
+
+ private static class ExplainingVisitor implements IntersectVisitor {
+
+ final IntersectVisitor in;
+ final List<Cell> stack = new ArrayList<>();
+ private List<Cell> stackToTargetDoc;
+ final int targetDocID;
+ final int numDims;
+ final int bytesPerDim;
+ private int targetStackUpto;
+ final StringBuilder b;
+
+ // In the first phase, we always return CROSSES to do a full scan of the BKD tree to see which leaf block the document lives in
+ boolean firstPhase = true;
+
+ public ExplainingVisitor(IntersectVisitor in, int targetDocID, int numDims, int bytesPerDim, StringBuilder b) {
+ this.in = in;
+ this.targetDocID = targetDocID;
+ this.numDims = numDims;
+ this.bytesPerDim = bytesPerDim;
+ this.b = b;
+ }
+
+ public void startSecondPhase() {
+ if (firstPhase == false) {
+ throw new IllegalStateException("already started second phase");
+ }
+ if (stackToTargetDoc == null) {
+ b.append("target docID=" + targetDocID + " was never seen in points!\n");
+ }
+ firstPhase = false;
+ stack.clear();
+ }
+
+ @Override
+ public void visit(int docID) throws IOException {
+ assert firstPhase == false;
+ if (docID == targetDocID) {
+ b.append("leaf visit docID=" + docID + "\n");
+ }
+ }
+
+ @Override
+ public void visit(int docID, byte[] packedValue) throws IOException {
+ if (firstPhase) {
+ if (docID == targetDocID) {
+ assert stackToTargetDoc == null;
+ stackToTargetDoc = new ArrayList<>(stack);
+ b.append(" full BKD path to target doc:\n");
+ for(Cell cell : stack) {
+ b.append(" " + cell + "\n");
+ }
+ }
+ } else {
+ if (docID == targetDocID) {
+ double x = Geo3DPoint.decodeDimension(packedValue, 0);
+ double y = Geo3DPoint.decodeDimension(packedValue, Integer.BYTES);
+ double z = Geo3DPoint.decodeDimension(packedValue, 2 * Integer.BYTES);
+ b.append("leaf visit docID=" + docID + " x=" + x + " y=" + y + " z=" + z + "\n");
+ in.visit(docID, packedValue);
+ }
+ }
+ }
+
+ @Override
+ public Relation compare(byte[] minPackedValue, byte[] maxPackedValue) {
+ Cell cell = new Cell(minPackedValue, maxPackedValue);
+ //System.out.println("compare: " + cell);
+
+ // TODO: this is a bit hacky, having to reverse-engineer where we are in the BKD tree's recursion ... but it's the lesser evil vs e.g.
+ // polluting this visitor API, or implementing this "under the hood" in BKDReader instead?
+ if (firstPhase) {
+
+ // Pop stack:
+ while (stack.size() > 0 && stack.get(stack.size()-1).contains(cell)) {
+ stack.remove(stack.size()-1);
+ //System.out.println(" pop");
+ }
+
+ // Push stack:
+ stack.add(cell);
+ //System.out.println(" push");
+
+ return Relation.CELL_CROSSES_QUERY;
+ } else {
+ Relation result = in.compare(minPackedValue, maxPackedValue);
+ if (targetStackUpto < stackToTargetDoc.size() && cell.equals(stackToTargetDoc.get(targetStackUpto))) {
+ b.append(" on cell " + stackToTargetDoc.get(targetStackUpto) + ", wrapped visitor returned " + result);
+ targetStackUpto++;
+ }
+ return result;
+ }
+ }
+
+ private class Cell {
+ private final byte[] minPackedValue;
+ private final byte[] maxPackedValue;
+
+ public Cell(byte[] minPackedValue, byte[] maxPackedValue) {
+ this.minPackedValue = minPackedValue.clone();
+ this.maxPackedValue = maxPackedValue.clone();
+ }
+
+ /** Returns true if this cell fully contains the other one */
+ public boolean contains(Cell other) {
+ for(int dim=0;dim<numDims;dim++) {
+ int offset = bytesPerDim * dim;
+ // other.min < this.min?
+ if (StringHelper.compare(bytesPerDim, other.minPackedValue, offset, minPackedValue, offset) < 0) {
+ return false;
+ }
+ // other.max < this.max?
+ if (StringHelper.compare(bytesPerDim, other.maxPackedValue, offset, maxPackedValue, offset) > 0) {
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ @Override
+ public String toString() {
+ double xMin = PointInShapeIntersectVisitor.decodeValueMin(NumericUtils.sortableBytesToInt(minPackedValue, 0));
+ double xMax = PointInShapeIntersectVisitor.decodeValueMax(NumericUtils.sortableBytesToInt(maxPackedValue, 0));
+ double yMin = PointInShapeIntersectVisitor.decodeValueMin(NumericUtils.sortableBytesToInt(minPackedValue, 1 * Integer.BYTES));
+ double yMax = PointInShapeIntersectVisitor.decodeValueMax(NumericUtils.sortableBytesToInt(maxPackedValue, 1 * Integer.BYTES));
+ double zMin = PointInShapeIntersectVisitor.decodeValueMin(NumericUtils.sortableBytesToInt(minPackedValue, 2 * Integer.BYTES));
+ double zMax = PointInShapeIntersectVisitor.decodeValueMax(NumericUtils.sortableBytesToInt(maxPackedValue, 2 * Integer.BYTES));
+ return "Cell(x=" + xMin + " TO " + xMax + " y=" + yMin + " TO " + yMax + " z=" + zMin + " TO " + zMax + ")";
+ }
+
+ @Override
+ public boolean equals(Object other) {
+ if (other instanceof Cell == false) {
+ return false;
+ }
+
+ Cell otherCell = (Cell) other;
+ return Arrays.equals(minPackedValue, otherCell.minPackedValue) && Arrays.equals(maxPackedValue, otherCell.maxPackedValue);
+ }
+
+ @Override
+ public int hashCode() {
+ return Arrays.hashCode(minPackedValue) + Arrays.hashCode(maxPackedValue);
+ }
+ }
+ }
+
+ public static String explain(String fieldName, GeoShape shape, IndexReader reader, int docID) throws Exception {
+
+ // First find the leaf reader that owns this doc:
+ int subIndex = ReaderUtil.subIndex(docID, reader.leaves());
+ LeafReader leafReader = reader.leaves().get(subIndex).reader();
+
+ StringBuilder b = new StringBuilder();
+ b.append("target is in leaf " + leafReader + " of full reader " + reader + "\n");
+
+ DocIdSetBuilder hits = new DocIdSetBuilder(leafReader.maxDoc());
+ ExplainingVisitor visitor = new ExplainingVisitor(new PointInShapeIntersectVisitor(hits, shape), docID - reader.leaves().get(subIndex).docBase, 3, Integer.BYTES, b);
+
+ // Do first phase, where we just figure out the "path" that leads to the target docID:
+ leafReader.getPointValues().intersect(fieldName, visitor);
+
+ // Do second phase, where we we see how the wrapped visitor responded along that path:
+ visitor.startSecondPhase();
+ leafReader.getPointValues().intersect(fieldName, visitor);
+
+ return b.toString();
+ }
+
+ @Ignore("https://issues.apache.org/jira/browse/LUCENE-7168")
+ public void testCuriousFailure() throws Exception {
+ GeoShape shape = GeoCircleFactory.makeGeoCircle(PlanetModel.WGS84, -0.8971654677124566, -0.3398482030102755, 1.4775317506492547);
+ GeoPoint point = new GeoPoint(0.8653002868649471, 0.50134342478497, 0.046203414829601996);
+
+ // point is inside our circle shape:
+ assertTrue(shape.isWithin(point));
+
+ double xMin = 0.8653002866318559;
+ double xMax = 0.8653002870980383;
+ double yMin = 0.5013434245518787;
+ double yMax = 0.5013434250180612;
+ double zMin = 0.04620341459651078;
+ double zMax = 0.04620341506269321;
+ GeoArea xyzSolid = GeoAreaFactory.makeGeoArea(PlanetModel.WGS84, xMin, xMax, yMin, yMax, zMin, zMax);
+
+ // point is also inside our wee tiny box:
+ assertTrue(xyzSolid.isWithin(point));
+
+ assertTrue(xyzSolid.getRelationship(shape) != GeoArea.DISJOINT);
+ }
}