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=16320916#comment-16320916
] 

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_r160769685
  
    --- 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];
    +        b[0] = TOKENS[cellId.face()];
    +        for (int i =1; i < getLevel(); i++) {
    +            b[i] = TOKENS[cellId.childPosition(i)];
    +        }
    +        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;
    +        if (cellId == null) {
    --- End diff --
    
    see Objects.equals(...)


> 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