ConcaveHull.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/Triangle.h>
#include <geos/triangulate/tri/Tri.h>
#include <geos/triangulate/tri/TriList.h>
#include <geos/triangulate/quadedge/TriangleVisitor.h>
#include <geos/algorithm/hull/HullTri.h>
 
#include <queue>
#include <deque>
 
namespace geos {
namespace geom {
class Coordinate;
class Geometry;
class GeometryFactory;
}
namespace triangulate {
namespace quadedge {
class Quadedge;
class QuadEdgeSubdivision;
}
}
}
 
namespace geos {
namespace algorithm { // geos::algorithm
namespace hull {      // geos::algorithm::hull
 
 
typedef std::priority_queue<HullTri*, std::vector<HullTri*>, HullTri::HullTriCompare> HullTriQueue;
 
 
class GEOS_DLL ConcaveHull {
    using Coordinate = geos::geom::Coordinate;
    using Geometry = geos::geom::Geometry;
    using GeometryFactory = geos::geom::GeometryFactory;
    using Triangle = geos::geom::Triangle;
    using QuadEdge = geos::triangulate::quadedge::QuadEdge;
    using QuadEdgeSubdivision = geos::triangulate::quadedge::QuadEdgeSubdivision;
    using Tri = geos::triangulate::tri::Tri;
    template<typename TriType>
    using TriList = geos::triangulate::tri::TriList<TriType>;
 
public:
 
    ConcaveHull(const Geometry* geom);
 
    static double uniformEdgeLength(const Geometry* geom);
 
    static std::unique_ptr<Geometry> concaveHullByLength(
        const Geometry* geom, double maxLength);
 
    static std::unique_ptr<Geometry> concaveHullByLength(
        const Geometry* geom, double maxLength, bool isHolesAllowed);
 
    static std::unique_ptr<Geometry> concaveHullByLengthRatio(
        const Geometry* geom, double lengthRatio);
 
    static std::unique_ptr<Geometry> concaveHullByLengthRatio(
        const Geometry* geom,
        double lengthRatio,
        bool isHolesAllowed);
 
    static std::unique_ptr<Geometry> alphaShape(
        const Geometry* geom,
        double alpha,
        bool isHolesAllowed);
 
    void setMaximumEdgeLength(double edgeLength);
 
    void setMaximumEdgeLengthRatio(double edgeLengthRatio);
 
    void setHolesAllowed(bool holesAllowed);
 
    void setAlpha(double newAlpha);
 
    std::unique_ptr<Geometry> getHull();
 
 
private:
 
    // Constants
    static constexpr int PARAM_EDGE_LENGTH = 1;
    static constexpr int PARAM_ALPHA = 2;
 
    // Members
    const Geometry* inputGeometry;
    double maxEdgeLengthRatio;
    double alpha;
    bool isHolesAllowed;
    int criteriaType;
    double maxSizeInHull;
    const GeometryFactory* geomFactory;
 
    // Methods
    static double computeTargetEdgeLength(
        TriList<HullTri>& triList,
        double edgeLengthFactor);
 
    void computeHull(TriList<HullTri>& triList);
    void computeHullBorder(TriList<HullTri>& triList);
    void createBorderQueue(HullTriQueue& queue, TriList<HullTri>& triList);
 
    void addBorderTri(HullTri* tri, HullTriQueue& queue);
    void computeHullHoles(TriList<HullTri>& triList);
    void setSize(HullTri* tri);
 
 
    static std::vector<HullTri*> findCandidateHoles(
        TriList<HullTri>& triList, double maxSizeInHull);
 
    void removeHole(TriList<HullTri>& triList, HullTri* triHole);
    void setSize(TriList<HullTri>& triList);
 
    bool isInHull(const HullTri* tri) const;
 
    bool isRemovableBorder(const HullTri* tri) const;
    bool isRemovableHole(const HullTri* tri) const;
 
    std::unique_ptr<Geometry> toGeometry(
        TriList<HullTri>& triList,
        const GeometryFactory* factory);
 
 
};
 
 
} // geos::algorithm::hull
} // geos::algorithm
} // geos