Return-Path: X-Original-To: apmail-lucene-commits-archive@www.apache.org Delivered-To: apmail-lucene-commits-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 67E011833A for ; Wed, 6 Apr 2016 23:17:46 +0000 (UTC) Received: (qmail 4016 invoked by uid 500); 6 Apr 2016 23:17:46 -0000 Mailing-List: contact commits-help@lucene.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@lucene.apache.org Delivered-To: mailing list commits@lucene.apache.org Received: (qmail 4006 invoked by uid 99); 6 Apr 2016 23:17:46 -0000 Received: from git1-us-west.apache.org (HELO git1-us-west.apache.org) (140.211.11.23) by apache.org (qpsmtpd/0.29) with ESMTP; Wed, 06 Apr 2016 23:17:46 +0000 Received: by git1-us-west.apache.org (ASF Mail Server at git1-us-west.apache.org, from userid 33) id 1B921DFF41; Wed, 6 Apr 2016 23:17:46 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: mikemccand@apache.org To: commits@lucene.apache.org Message-Id: <11a52ece20ae4becab401f851f3cbf50@git.apache.org> X-Mailer: ASF-Git Admin Mailer Subject: lucene-solr:branch_6x: LUCENE-7168: improve encode and quantization testing for geo3d Date: Wed, 6 Apr 2016 23:17:46 +0000 (UTC) Repository: lucene-solr Updated Branches: refs/heads/branch_6x a3ea71e04 -> 6868a8cd7 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/6868a8cd Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/6868a8cd Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/6868a8cd Branch: refs/heads/branch_6x Commit: 6868a8cd74d2d21dd679dfbb867d0823253ac2a5 Parents: a3ea71e Author: Mike McCandless Authored: Wed Apr 6 19:18:56 2016 -0400 Committer: Mike McCandless Committed: Wed Apr 6 19:19:31 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/6868a8cd/lucene/CHANGES.txt ---------------------------------------------------------------------- diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt index da5be98..f28254d 100644 --- a/lucene/CHANGES.txt +++ b/lucene/CHANGES.txt @@ -63,6 +63,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/6868a8cd/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/6868a8cd/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/6868a8cd/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< 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/6868a8cd/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/6868a8cd/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/6868a8cd/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 deleted = new HashSet<>(); // RandomIndexWriter is too slow here: IndexWriter w = new IndexWriter(dir, iwc); - for(int id=0;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 threads = new ArrayList<>(); final int iters = atLeast(100); - final CountDownLatch startingGun = new CountDownLatch(1); - final AtomicBoolean failed = new AtomicBoolean(); - - for(int i=0;i", point.toString()); + assertEquals("Geo3DPoint ", 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 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 stack = new ArrayList<>(); + private List 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 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); + } }