lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "ASF GitHub Bot (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry
Date Wed, 10 Jan 2018 19:23:01 GMT

    [ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16320909#comment-16320909
] 

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_r160766117
  
    --- 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);
    --- End diff --
    
    I think you meant to cache to this.shape instead?


> 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: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org


Mime
View raw message