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
 
// Forward declarations
namespace geos {
namespace geom {
class Coordinate;
class Envelope;
}
}
 
using geos::geom::Coordinate;
using geos::geom::Envelope;
 
 
namespace geos {
namespace triangulate {
namespace polygon {
 
 
class GEOS_DLL VertexSequencePackedRtree {
 
private:
 
 
    static constexpr std::size_t NODE_CAPACITY = 16;
 
    // Members
    const std::vector<Coordinate>& 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 std::vector<Coordinate>& 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 std::vector<Coordinate>& 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.triangulate.polygon
} // namespace geos.triangulate
} // namespace geos