ConcaveHullOfPolygons.h

/**********************************************************************
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.osgeo.org
 *
 * Copyright (C) 2022 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/triangulate/tri/TriList.h>
 
#include <set>
#include <deque>
#include <map>
 
namespace geos {
namespace geom {
class Coordinate;
class CoordinateSequence;
class Envelope;
class Geometry;
class GeometryCollection;
class GeometryFactory;
class LinearRing;
class Polygon;
}
namespace triangulate {
namespace tri {
class Tri;
}
}
}
 
#include <geos/triangulate/tri/Tri.h>
 
 
using geos::geom::Coordinate;
using geos::geom::CoordinateSequence;
using geos::geom::Envelope;
using geos::geom::Geometry;
using geos::geom::GeometryCollection;
using geos::geom::GeometryFactory;
using geos::geom::LinearRing;
using geos::geom::Polygon;
using geos::triangulate::tri::Tri;
using geos::triangulate::tri::TriList;
 
 
namespace geos {
namespace algorithm { // geos::algorithm
namespace hull {      // geos::algorithm::hull
 
 
class GEOS_DLL ConcaveHullOfPolygons {
 
private:
 
    /* Members */
 
    static constexpr int FRAME_EXPAND_FACTOR = 4;
 
    const Geometry* inputPolygons;
    const GeometryFactory* geomFactory;
    double maxEdgeLength;
    double maxEdgeLengthRatio;
    bool isHolesAllowed;
    bool isTight;
 
    std::set<Tri*> hullTris;
    std::deque<Tri*> borderTriQue;
    std::vector<const LinearRing*> polygonRings;
    TriList<Tri> triList;
 
    std::map<Tri*, TriIndex> borderEdgeMap;
 
    /* Methods */
 
    std::unique_ptr<Geometry> createEmptyHull();
 
    static void extractShellRings(
        const Geometry* polygons,
        std::vector<const LinearRing*>& rings);
 
    void buildHullTris();
 
    std::unique_ptr<Polygon> createFrame(
        const Envelope* polygonsEnv);
 
    double computeTargetEdgeLength(
        TriList<Tri>& triList,
        const CoordinateSequence* frameCorners,
        double edgeLengthRatio) const;
 
    bool isFrameTri(
        const Tri* tri,
        const CoordinateSequence* frameCorners) const;
 
    void removeFrameCornerTris(
        TriList<Tri>& tris,
        const CoordinateSequence* frameCorners);
 
    TriIndex vertexIndex(
        const Tri* tri,
        const CoordinateSequence* pts) const;
 
    void removeBorderTris();
 
    void removeHoleTris();
 
    Tri* findHoleSeedTri() const;
 
    bool isHoleSeedTri(const Tri* tri) const;
 
    bool isBorderTri(const Tri* tri) const;
 
    bool isRemovable(const Tri* tri) const;
 
    bool isTouchingSinglePolygon(const Tri* tri) const;
 
    void addBorderTris(Tri* tri);
 
    void addBorderTri(Tri* tri, TriIndex index);
 
    void removeBorderTri(Tri* tri);
 
    bool hasAllVertices(const LinearRing* ring, const Tri* tri) const;
 
    bool hasVertex(const LinearRing* ring, const Coordinate& v) const;
 
    void envelope(const Tri* tri, Envelope& env) const;
 
    std::unique_ptr<Geometry> createHullGeometry(bool isIncludeInput);
 
 
public:
 
    static std::unique_ptr<Geometry>
    concaveHullByLength(const Geometry* polygons, double maxLength);
 
    static std::unique_ptr<Geometry>
    concaveHullByLength(
        const Geometry* polygons, double maxLength,
        bool isTight, bool isHolesAllowed);
 
    static std::unique_ptr<Geometry>
    concaveHullByLengthRatio(const Geometry* polygons, double lengthRatio);
 
    static std::unique_ptr<Geometry>
    concaveHullByLengthRatio(
        const Geometry* polygons, double lengthRatio,
        bool isTight, bool isHolesAllowed);
 
    static std::unique_ptr<Geometry>
    concaveFillByLength(const Geometry* polygons, double maxLength);
 
    static std::unique_ptr<Geometry>
    concaveFillByLengthRatio(const Geometry* polygons, double lengthRatio);
 
    ConcaveHullOfPolygons(const Geometry* geom);
 
    void setMaximumEdgeLength(double edgeLength);
 
    void setMaximumEdgeLengthRatio(double edgeLengthRatio);
 
    void setHolesAllowed(bool p_isHolesAllowed);
 
    void setTight(bool p_isTight);
 
    std::unique_ptr<Geometry> getHull();
 
    std::unique_ptr<Geometry> getFill();
 
 
};
 
 
 
} // geos::algorithm::hull
} // geos::algorithm
} // geos