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
geos::algorithm::hull::ConcaveHull::concaveHullByLengthRatio
static std::unique_ptr< Geometry > concaveHullByLengthRatio(const Geometry *geom, double lengthRatio, bool isHolesAllowed)
geos::algorithm::hull::ConcaveHull::concaveHullByLengthRatio
static std::unique_ptr< Geometry > concaveHullByLengthRatio(const Geometry *geom, double lengthRatio)
geos::algorithm::hull::ConcaveHull::setHolesAllowed
void setHolesAllowed(bool holesAllowed)
geos::algorithm::hull::ConcaveHull::setAlpha
void setAlpha(double newAlpha)
geos::algorithm::hull::ConcaveHull::uniformEdgeLength
static double uniformEdgeLength(const Geometry *geom)
geos::algorithm::hull::ConcaveHull::alphaShape
static std::unique_ptr< Geometry > alphaShape(const Geometry *geom, double alpha, bool isHolesAllowed)
geos::algorithm::hull::ConcaveHull::concaveHullByLength
static std::unique_ptr< Geometry > concaveHullByLength(const Geometry *geom, double maxLength)
geos::algorithm::hull::ConcaveHull::setMaximumEdgeLength
void setMaximumEdgeLength(double edgeLength)
geos::algorithm::hull::ConcaveHull::setMaximumEdgeLengthRatio
void setMaximumEdgeLengthRatio(double edgeLengthRatio)
geos::algorithm::hull::ConcaveHull::getHull
std::unique_ptr< Geometry > getHull()
geos::geom::Coordinate
Coordinate is the lightweight class used to store coordinates.
Definition Coordinate.h:217
geos::geom::GeometryFactory
Supplies a set of utility methods for building Geometry objects from CoordinateSequence or other Geom...
Definition GeometryFactory.h:70
geos::geom::Geometry
Basic implementation of Geometry, constructed and destructed by GeometryFactory.
Definition Geometry.h:196
geos::geom::Triangle
Represents a planar triangle, and provides methods for calculating various properties of triangles.
Definition Triangle.h:28
geos::triangulate::quadedge::QuadEdgeSubdivision
A class that contains the QuadEdges representing a planar subdivision that models a triangulation.
Definition QuadEdgeSubdivision.h:78
geos::triangulate::quadedge::QuadEdge
A class that represents the edge data structure which implements the quadedge algebra.
Definition QuadEdge.h:53
geos::triangulate::tri::TriList
Definition TriList.h:50
geos::triangulate::tri::Tri
Definition Tri.h:45
geos::geom
Definition Angle.h:26
geos::triangulate::quadedge
Classes to implement a topological subdivision of quadeges, to support creating triangulations and Vo...
Definition ConcaveHull.h:33
geos::triangulate
Classes to compute Delaunay triangulations.
Definition ConcaveHull.h:32
geos
Basic namespace for all GEOS functionalities.
Definition geos.h:38