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

    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