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;
}
}
}
 
using geos::geom::Coordinate;
using geos::geom::Geometry;
using geos::geom::GeometryFactory;
using geos::geom::Triangle;
using geos::triangulate::quadedge::QuadEdge;
using geos::triangulate::quadedge::QuadEdgeSubdivision;
using geos::triangulate::quadedge::TriangleVisitor;
using geos::triangulate::tri::Tri;
using geos::triangulate::tri::TriList;
 
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 {
 
public:
 
    ConcaveHull(const Geometry* geom)
        : inputGeometry(geom)
        , maxEdgeLength(0.0)
        , maxEdgeLengthRatio(-1.0)
        , isHolesAllowed(false)
        , geomFactory(geom->getFactory())
        {};
 
    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);
 
    void setMaximumEdgeLength(double edgeLength);
 
    void setMaximumEdgeLengthRatio(double edgeLengthRatio);
 
    void setHolesAllowed(bool holesAllowed);
 
    std::unique_ptr<Geometry> getHull();
 
 
private:
 
    // Members
    const Geometry* inputGeometry;
    double maxEdgeLength;
    double maxEdgeLengthRatio;
    bool isHolesAllowed;
    const GeometryFactory* geomFactory;
 
    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);
    bool isBelowLengthThreshold(const HullTri* tri) const;
    void computeHullHoles(TriList<HullTri>& triList);
 
    static std::vector<HullTri*> findCandidateHoles(
        TriList<HullTri>& triList, double minEdgeLen);
 
    void removeHole(TriList<HullTri>& triList, HullTri* triHole);
 
    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