VertexSequencePackedRtree.h

/**********************************************************************
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.osgeo.org
 *
 * Copyright (C) 2020 Paul Ramsey <pramsey@cleverelephant.ca>
 *
 * This is free software; you can redistribute and/or modify it under
 * the terms of the GNU Lesser General Public Licence as published
 * by the Free Software Foundation.
 * See the COPYING file for more information.
 *
 **********************************************************************/
 
#pragma once
 
#include <geos/export.h>
#include <vector>
 
// Forward declarations
namespace geos {
namespace geom {
class Coordinate;
class CoordinateSequence;
class Envelope;
}
}
 
namespace geos {
namespace index {
 
 
class GEOS_DLL VertexSequencePackedRtree {
    using Coordinate = geos::geom::Coordinate;
    using CoordinateSequence = geos::geom::CoordinateSequence;
    using Envelope = geos::geom::Envelope;
 
private:
 
 
    static constexpr std::size_t NODE_CAPACITY = 16;
 
    // Members
    const CoordinateSequence& items;
    std::vector<bool> removedItems;
    std::vector<std::size_t> levelOffset;
    std::size_t nodeCapacity = NODE_CAPACITY;
    std::vector<Envelope> bounds;
 
 
    // Methods
 
    void build();
 
    std::vector<std::size_t> computeLevelOffsets();
 
    static std::size_t ceilDivisor(std::size_t num, std::size_t denom);
    static std::size_t clampMax(std::size_t x, std::size_t max);
 
    std::size_t levelNodeCount(std::size_t numNodes);
 
    std::vector<Envelope> createBounds();
 
    void fillItemBounds(std::vector<Envelope>& bounds);
    void fillLevelBounds(std::size_t lvl, std::vector<Envelope>& bounds);
 
    static Envelope computeNodeEnvelope(const std::vector<Envelope>& bounds,
        std::size_t start, std::size_t end);
    static Envelope computeItemEnvelope(const CoordinateSequence& items,
        std::size_t start, std::size_t end);
 
    void queryNode(const Envelope& queryEnv,
        std::size_t level, std::size_t nodeIndex,
        std::vector<std::size_t>& result) const;
    void queryNodeRange(const Envelope& queryEnv,
        std::size_t level, std::size_t nodeStartIndex,
        std::vector<std::size_t>& result) const;
    void queryItemRange(const Envelope& queryEnv, std::size_t itemIndex,
        std::vector<std::size_t>& result) const;
 
    std::size_t levelSize(std::size_t level) const;
    bool isNodeEmpty(std::size_t level, std::size_t index);
    bool isItemsNodeEmpty(std::size_t nodeIndex);
 
 
public:
 
    VertexSequencePackedRtree(const CoordinateSequence& pts);
 
    std::vector<Envelope> getBounds();
 
    void remove(std::size_t index);
 
    void query(const Envelope& queryEnv, std::vector<std::size_t>& result) const;
 
};
 
 
 
} // namespace geos.index
} // namespace geos