RingHull.h

/**********************************************************************
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.osgeo.org
 *
 * Copyright (C) 2021 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/geom/Coordinate.h>
#include <geos/simplify/LinkedRing.h>
#include <geos/index/VertexSequencePackedRtree.h>
 
#include <queue>
 
namespace geos {
namespace geom {
class Envelope;
class LinearRing;
class LineString;
class Polygon;
}
namespace simplify {
class RingHullIndex;
}
}
 
namespace geos {
namespace simplify { // geos::simplify
 
 
class RingHull
{
    using Coordinate = geos::geom::Coordinate;
    using CoordinateSequence = geos::geom::CoordinateSequence;
    using Envelope = geos::geom::Envelope;
    using LinearRing = geos::geom::LinearRing;
    using LineString = geos::geom::LineString;
    using Polygon = geos::geom::Polygon;
    using VertexSequencePackedRtree = geos::index::VertexSequencePackedRtree;
 
 
public:
 
    /*
    * Creates a new instance.
    *
    * @param p_ring the ring vertices to process
    * @param p_isOuter whether the hull is outer or inner
    */
    RingHull(const LinearRing* p_ring, bool p_isOuter);
 
    void setMinVertexNum(std::size_t minVertexNum);
 
    void setMaxAreaDelta(double maxAreaDelta);
 
    const Envelope* getEnvelope() const;
 
    std::unique_ptr<LinearRing> getHull(RingHullIndex& hullIndex);
 
    static bool isConvex(const LinkedRing& vertexRing, std::size_t index);
 
    static double area(const LinkedRing& vertexRing, std::size_t index);
 
    void compute(RingHullIndex& hullIndex);
 
    std::unique_ptr<Polygon> toGeometry() const;
 
 
private:
 
 
    class Corner
    {
 
    private:
 
        std::size_t index;
        std::size_t prev;
        std::size_t next;
        double area;
 
    public:
 
        Corner(std::size_t p_idx, std::size_t p_prev, std::size_t p_next, double p_area)
            : index(p_idx)
            , prev(p_prev)
            , next(p_next)
            , area(p_area)
            {};
 
        inline int compareTo(const Corner& rhs) const {
            if (area == rhs.getArea()) {
                if (index == rhs.getIndex())
                    return 0;
                else return index < rhs.getIndex() ? -1 : 1;
            }
            else return area < rhs.getArea() ? -1 : 1;
        }
 
        inline bool operator< (const Corner& rhs) const {
            return compareTo(rhs) < 0;
        };
 
        inline bool operator> (const Corner& rhs) const {
            return compareTo(rhs) > 0;
        };
 
        inline bool operator==(const Corner& rhs) const {
            return compareTo(rhs) == 0;
        };
 
        bool isVertex(std::size_t p_index) const;
        std::size_t getIndex() const;
        double getArea() const;
        void envelope(const LinkedRing& ring, Envelope& env) const;
        bool intersects(const Coordinate& v, const LinkedRing& ring) const;
        bool isRemoved(const LinkedRing& ring) const;
        std::unique_ptr<LineString> toLineString(const LinkedRing& ring);
 
        struct Greater {
            inline bool operator()(const Corner & a, const Corner & b) const {
                return a > b;
            }
        };
 
        using PriorityQueue = std::priority_queue<Corner, std::vector<Corner>, Corner::Greater>;
 
    }; // class Corner
 
 
 
    const LinearRing* inputRing;
    double targetVertexNum = -1.0;
    double targetAreaDelta = -1.0;
 
    std::unique_ptr<CoordinateSequence> vertex;
    std::unique_ptr<LinkedRing> vertexRing;
    double areaDelta = 0;
 
    std::unique_ptr<VertexSequencePackedRtree> vertexIndex;
 
    Corner::PriorityQueue cornerQueue;
 
 
    void init(CoordinateSequence& ring, bool isOuter);
    void addCorner(std::size_t i, Corner::PriorityQueue& cornerQueue);
    bool isAtTarget(const Corner& corner);
 
    void removeCorner(const Corner& corner, Corner::PriorityQueue& cornerQueue);
    bool isRemovable(const Corner& corner, const RingHullIndex& hullIndex) const;
 
    bool hasIntersectingVertex(
        const Corner& corner,
        const Envelope& cornerEnv,
        const RingHull* hull) const;
 
    const Coordinate& getCoordinate(std::size_t index) const;
 
    void query(
        const Envelope& cornerEnv,
        std::vector<std::size_t>& result) const;
 
    void queryHull(const Envelope& queryEnv, std::vector<Coordinate>& pts);
 
 
 
 
}; // RingHull
 
 
} // geos::simplify
} // geos