You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by iv...@apache.org on 2018/03/02 09:39:04 UTC
lucene-solr:master: LUCENE-8126: New spatial prefix tree (SPT) based
on google S2 geometry
Repository: lucene-solr
Updated Branches:
refs/heads/master f1ce5419e -> e3032dd3f
LUCENE-8126: New spatial prefix tree (SPT) based on google S2 geometry
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/e3032dd3
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/e3032dd3
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/e3032dd3
Branch: refs/heads/master
Commit: e3032dd3fcc28570c5f9d2dab4961b5b07555912
Parents: f1ce541
Author: Ignacio Vera <iv...@apache.org>
Authored: Fri Mar 2 10:29:07 2018 +0100
Committer: Ignacio Vera <iv...@apache.org>
Committed: Fri Mar 2 10:29:07 2018 +0100
----------------------------------------------------------------------
lucene/CHANGES.txt | 5 +
lucene/ivy-versions.properties | 4 +-
.../s2-geometry-library-java-1.0.0.jar.sha1 | 1 +
.../s2-geometry-library-java-LICENSE-ASL.txt | 202 +++++++++++++
.../s2-geometry-library-java-NOTICE.txt | 0
lucene/spatial-extras/ivy.xml | 2 +
.../spatial/prefix/tree/S2PrefixTree.java | 157 ++++++++++
.../spatial/prefix/tree/S2PrefixTreeCell.java | 289 +++++++++++++++++++
.../spatial/prefix/tree/S2ShapeFactory.java | 40 +++
.../spatial/spatial4j/Geo3dShapeFactory.java | 24 +-
.../spatial/prefix/tree/S2PrefixTreeTest.java | 113 ++++++++
.../lucene/spatial/spatial4j/Geo3dRptTest.java | 36 ++-
.../lucene/spatial3d/geom/GeoS2Shape.java | 202 +++++++++++++
.../spatial3d/geom/GeoS2ShapeFactory.java | 50 ++++
.../lucene/spatial3d/geom/StandardObjects.java | 1 +
15 files changed, 1113 insertions(+), 13 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e3032dd3/lucene/CHANGES.txt
----------------------------------------------------------------------
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 4a230b5..f62a7c4 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -120,6 +120,11 @@ New Features
(Lance Norskog, Grant Ingersoll, Joern Kottmann, Em, Kai Gülzau,
Rene Nederhand, Robert Muir, Steven Bower, Steve Rowe)
+* LUCENE-8126: Add new spatial prefix tree (SPT) based on google S2 geometry.
+ It can only be used currently with Geo3D spatial context and it provides
+ improvements on indexing time for non-points shapes and on query performance.
+ (Ignacio Vera, David Smiley).
+
Improvements
* LUCENE-8081: Allow IndexWriter to opt out of flushing on indexing threads
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e3032dd3/lucene/ivy-versions.properties
----------------------------------------------------------------------
diff --git a/lucene/ivy-versions.properties b/lucene/ivy-versions.properties
index 5ab36dd..fc8ea7d 100644
--- a/lucene/ivy-versions.properties
+++ b/lucene/ivy-versions.properties
@@ -70,7 +70,9 @@ io.dropwizard.metrics.version = 3.2.2
io.netty.netty-all.version = 4.0.36.Final
/io.netty/netty-all = ${io.netty.netty-all.version}
-/javax.activation/activation = 1.1.1
+/io.sgr/s2-geometry-library-java = 1.0.0
+
+javax.activation/activation = 1.1.1
/javax.servlet/javax.servlet-api = 3.1.0
/javax.servlet/servlet-api = 2.4
/joda-time/joda-time = 2.2
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e3032dd3/lucene/licenses/s2-geometry-library-java-1.0.0.jar.sha1
----------------------------------------------------------------------
diff --git a/lucene/licenses/s2-geometry-library-java-1.0.0.jar.sha1 b/lucene/licenses/s2-geometry-library-java-1.0.0.jar.sha1
new file mode 100644
index 0000000..2cfb3a8
--- /dev/null
+++ b/lucene/licenses/s2-geometry-library-java-1.0.0.jar.sha1
@@ -0,0 +1 @@
+f95b25589b40b5b0965deb592445073ff3efa299
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e3032dd3/lucene/licenses/s2-geometry-library-java-LICENSE-ASL.txt
----------------------------------------------------------------------
diff --git a/lucene/licenses/s2-geometry-library-java-LICENSE-ASL.txt b/lucene/licenses/s2-geometry-library-java-LICENSE-ASL.txt
new file mode 100644
index 0000000..03c7bfc
--- /dev/null
+++ b/lucene/licenses/s2-geometry-library-java-LICENSE-ASL.txt
@@ -0,0 +1,202 @@
+
+ Apache License
+ Version 2.0, January 2004
+ http://www.apache.org/licenses/
+
+ TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+ 1. Definitions.
+
+ "License" shall mean the terms and conditions for use, reproduction,
+ and distribution as defined by Sections 1 through 9 of this document.
+
+ "Licensor" shall mean the copyright owner or entity authorized by
+ the copyright owner that is granting the License.
+
+ "Legal Entity" shall mean the union of the acting entity and all
+ other entities that control, are controlled by, or are under common
+ control with that entity. For the purposes of this definition,
+ "control" means (i) the power, direct or indirect, to cause the
+ direction or management of such entity, whether by contract or
+ otherwise, or (ii) ownership of fifty percent (50%) or more of the
+ outstanding shares, or (iii) beneficial ownership of such entity.
+
+ "You" (or "Your") shall mean an individual or Legal Entity
+ exercising permissions granted by this License.
+
+ "Source" form shall mean the preferred form for making modifications,
+ including but not limited to software source code, documentation
+ source, and configuration files.
+
+ "Object" form shall mean any form resulting from mechanical
+ transformation or translation of a Source form, including but
+ not limited to compiled object code, generated documentation,
+ and conversions to other media types.
+
+ "Work" shall mean the work of authorship, whether in Source or
+ Object form, made available under the License, as indicated by a
+ copyright notice that is included in or attached to the work
+ (an example is provided in the Appendix below).
+
+ "Derivative Works" shall mean any work, whether in Source or Object
+ form, that is based on (or derived from) the Work and for which the
+ editorial revisions, annotations, elaborations, or other modifications
+ represent, as a whole, an original work of authorship. For the purposes
+ of this License, Derivative Works shall not include works that remain
+ separable from, or merely link (or bind by name) to the interfaces of,
+ the Work and Derivative Works thereof.
+
+ "Contribution" shall mean any work of authorship, including
+ the original version of the Work and any modifications or additions
+ to that Work or Derivative Works thereof, that is intentionally
+ submitted to Licensor for inclusion in the Work by the copyright owner
+ or by an individual or Legal Entity authorized to submit on behalf of
+ the copyright owner. For the purposes of this definition, "submitted"
+ means any form of electronic, verbal, or written communication sent
+ to the Licensor or its representatives, including but not limited to
+ communication on electronic mailing lists, source code control systems,
+ and issue tracking systems that are managed by, or on behalf of, the
+ Licensor for the purpose of discussing and improving the Work, but
+ excluding communication that is conspicuously marked or otherwise
+ designated in writing by the copyright owner as "Not a Contribution."
+
+ "Contributor" shall mean Licensor and any individual or Legal Entity
+ on behalf of whom a Contribution has been received by Licensor and
+ subsequently incorporated within the Work.
+
+ 2. Grant of Copyright License. Subject to the terms and conditions of
+ this License, each Contributor hereby grants to You a perpetual,
+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+ copyright license to reproduce, prepare Derivative Works of,
+ publicly display, publicly perform, sublicense, and distribute the
+ Work and such Derivative Works in Source or Object form.
+
+ 3. Grant of Patent License. Subject to the terms and conditions of
+ this License, each Contributor hereby grants to You a perpetual,
+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+ (except as stated in this section) patent license to make, have made,
+ use, offer to sell, sell, import, and otherwise transfer the Work,
+ where such license applies only to those patent claims licensable
+ by such Contributor that are necessarily infringed by their
+ Contribution(s) alone or by combination of their Contribution(s)
+ with the Work to which such Contribution(s) was submitted. If You
+ institute patent litigation against any entity (including a
+ cross-claim or counterclaim in a lawsuit) alleging that the Work
+ or a Contribution incorporated within the Work constitutes direct
+ or contributory patent infringement, then any patent licenses
+ granted to You under this License for that Work shall terminate
+ as of the date such litigation is filed.
+
+ 4. Redistribution. You may reproduce and distribute copies of the
+ Work or Derivative Works thereof in any medium, with or without
+ modifications, and in Source or Object form, provided that You
+ meet the following conditions:
+
+ (a) You must give any other recipients of the Work or
+ Derivative Works a copy of this License; and
+
+ (b) You must cause any modified files to carry prominent notices
+ stating that You changed the files; and
+
+ (c) You must retain, in the Source form of any Derivative Works
+ that You distribute, all copyright, patent, trademark, and
+ attribution notices from the Source form of the Work,
+ excluding those notices that do not pertain to any part of
+ the Derivative Works; and
+
+ (d) If the Work includes a "NOTICE" text file as part of its
+ distribution, then any Derivative Works that You distribute must
+ include a readable copy of the attribution notices contained
+ within such NOTICE file, excluding those notices that do not
+ pertain to any part of the Derivative Works, in at least one
+ of the following places: within a NOTICE text file distributed
+ as part of the Derivative Works; within the Source form or
+ documentation, if provided along with the Derivative Works; or,
+ within a display generated by the Derivative Works, if and
+ wherever such third-party notices normally appear. The contents
+ of the NOTICE file are for informational purposes only and
+ do not modify the License. You may add Your own attribution
+ notices within Derivative Works that You distribute, alongside
+ or as an addendum to the NOTICE text from the Work, provided
+ that such additional attribution notices cannot be construed
+ as modifying the License.
+
+ You may add Your own copyright statement to Your modifications and
+ may provide additional or different license terms and conditions
+ for use, reproduction, or distribution of Your modifications, or
+ for any such Derivative Works as a whole, provided Your use,
+ reproduction, and distribution of the Work otherwise complies with
+ the conditions stated in this License.
+
+ 5. Submission of Contributions. Unless You explicitly state otherwise,
+ any Contribution intentionally submitted for inclusion in the Work
+ by You to the Licensor shall be under the terms and conditions of
+ this License, without any additional terms or conditions.
+ Notwithstanding the above, nothing herein shall supersede or modify
+ the terms of any separate license agreement you may have executed
+ with Licensor regarding such Contributions.
+
+ 6. Trademarks. This License does not grant permission to use the trade
+ names, trademarks, service marks, or product names of the Licensor,
+ except as required for reasonable and customary use in describing the
+ origin of the Work and reproducing the content of the NOTICE file.
+
+ 7. Disclaimer of Warranty. Unless required by applicable law or
+ agreed to in writing, Licensor provides the Work (and each
+ Contributor provides its Contributions) on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+ implied, including, without limitation, any warranties or conditions
+ of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+ PARTICULAR PURPOSE. You are solely responsible for determining the
+ appropriateness of using or redistributing the Work and assume any
+ risks associated with Your exercise of permissions under this License.
+
+ 8. Limitation of Liability. In no event and under no legal theory,
+ whether in tort (including negligence), contract, or otherwise,
+ unless required by applicable law (such as deliberate and grossly
+ negligent acts) or agreed to in writing, shall any Contributor be
+ liable to You for damages, including any direct, indirect, special,
+ incidental, or consequential damages of any character arising as a
+ result of this License or out of the use or inability to use the
+ Work (including but not limited to damages for loss of goodwill,
+ work stoppage, computer failure or malfunction, or any and all
+ other commercial damages or losses), even if such Contributor
+ has been advised of the possibility of such damages.
+
+ 9. Accepting Warranty or Additional Liability. While redistributing
+ the Work or Derivative Works thereof, You may choose to offer,
+ and charge a fee for, acceptance of support, warranty, indemnity,
+ or other liability obligations and/or rights consistent with this
+ License. However, in accepting such obligations, You may act only
+ on Your own behalf and on Your sole responsibility, not on behalf
+ of any other Contributor, and only if You agree to indemnify,
+ defend, and hold each Contributor harmless for any liability
+ incurred by, or claims asserted against, such Contributor by reason
+ of your accepting any such warranty or additional liability.
+
+ END OF TERMS AND CONDITIONS
+
+ APPENDIX: How to apply the Apache License to your work.
+
+ To apply the Apache License to your work, attach the following
+ boilerplate notice, with the fields enclosed by brackets "[]"
+ replaced with your own identifying information. (Don't include
+ the brackets!) The text should be enclosed in the appropriate
+ comment syntax for the file format. We also recommend that a
+ file or class name and description of purpose be included on the
+ same "printed page" as the copyright notice for easier
+ identification within third-party archives.
+
+ Copyright [yyyy] [name of copyright owner]
+
+ Licensed 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.
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e3032dd3/lucene/licenses/s2-geometry-library-java-NOTICE.txt
----------------------------------------------------------------------
diff --git a/lucene/licenses/s2-geometry-library-java-NOTICE.txt b/lucene/licenses/s2-geometry-library-java-NOTICE.txt
new file mode 100644
index 0000000..e69de29
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e3032dd3/lucene/spatial-extras/ivy.xml
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/ivy.xml b/lucene/spatial-extras/ivy.xml
index df67503..c3d982f 100644
--- a/lucene/spatial-extras/ivy.xml
+++ b/lucene/spatial-extras/ivy.xml
@@ -25,6 +25,8 @@
<dependencies>
<dependency org="org.locationtech.spatial4j" name="spatial4j" rev="${/org.locationtech.spatial4j/spatial4j}" conf="compile"/>
+ <dependency org="io.sgr" name="s2-geometry-library-java" rev="${/io.sgr/s2-geometry-library-java}" conf="compile"/>
+
<dependency org="org.locationtech.spatial4j" name="spatial4j" rev="${/org.locationtech.spatial4j/spatial4j}" conf="test">
<artifact name="spatial4j" type="test" ext="jar" maven:classifier="tests" />
</dependency>
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e3032dd3/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/S2PrefixTree.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/S2PrefixTree.java b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/S2PrefixTree.java
new file mode 100644
index 0000000..f77c578
--- /dev/null
+++ b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/S2PrefixTree.java
@@ -0,0 +1,157 @@
+/*
+ * 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.spatial.prefix.tree;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import com.google.common.geometry.S2CellId;
+import com.google.common.geometry.S2LatLng;
+import com.google.common.geometry.S2Projections;
+import org.apache.lucene.util.BytesRef;
+import org.locationtech.spatial4j.context.SpatialContext;
+import org.locationtech.spatial4j.distance.DistanceUtils;
+import org.locationtech.spatial4j.shape.Point;
+import org.locationtech.spatial4j.shape.Shape;
+
+/**
+ * Spatial prefix tree for <a href="https://s2geometry.io/">S2 Geometry</a>. Shape factories
+ * for the given {@link SpatialContext} must implement the interface {@link S2ShapeFactory}.
+ *
+ * The tree can be configured on how it divided itself by providing an arity. The default arity is 1
+ * which divided every sub-cell in 4 (except the first level that is always divided by 6) . Arity 2
+ * divides sub-cells in 16 and arity 3 in 64 sub-cells.
+ *
+ * @lucene.experimental
+ */
+public class S2PrefixTree extends SpatialPrefixTree {
+
+
+ /**
+ * Factory for creating {@link S2PrefixTree} instances with useful defaults
+ */
+ protected static class Factory extends SpatialPrefixTreeFactory {
+
+ @Override
+ protected int getLevelForDistance(double degrees) {
+ S2PrefixTree grid = new S2PrefixTree(ctx, S2PrefixTree.getMaxLevels(1));
+ return grid.getLevelForDistance(degrees);
+ }
+
+ @Override
+ protected SpatialPrefixTree newSPT() {
+ return new S2PrefixTree(ctx,
+ maxLevels != null ? maxLevels : S2PrefixTree.getMaxLevels(1));
+ }
+
+ }
+
+ //factory to generate S2 cell shapes
+ protected final S2ShapeFactory s2ShapeFactory;
+ protected final int arity;
+
+ /**
+ * Creates a S2 spatial tree with arity 1.
+ *
+ * @param ctx The provided spatial context. The shape factor of the spatial context
+ * must implement {@link S2ShapeFactory}
+ * @param maxLevels The provided maximum level for this tree.
+ */
+ public S2PrefixTree(SpatialContext ctx, int maxLevels) {
+ this(ctx, maxLevels, 1);
+ }
+
+ /**
+ * Creates a S2 spatial tree with provided arity.
+ *
+ * @param ctx The provided spatial context. The shape factor of the spatial context
+ * must implement {@link S2ShapeFactory}
+ * @param maxLevels The provided maximum level for this tree.
+ * @param arity The arity of the tree.
+ */
+ public S2PrefixTree(SpatialContext ctx, int maxLevels, int arity) {
+ super(ctx, maxLevels);
+ if (!(ctx.getShapeFactory() instanceof S2ShapeFactory)) {
+ throw new IllegalArgumentException("Spatial context does not support S2 spatial index.");
+ }
+ this.s2ShapeFactory = (S2ShapeFactory) ctx.getShapeFactory();
+ if (arity <1 || arity > 3) {
+ throw new IllegalArgumentException("Invalid value for S2 tree arity. Possible values are 1, 2 or 3. Provided value is " + arity + ".");
+ }
+ this.arity = arity;
+ }
+
+ /**
+ * Get max levels for this spatial tree.
+ *
+ * @param arity The arity of the tree.
+ * @return The maximum number of levels by the provided arity.
+ */
+ public static int getMaxLevels(int arity) {
+ return S2CellId.MAX_LEVEL/arity + 1;
+ }
+
+ @Override
+ public int getLevelForDistance(double dist) {
+ if (dist == 0){
+ return maxLevels;
+ }
+ int level = S2Projections.MAX_WIDTH.getMinLevel(dist * DistanceUtils.DEGREES_TO_RADIANS);
+ int roundLevel = level % arity != 0 ? 1 : 0;
+ level = level/arity + roundLevel;
+ return Math.min(maxLevels, level + 1);
+ }
+
+ @Override
+ public double getDistanceForLevel(int level) {
+ if (level == 0) {
+ return 180;
+ }
+ return S2Projections.MAX_WIDTH.getValue(arity * (level - 1)) * DistanceUtils.RADIANS_TO_DEGREES;
+ }
+
+ @Override
+ public Cell getWorldCell() {
+ return new S2PrefixTreeCell(this, null);
+ }
+
+ @Override
+ public Cell readCell(BytesRef term, Cell scratch) {
+ S2PrefixTreeCell cell = (S2PrefixTreeCell) scratch;
+ if (cell == null) {
+ cell = (S2PrefixTreeCell) getWorldCell();
+ }
+ cell.readCell(this, term);
+ return cell;
+ }
+
+ @Override
+ public CellIterator getTreeCellIterator(Shape shape, int detailLevel) {
+ if (!(shape instanceof Point)) {
+ return super.getTreeCellIterator(shape, detailLevel);
+ }
+ Point p = (Point) shape;
+ S2CellId id = S2CellId.fromLatLng(S2LatLng.fromDegrees(p.getY(), p.getX())).parent(arity * (detailLevel - 1));
+ List<Cell> cells = new ArrayList<>(detailLevel);
+ for (int i=0; i < detailLevel - 1; i++) {
+ cells.add(new S2PrefixTreeCell(this, id.parent(i * arity)));
+ }
+ cells.add(new S2PrefixTreeCell(this, id));
+ return new FilterCellIterator(cells.iterator(), null);
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e3032dd3/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/S2PrefixTreeCell.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/S2PrefixTreeCell.java b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/S2PrefixTreeCell.java
new file mode 100644
index 0000000..63a728f
--- /dev/null
+++ b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/S2PrefixTreeCell.java
@@ -0,0 +1,289 @@
+/*
+ * 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.spatial.prefix.tree;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+
+import com.google.common.geometry.S2CellId;
+import org.apache.lucene.util.BytesRef;
+import org.locationtech.spatial4j.shape.Shape;
+import org.locationtech.spatial4j.shape.SpatialRelation;
+
+/**
+ * This class represents a S2 pixel in the RPT.
+ *
+ * @lucene.internal
+ */
+class S2PrefixTreeCell implements Cell {
+
+ //Faces of S2 Geometry
+ private static S2CellId[] FACES = new S2CellId[6];
+
+ static {
+ FACES[0] = S2CellId.fromFacePosLevel(0, 0, 0);
+ FACES[1] = S2CellId.fromFacePosLevel(1, 0, 0);
+ FACES[2] = S2CellId.fromFacePosLevel(2, 0, 0);
+ FACES[3] = S2CellId.fromFacePosLevel(3, 0, 0);
+ FACES[4] = S2CellId.fromFacePosLevel(4, 0, 0);
+ FACES[5] = S2CellId.fromFacePosLevel(5, 0, 0);
+ }
+
+ /*Special character to define a cell leaf*/
+ private static final byte LEAF = '+';
+ /*Tokens are used to serialize cells*/
+ private static final byte[] TOKENS = {'.', '/', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
+ 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
+ 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
+ /*Map containing mapping between tokens and integer values*/
+ private static final Map<Byte, Integer> PIXELS;
+
+ static {
+ PIXELS = new HashMap<>(TOKENS.length);
+ for (int i = 0; i < TOKENS.length; i++) {
+ PIXELS.put(TOKENS[i], i);
+ }
+ }
+
+ S2CellId cellId;
+ int level; //cache level
+ S2PrefixTree tree;
+
+ SpatialRelation shapeRel = null;
+ boolean isLeaf;
+ Shape shape = null;
+
+ S2PrefixTreeCell(S2PrefixTree tree, S2CellId cellId) {
+ this.cellId = cellId;
+ this.tree = tree;
+ setLevel();
+ if (getLevel() == tree.getMaxLevels()) {
+ setLeaf();
+ }
+ }
+
+ void readCell(S2PrefixTree tree, BytesRef ref) {
+ isLeaf = false;
+ shape = null;
+ shapeRel = null;
+ this.tree = tree;
+ cellId = getS2CellIdFromBytesRef(ref);
+ setLevel();
+ if (isLeaf(ref) || getLevel() == tree.getMaxLevels()) {
+ setLeaf();
+ }
+ }
+
+ @Override
+ public SpatialRelation getShapeRel() {
+ return shapeRel;
+ }
+
+ @Override
+ public void setShapeRel(SpatialRelation rel) {
+ shapeRel = rel;
+ }
+
+ @Override
+ public boolean isLeaf() {
+ return isLeaf;
+ }
+
+ @Override
+ public void setLeaf() {
+ isLeaf = true;
+ }
+
+ @Override
+ public BytesRef getTokenBytesWithLeaf(BytesRef result) {
+ result = getTokenBytesNoLeaf(result);
+ //max levels do not have leaf
+ if (isLeaf() && !(getLevel() == tree.getMaxLevels())) {
+ //Add leaf byte
+ result.bytes[result.offset + result.length] = LEAF;
+ result.length++;
+ }
+ return result;
+ }
+
+ @Override
+ public BytesRef getTokenBytesNoLeaf(BytesRef result) {
+ if (result == null) {
+ result = new BytesRef();
+ }
+ getBytesRefFromS2CellId(cellId, result);
+ return result;
+ }
+
+ @Override
+ public int getLevel() {
+ return this.level;
+ }
+
+ /**
+ * Cache level of cell.
+ */
+ private void setLevel() {
+ if (this.cellId == null) {
+ this.level = 0;
+ } else {
+ assert cellId.level() % tree.arity == 0;
+ this.level = (this.cellId.level() / tree.arity) + 1;
+ }
+ }
+
+ @Override
+ public CellIterator getNextLevelCells(Shape shapeFilter) {
+ S2CellId[] children;
+ if (cellId == null) { // this is the world cell
+ children = FACES;
+ } else {
+ int nChildren = (int) Math.pow(4, tree.arity);
+ children = new S2CellId[nChildren];
+ children[0] = cellId.childBegin(cellId.level() + tree.arity);
+ for (int i = 1; i < nChildren; i++) {
+ children[i] = children[i - 1].next();
+ }
+ }
+ List<Cell> cells = new ArrayList<>(children.length);
+ for (S2CellId pixel : children) {
+ cells.add(new S2PrefixTreeCell(tree, pixel));
+ }
+ return new FilterCellIterator(cells.iterator(), shapeFilter);
+ }
+
+ @Override
+ public Shape getShape() {
+ if (shape == null) {
+ if (cellId == null) { //World cell
+ shape = tree.getSpatialContext().getWorldBounds();
+ } else {
+ shape = tree.s2ShapeFactory.getS2CellShape(cellId);
+ }
+ }
+ return shape;
+ }
+
+ @Override
+ public boolean isPrefixOf(Cell c) {
+ if (cellId == null) {
+ return true;
+ }
+ S2PrefixTreeCell cell = (S2PrefixTreeCell) c;
+ return cellId.contains(cell.cellId);
+ }
+
+ @Override
+ public int compareToNoLeaf(Cell fromCell) {
+ if (cellId == null) {
+ return 1;
+ }
+ S2PrefixTreeCell cell = (S2PrefixTreeCell) fromCell;
+ return cellId.compareTo(cell.cellId);
+ }
+
+ /**
+ * Check if a cell is a leaf.
+ *
+ * @param ref The Byteref of the leaf
+ * @return true if it is a leaf, e.g last byte is the special Character.
+ */
+ private boolean isLeaf(BytesRef ref) {
+ return (ref.bytes[ref.offset + ref.length - 1] == LEAF);
+ }
+
+ /**
+ * Get the {@link S2CellId} from the {@link BytesRef} representation.
+ *
+ * @param ref The bytes.
+ * @return the corresponding S2 cell.
+ */
+ private S2CellId getS2CellIdFromBytesRef(BytesRef ref) {
+ int length = ref.length;
+ if (isLeaf(ref)) {
+ length--;
+ }
+ if (length == 0) {
+ return null; //world cell
+ }
+ int face = PIXELS.get(ref.bytes[ref.offset]);
+ S2CellId cellId = FACES[face];
+ long id = cellId.id();
+ for (int i = ref.offset + 1; i < ref.offset + length; i++) {
+ int thisLevel = i - ref.offset;
+ int pos = PIXELS.get(ref.bytes[i]);
+ // first child at level
+ id = id - (id & -id) + (1L << (2 * (S2CellId.MAX_LEVEL - thisLevel * tree.arity)));
+ // next until pos
+ id = id + pos * ((id & -id) << 1);
+ }
+ return new S2CellId(id);
+ }
+
+ /**
+ * Codify a {@link S2CellId} into its {@link BytesRef} representation.
+ *
+ * @param cellId The S2 Cell id to codify.
+ * @param bref The byteref representation.
+ */
+ private void getBytesRefFromS2CellId(S2CellId cellId, BytesRef bref) {
+ if (cellId == null) {//world cell
+ bref.length = 0;
+ return;
+ }
+ int length = getLevel() + 1;
+ byte[] b = bref.bytes.length >= length ? bref.bytes : new byte[length];
+ b[0] = TOKENS[cellId.face()];
+ for (int i = 1; i < getLevel(); i++) {
+ int offset = 0;
+ int level = tree.arity * i;
+ for (int j = 1; j < tree.arity; j++) {
+ offset = 4 * offset + cellId.childPosition(level - tree.arity + j);
+ }
+ b[i] = TOKENS[4 * offset + cellId.childPosition(level)];
+ }
+ bref.bytes = b;
+ bref.length = getLevel();
+ bref.offset = 0;
+ }
+
+ @Override
+ public int hashCode() {
+ if (cellId == null) {
+ return super.hashCode();
+ }
+ return this.cellId.hashCode();
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ S2PrefixTreeCell cell = (S2PrefixTreeCell) o;
+ return Objects.equals(cellId, cell.cellId);
+ }
+
+ @Override
+ public String toString() {
+ if (cellId == null) {
+ return "0";
+ }
+ return cellId.toString();
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e3032dd3/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/S2ShapeFactory.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/S2ShapeFactory.java b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/S2ShapeFactory.java
new file mode 100644
index 0000000..1306f60
--- /dev/null
+++ b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/S2ShapeFactory.java
@@ -0,0 +1,40 @@
+/*
+ * 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.spatial.prefix.tree;
+
+
+import com.google.common.geometry.S2CellId;
+import org.locationtech.spatial4j.shape.Shape;
+import org.locationtech.spatial4j.shape.ShapeFactory;
+
+/**
+ * Shape factory for Spatial contexts that support S2 geometry. It is an extension of
+ * Spatial4j {@link ShapeFactory}.
+ *
+ * @lucene.experimental
+ */
+public interface S2ShapeFactory extends ShapeFactory{
+
+ /**
+ * Factory method for S2 cell shapes.
+ *
+ * @param cellId The S2 cell id
+ * @return the shape representing the cell.
+ */
+ Shape getS2CellShape(S2CellId cellId);
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e3032dd3/lucene/spatial-extras/src/java/org/apache/lucene/spatial/spatial4j/Geo3dShapeFactory.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/java/org/apache/lucene/spatial/spatial4j/Geo3dShapeFactory.java b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/spatial4j/Geo3dShapeFactory.java
index 282d93b..a6147df 100644
--- a/lucene/spatial-extras/src/java/org/apache/lucene/spatial/spatial4j/Geo3dShapeFactory.java
+++ b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/spatial4j/Geo3dShapeFactory.java
@@ -20,6 +20,10 @@ package org.apache.lucene.spatial.spatial4j;
import java.util.ArrayList;
import java.util.List;
+import com.google.common.geometry.S2Cell;
+import com.google.common.geometry.S2CellId;
+import com.google.common.geometry.S2Point;
+import org.apache.lucene.spatial.prefix.tree.S2ShapeFactory;
import org.apache.lucene.spatial3d.geom.GeoBBox;
import org.apache.lucene.spatial3d.geom.GeoBBoxFactory;
import org.apache.lucene.spatial3d.geom.GeoCircle;
@@ -32,6 +36,7 @@ import org.apache.lucene.spatial3d.geom.GeoPointShape;
import org.apache.lucene.spatial3d.geom.GeoPointShapeFactory;
import org.apache.lucene.spatial3d.geom.GeoPolygon;
import org.apache.lucene.spatial3d.geom.GeoPolygonFactory;
+import org.apache.lucene.spatial3d.geom.GeoS2ShapeFactory;
import org.apache.lucene.spatial3d.geom.PlanetModel;
import org.locationtech.spatial4j.context.SpatialContext;
import org.locationtech.spatial4j.context.SpatialContextFactory;
@@ -42,14 +47,13 @@ import org.locationtech.spatial4j.shape.Point;
import org.locationtech.spatial4j.shape.Rectangle;
import org.locationtech.spatial4j.shape.Shape;
import org.locationtech.spatial4j.shape.ShapeCollection;
-import org.locationtech.spatial4j.shape.ShapeFactory;
/**
- * Geo3d implementation of {@link ShapeFactory}
+ * Geo3d implementation of {@link S2ShapeFactory}
*
* @lucene.experimental
*/
-public class Geo3dShapeFactory implements ShapeFactory {
+public class Geo3dShapeFactory implements S2ShapeFactory {
private final boolean normWrapLongitude;
private SpatialContext context;
@@ -237,6 +241,20 @@ public class Geo3dShapeFactory implements ShapeFactory {
return new Geo3dMultiPolygonBuilder();
}
+ @Override
+ public Shape getS2CellShape(S2CellId cellId) {
+ S2Cell cell = new S2Cell(cellId);
+ GeoPoint point1 = getGeoPoint(cell.getVertexRaw(0));
+ GeoPoint point2 = getGeoPoint(cell.getVertexRaw(1));
+ GeoPoint point3 = getGeoPoint(cell.getVertexRaw(2));
+ GeoPoint point4 = getGeoPoint(cell.getVertexRaw(3));
+ return new Geo3dShape<>(GeoS2ShapeFactory.makeGeoS2Shape(planetModel, point1, point2, point3, point4), context);
+ }
+
+ private GeoPoint getGeoPoint(S2Point point) {
+ return planetModel.createSurfacePoint(point.get(0), point.get(1), point.get(2));
+ }
+
/**
* Geo3d implementation of {@link org.locationtech.spatial4j.shape.ShapeFactory.PointsBuilder} interface to
* generate {@link GeoPoint}.
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e3032dd3/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/tree/S2PrefixTreeTest.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/tree/S2PrefixTreeTest.java b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/tree/S2PrefixTreeTest.java
new file mode 100644
index 0000000..f3bfe3e
--- /dev/null
+++ b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/tree/S2PrefixTreeTest.java
@@ -0,0 +1,113 @@
+/*
+ * 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.spatial.prefix.tree;
+
+import com.carrotsearch.randomizedtesting.annotations.Repeat;
+import com.google.common.geometry.S2CellId;
+import com.google.common.geometry.S2Projections;
+import org.apache.lucene.spatial.spatial4j.Geo3dSpatialContextFactory;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LuceneTestCase;
+import org.junit.Test;
+import org.locationtech.spatial4j.context.SpatialContext;
+import org.locationtech.spatial4j.shape.Point;
+
+/**
+ * Test for S2 Spatial prefix tree.
+ */
+public class S2PrefixTreeTest extends LuceneTestCase{
+
+ @Test
+ @Repeat(iterations = 10)
+ public void testCells() {
+ int face = random().nextInt(6);
+ S2CellId id = S2CellId.fromFacePosLevel(face, 0, 0);
+ int arity = random().nextInt(3) + 1;
+ int level = random().nextInt(S2PrefixTree.getMaxLevels(arity));
+ level = level * arity;
+ for (int i = 0; i < level; i++) {
+ int pos = random().nextInt(4);
+ id = id.childBegin();
+ if (pos == 0) continue;
+ id = id.next();
+ if (pos == 1) continue;
+ id = id.next();
+ if (pos == 2) continue;
+ id = id.next();
+ }
+ S2PrefixTree tree = new S2PrefixTree(new Geo3dSpatialContextFactory().newSpatialContext(), S2PrefixTree.getMaxLevels(arity), arity);
+ S2PrefixTreeCell cell = new S2PrefixTreeCell(tree, id);
+ BytesRef ref = cell.getTokenBytesWithLeaf(null);
+ if (random().nextBoolean()) {
+ int newOffset = random().nextInt(10) + 1;
+ byte[] newBytes = new byte[ref.bytes.length + newOffset];
+ for (int i = 0; i < ref.bytes.length; i++) {
+ newBytes[i + newOffset] = ref.bytes[i];
+ }
+ ref.bytes = newBytes;
+ ref.offset = ref.offset + newOffset;
+ }
+ S2PrefixTreeCell cell2 = new S2PrefixTreeCell(tree, null);
+ cell2.readCell(tree, ref);
+ assertEquals(cell, cell2);
+ }
+
+ @Test
+ @Repeat(iterations = 10)
+ public void testDistanceAndLevels() {
+ S2PrefixTree tree = new S2PrefixTree(new Geo3dSpatialContextFactory().newSpatialContext(), S2PrefixTree.getMaxLevels(1), 1);
+
+ double randomDist = random().nextDouble() * 5;
+ int levelDistance = tree.getLevelForDistance(randomDist);
+ double distanceLevel = tree.getDistanceForLevel(levelDistance);
+ assertTrue(randomDist > distanceLevel);
+
+
+ tree = new S2PrefixTree(new Geo3dSpatialContextFactory().newSpatialContext(), S2PrefixTree.getMaxLevels(2), 2);
+
+ levelDistance = tree.getLevelForDistance(randomDist);
+ distanceLevel = tree.getDistanceForLevel(levelDistance);
+ assertTrue(randomDist > distanceLevel);
+
+ tree = new S2PrefixTree(new Geo3dSpatialContextFactory().newSpatialContext(), S2PrefixTree.getMaxLevels(3), 3);
+
+ levelDistance = tree.getLevelForDistance(randomDist);
+ distanceLevel = tree.getDistanceForLevel(levelDistance);
+ assertTrue(randomDist > distanceLevel);
+
+ }
+
+ @Test
+ @Repeat(iterations = 10)
+ public void testPrecision() {
+ int arity = random().nextInt(3) +1;
+ SpatialContext context = new Geo3dSpatialContextFactory().newSpatialContext();
+ S2PrefixTree tree = new S2PrefixTree(context, S2PrefixTree.getMaxLevels(arity), arity);
+ double precision = random().nextDouble();
+ int level = tree.getLevelForDistance(precision);
+ Point point = context.getShapeFactory().pointXY(0, 0);
+ CellIterator iterator = tree.getTreeCellIterator(point, level);
+ S2PrefixTreeCell cell = null;
+ while (iterator.hasNext()) {
+ cell = (S2PrefixTreeCell)iterator.next();
+ }
+ assertTrue(cell.getLevel() == level);
+ double precisionCell = S2Projections.MAX_WIDTH.getValue(cell.cellId.level());
+ assertTrue(precision > precisionCell);
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e3032dd3/lucene/spatial-extras/src/test/org/apache/lucene/spatial/spatial4j/Geo3dRptTest.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/test/org/apache/lucene/spatial/spatial4j/Geo3dRptTest.java b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/spatial4j/Geo3dRptTest.java
index 0b29684..5160d74 100644
--- a/lucene/spatial-extras/src/test/org/apache/lucene/spatial/spatial4j/Geo3dRptTest.java
+++ b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/spatial4j/Geo3dRptTest.java
@@ -25,6 +25,8 @@ import org.apache.lucene.spatial.composite.CompositeSpatialStrategy;
import org.apache.lucene.spatial.prefix.RandomSpatialOpStrategyTestCase;
import org.apache.lucene.spatial.prefix.RecursivePrefixTreeStrategy;
import org.apache.lucene.spatial.prefix.tree.GeohashPrefixTree;
+import org.apache.lucene.spatial.prefix.tree.QuadPrefixTree;
+import org.apache.lucene.spatial.prefix.tree.S2PrefixTree;
import org.apache.lucene.spatial.prefix.tree.SpatialPrefixTree;
import org.apache.lucene.spatial.query.SpatialOperation;
import org.apache.lucene.spatial.serialized.SerializedDVStrategy;
@@ -32,6 +34,7 @@ import org.apache.lucene.spatial3d.geom.GeoAreaShape;
import org.apache.lucene.spatial3d.geom.GeoPath;
import org.apache.lucene.spatial3d.geom.GeoPathFactory;
import org.apache.lucene.spatial3d.geom.GeoPoint;
+import org.apache.lucene.spatial3d.geom.GeoPointShape;
import org.apache.lucene.spatial3d.geom.GeoPolygonFactory;
import org.apache.lucene.spatial3d.geom.PlanetModel;
import org.apache.lucene.spatial3d.geom.RandomGeo3dShapeGenerator;
@@ -49,9 +52,21 @@ public class Geo3dRptTest extends RandomSpatialOpStrategyTestCase {
private SpatialPrefixTree grid;
private RecursivePrefixTreeStrategy rptStrategy;
- private void setupGeohashGrid() {
- this.grid = new GeohashPrefixTree(ctx, 2);//A fairly shallow grid
- this.rptStrategy = newRPT();
+ private void setupGrid() {
+ int type = random().nextInt(4);
+ if (type == 0) {
+ this.grid = new GeohashPrefixTree(ctx, 2);
+ this.rptStrategy = newRPT();
+ } else if (type == 1) {
+ this.grid = new QuadPrefixTree(ctx, 5);
+ this.rptStrategy = newRPT();
+ }
+ else {
+ int arity = random().nextInt(3) + 1;
+ this.grid = new S2PrefixTree(ctx, 5 - arity, arity);
+ this.rptStrategy = newRPT();
+ this.rptStrategy.setPruneLeafyBranches(false);
+ }
}
protected RecursivePrefixTreeStrategy newRPT() {
@@ -68,7 +83,7 @@ public class Geo3dRptTest extends RandomSpatialOpStrategyTestCase {
factory.planetModel = planetModel;
ctx = factory.newSpatialContext();
- setupGeohashGrid();
+ setupGrid();
SerializedDVStrategy serializedDVStrategy = new SerializedDVStrategy(ctx, getClass().getSimpleName() + "_sdv");
this.strategy = new CompositeSpatialStrategy("composite_" + getClass().getSimpleName(),
@@ -99,10 +114,10 @@ public class Geo3dRptTest extends RandomSpatialOpStrategyTestCase {
points.add(new GeoPoint(planetModel, 14 * DEGREES_TO_RADIANS, -180 * DEGREES_TO_RADIANS));
points.add(new GeoPoint(planetModel, -15 * DEGREES_TO_RADIANS, 153 * DEGREES_TO_RADIANS));
final GeoPoint[] pathPoints = new GeoPoint[] {
- new GeoPoint(planetModel, 55.0 * DEGREES_TO_RADIANS, -26.0 * DEGREES_TO_RADIANS),
- new GeoPoint(planetModel, -90.0 * DEGREES_TO_RADIANS, 0.0),
- new GeoPoint(planetModel, 54.0 * DEGREES_TO_RADIANS, 165.0 * DEGREES_TO_RADIANS),
- new GeoPoint(planetModel, -90.0 * DEGREES_TO_RADIANS, 0.0)};
+ new GeoPoint(planetModel, 55.0 * DEGREES_TO_RADIANS, -26.0 * DEGREES_TO_RADIANS),
+ new GeoPoint(planetModel, -90.0 * DEGREES_TO_RADIANS, 0.0),
+ new GeoPoint(planetModel, 54.0 * DEGREES_TO_RADIANS, 165.0 * DEGREES_TO_RADIANS),
+ new GeoPoint(planetModel, -90.0 * DEGREES_TO_RADIANS, 0.0)};
final GeoPath path = GeoPathFactory.makeGeoPath(planetModel, 29 * DEGREES_TO_RADIANS, pathPoints);
final Shape shape = new Geo3dShape(path,ctx);
final Rectangle rect = ctx.makeRectangle(131, 143, 39, 54);
@@ -110,7 +125,7 @@ public class Geo3dRptTest extends RandomSpatialOpStrategyTestCase {
}
@Test
- @Repeat(iterations = 10)
+ @Repeat(iterations = 30)
public void testOperations() throws IOException {
setupStrategy();
@@ -121,6 +136,9 @@ public class Geo3dRptTest extends RandomSpatialOpStrategyTestCase {
protected Shape randomIndexedShape() {
int type = shapeGenerator.randomShapeType();
GeoAreaShape areaShape = shapeGenerator.randomGeoAreaShape(type, planetModel);
+ if (areaShape instanceof GeoPointShape) {
+ return new Geo3dPointShape((GeoPointShape) areaShape, ctx);
+ }
return new Geo3dShape<>(areaShape, ctx);
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e3032dd3/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoS2Shape.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoS2Shape.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoS2Shape.java
new file mode 100644
index 0000000..b4c5d06
--- /dev/null
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoS2Shape.java
@@ -0,0 +1,202 @@
+/*
+ * 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.geom;
+
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.OutputStream;
+
+/**
+ * Fast implementation of a polygon representing S2 geometry cell. There are no checks validating that
+ * points are convex therefore users must be provide four points in CCW or the logic will fail.
+ *
+ * @lucene.internal
+ */
+class GeoS2Shape extends GeoBasePolygon {
+
+ /** The first point */
+ protected final GeoPoint point1;
+ /** The second point */
+ protected final GeoPoint point2;
+ /** The third point */
+ protected final GeoPoint point3;
+ /** The fourth point */
+ protected final GeoPoint point4;
+
+ /** The first plane */
+ protected final SidedPlane plane1;
+ /** The second plane */
+ protected final SidedPlane plane2;
+ /** The third plane */
+ protected final SidedPlane plane3;
+ /** The fourth plane */
+ protected final SidedPlane plane4;
+
+ /** Notable points for the first plane */
+ protected final GeoPoint[] plane1Points;
+ /** Notable points for second plane */
+ protected final GeoPoint[] plane2Points;
+ /** Notable points for third plane */
+ protected final GeoPoint[] plane3Points;
+ /** Notable points for fourth plane */
+ protected final GeoPoint[] plane4Points;
+
+ /** Edge point for this S2 cell */
+ protected final GeoPoint[] edgePoints;
+
+ /**
+ * It builds from 4 points given in CCW. It must be convex or logic will fail.
+ *
+ *@param planetModel is the planet model.
+ *@param point1 the first point.
+ *@param point2 the second point.
+ *@param point3 the third point.
+ *@param point4 the four point.
+ */
+ public GeoS2Shape(final PlanetModel planetModel, GeoPoint point1, GeoPoint point2, GeoPoint point3, GeoPoint point4) {
+ super(planetModel);
+ this.point1 = point1;
+ this.point2 = point2;
+ this.point3 = point3;
+ this.point4 = point4;
+
+ // Now build the four planes
+ this.plane1 = new SidedPlane(point4, point1, point2);
+ this.plane2 = new SidedPlane(point1, point2, point3);
+ this.plane3 = new SidedPlane(point2, point3, point4);
+ this.plane4 = new SidedPlane(point3, point4, point1);
+
+ //collect the notable points for the planes
+ this.plane1Points = new GeoPoint[]{point1, point2};
+ this.plane2Points = new GeoPoint[]{point2, point3};
+ this.plane3Points = new GeoPoint[]{point3, point4};
+ this.plane4Points = new GeoPoint[]{point4, point1};
+
+ this.edgePoints = new GeoPoint[]{point1};
+ }
+
+ /**
+ * Constructor for deserialization.
+ * @param planetModel is the planet model.
+ * @param inputStream is the input stream.
+ */
+ public GeoS2Shape(final PlanetModel planetModel, final InputStream inputStream) throws IOException {
+ this(planetModel,
+ (GeoPoint) SerializableObject.readObject(inputStream),
+ (GeoPoint) SerializableObject.readObject(inputStream),
+ (GeoPoint) SerializableObject.readObject(inputStream),
+ (GeoPoint) SerializableObject.readObject(inputStream));
+ }
+
+ @Override
+ public void write(final OutputStream outputStream) throws IOException {
+ SerializableObject.writeObject(outputStream, point1);
+ SerializableObject.writeObject(outputStream, point2);
+ SerializableObject.writeObject(outputStream, point3);
+ SerializableObject.writeObject(outputStream, point4);
+ }
+
+
+ @Override
+ public boolean isWithin(final double x, final double y, final double z) {
+ return plane1.isWithin(x, y, z) &&
+ plane2.isWithin(x, y, z) &&
+ plane3.isWithin(x, y, z) &&
+ plane4.isWithin(x, y, z);
+ }
+
+
+ @Override
+ public GeoPoint[] getEdgePoints() {
+ return edgePoints;
+ }
+
+ @Override
+ public boolean intersects(final Plane p, final GeoPoint[] notablePoints, final Membership... bounds) {
+ return p.intersects(planetModel, plane1, notablePoints, plane1Points, bounds, plane2, plane4) ||
+ p.intersects(planetModel, plane2, notablePoints, plane2Points, bounds, plane3, plane1) ||
+ p.intersects(planetModel, plane3, notablePoints, plane3Points, bounds, plane4, plane2) ||
+ p.intersects(planetModel, plane4, notablePoints, plane4Points, bounds, plane1, plane3);
+ }
+
+ @Override
+ public boolean intersects(GeoShape geoShape) {
+ return geoShape.intersects(plane1, plane1Points, plane2, plane4) ||
+ geoShape.intersects(plane2, plane2Points, plane3, plane1) ||
+ geoShape.intersects(plane3, plane3Points, plane4, plane2) ||
+ geoShape.intersects(plane4, plane4Points, plane1, plane3);
+ }
+
+ @Override
+ public void getBounds(Bounds bounds) {
+ super.getBounds(bounds);
+ bounds.addPlane(planetModel, plane1, plane2, plane4)
+ .addPlane(planetModel, plane2, plane3, plane1)
+ .addPlane(planetModel, plane3, plane4, plane2)
+ .addPlane(planetModel, plane4, plane1, plane3)
+ .addPoint(point1).addPoint(point2).addPoint(point3).addPoint(point4);
+ }
+
+ @Override
+ public double outsideDistance(DistanceStyle distanceStyle, double x, double y, double z) {
+ final double planeDistance1 = distanceStyle.computeDistance(planetModel, plane1, x,y,z, plane2, plane4);
+ final double planeDistance2 = distanceStyle.computeDistance(planetModel, plane2, x,y,z, plane3, plane1);
+ final double planeDistance3 = distanceStyle.computeDistance(planetModel, plane3, x,y,z, plane4, plane2);
+ final double planeDistance4 = distanceStyle.computeDistance(planetModel, plane4, x,y,z, plane1, plane3);
+
+ final double pointDistance1 = distanceStyle.computeDistance(point1, x,y,z);
+ final double pointDistance2 = distanceStyle.computeDistance(point2, x,y,z);
+ final double pointDistance3 = distanceStyle.computeDistance(point3, x,y,z);
+ final double pointDistance4 = distanceStyle.computeDistance(point4, x,y,z);
+
+ return Math.min(
+ Math.min(
+ Math.min(planeDistance1, planeDistance2),
+ Math.min(planeDistance3, planeDistance4)),
+ Math.min(
+ Math.min(pointDistance1, pointDistance2),
+ Math.min(pointDistance3, pointDistance4)));
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (!(o instanceof GeoS2Shape))
+ return false;
+ GeoS2Shape other = (GeoS2Shape) o;
+ return super.equals(other) && other.point1.equals(point1)
+ && other.point2.equals(point2) && other.point3.equals(point3)
+ && other.point4.equals(point4);
+ }
+
+ @Override
+ public int hashCode() {
+ int result = super.hashCode();
+ result = 31 * result + point1.hashCode();
+ result = 31 * result + point2.hashCode();
+ result = 31 * result + point3.hashCode();
+ result = 31 * result + point4.hashCode();
+ return result;
+ }
+
+ @Override
+ public String toString() {
+ return "GeoS2Shape: {planetmodel="+planetModel+", point1=" + point1 +", point2=" + point2 +", point3=" + point3 +", point4=" + point4+ "}";
+ }
+
+}
+
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e3032dd3/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoS2ShapeFactory.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoS2ShapeFactory.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoS2ShapeFactory.java
new file mode 100644
index 0000000..848b2e6
--- /dev/null
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoS2ShapeFactory.java
@@ -0,0 +1,50 @@
+/*
+ * 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.geom;
+
+/**
+ * Class which constructs a GeoPolygon representing S2 google pixel.
+ *
+ * @lucene.experimental
+ */
+public class GeoS2ShapeFactory {
+
+ private GeoS2ShapeFactory() {
+ }
+
+ /**
+ * Creates a convex polygon with 4 planes by providing 4 points in CCW.
+ * This is a very fast shape and there are no checks that the points currently define
+ * a convex shape.
+ *
+ * @param planetModel The planet model
+ * @param point1 the first point.
+ * @param point2 the second point.
+ * @param point3 the third point.
+ * @param point4 the four point.
+ * @return the generated shape.
+ */
+ public static GeoPolygon makeGeoS2Shape(final PlanetModel planetModel,
+ final GeoPoint point1,
+ final GeoPoint point2,
+ final GeoPoint point3,
+ final GeoPoint point4) {
+ return new GeoS2Shape(planetModel, point1, point2, point3, point4);
+ }
+}
+
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e3032dd3/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/StandardObjects.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/StandardObjects.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/StandardObjects.java
index bcebf43..4e0acae 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/StandardObjects.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/StandardObjects.java
@@ -75,6 +75,7 @@ class StandardObjects {
classRegsitry.put(PlanetModel.class, 35);
classRegsitry.put(GeoDegeneratePath.class, 36);
classRegsitry.put(GeoExactCircle.class, 37);
+ classRegsitry.put(GeoS2Shape.class, 38);
for (Class<?> clazz : classRegsitry.keySet()){
codeRegsitry.put(classRegsitry.get(clazz), clazz);