[
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16320915#comment-16320915
]
ASF GitHub Bot commented on LUCENE-8126:
----------------------------------------
Github user dsmiley commented on a diff in the pull request:
https://github.com/apache/lucene-solr/pull/302#discussion_r160769274
--- Diff:
lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/S2PrefixTreeCell.java
---
@@ -0,0 +1,285 @@
+/*
+ * 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 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;
+ /*Map containing mapping between tokens and integer values*/
+ private static final Map<Byte,Integer> PIXELS;
+ static {
+ TOKENS = new byte[]{'0', '1', '2', '3', '4', '5'};
+ PIXELS = new HashMap<>(6);
+ PIXELS.put(TOKENS[0], 0);
+ PIXELS.put(TOKENS[1], 1);
+ PIXELS.put(TOKENS[2], 2);
+ PIXELS.put(TOKENS[3], 3);
+ PIXELS.put(TOKENS[4], 4);
+ PIXELS.put(TOKENS[5], 5);
+ }
+
+ 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 {
+ this.level = this.cellId.level() + 1;
+ }
+ }
+
+ @Override
+ public CellIterator getNextLevelCells(Shape shapeFilter) {
+ S2CellId[] children;
+ if (cellId == null){ // this is the world cell
+ children = FACES;
+ }
+ else {
+ children = new S2CellId[4];
+ children[0] = cellId.childBegin();
+ children[1] = children[0].next();
+ children[2] = children[1].next();
+ children[3] = children[2].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
+ return tree.getSpatialContext().getWorldBounds();
+ }
+ return 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];
+ //we will do it directly with cell ids for performance
+ long id = cellId.id();
+ for (int i=ref.offset+1; i<ref.offset + length; i++){
+ int pos = PIXELS.get(ref.bytes[i]);
+ long oldLsb = id & -id;
+ id = id - oldLsb + (oldLsb >>> 2);
+ 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 = new byte[length];
--- End diff --
the bref parameter may already have bytes that is of this length. If it
is, reuse it thus avoiding object allocation. BytesRef exists to avoid object
allocation and copying.
> Spatial prefix tree based on S2 geometry
> ----------------------------------------
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
> Issue Type: New Feature
> Components: modules/spatial-extras
> Reporter: Ignacio Vera
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very
> promising results, in particular for complex shapes (e.g polygons). Using
> this pixelization scheme reduces the size of the index, improves the
> performance of the queries and reduces the loading time for non-point shapes.
> If you are ok with this contribution and before providing any code I would
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree
> and create shapes from S2 cells (basically port what we need from the library
> into Lucene).
> What do you think?
--
This message was sent by Atlassian JIRA
(v6.4.14#64029)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
