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();

    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