GEOS 3.12.0
ConcaveHull.h
1/**********************************************************************
2 *
3 * GEOS - Geometry Engine Open Source
4 * http://geos.osgeo.org
5 *
6 * Copyright (C) 2021 Paul Ramsey <pramsey@cleverelephant.ca>
7 *
8 * This is free software; you can redistribute and/or modify it under
9 * the terms of the GNU Lesser General Public Licence as published
10 * by the Free Software Foundation.
11 * See the COPYING file for more information.
12 *
13 **********************************************************************/
14
15#pragma once
16
17#include <geos/geom/Triangle.h>
18#include <geos/triangulate/tri/Tri.h>
19#include <geos/triangulate/tri/TriList.h>
20#include <geos/triangulate/quadedge/TriangleVisitor.h>
21#include <geos/algorithm/hull/HullTri.h>
22
23#include <queue>
24#include <deque>
25
26namespace geos {
27namespace geom {
28class Coordinate;
29class Geometry;
30class GeometryFactory;
31}
32namespace triangulate {
33namespace quadedge {
34class Quadedge;
36}
37}
38}
39
49
50namespace geos {
51namespace algorithm { // geos::algorithm
52namespace hull { // geos::algorithm::hull
53
54
55typedef std::priority_queue<HullTri*, std::vector<HullTri*>, HullTri::HullTriCompare> HullTriQueue;
56
57
95class GEOS_DLL ConcaveHull {
96
97public:
98
99 ConcaveHull(const Geometry* geom)
100 : inputGeometry(geom)
101 , maxEdgeLengthRatio(-1.0)
102 , alpha(-1)
103 , isHolesAllowed(false)
104 , criteriaType(PARAM_EDGE_LENGTH)
105 , maxSizeInHull(0.0)
106 , geomFactory(geom->getFactory())
107 {};
108
121 static double uniformEdgeLength(const Geometry* geom);
122
131 static std::unique_ptr<Geometry> concaveHullByLength(
132 const Geometry* geom, double maxLength);
133
134 static std::unique_ptr<Geometry> concaveHullByLength(
135 const Geometry* geom, double maxLength, bool isHolesAllowed);
136
148 static std::unique_ptr<Geometry> concaveHullByLengthRatio(
149 const Geometry* geom, double lengthRatio);
150
164 static std::unique_ptr<Geometry> concaveHullByLengthRatio(
165 const Geometry* geom,
166 double lengthRatio,
167 bool isHolesAllowed);
168
178 static std::unique_ptr<Geometry> alphaShape(
179 const Geometry* geom,
180 double alpha,
181 bool isHolesAllowed);
182
198 void setMaximumEdgeLength(double edgeLength);
199
211 void setMaximumEdgeLengthRatio(double edgeLengthRatio);
212
218 void setHolesAllowed(bool holesAllowed);
219
227 void setAlpha(double newAlpha);
228
234 std::unique_ptr<Geometry> getHull();
235
236
237private:
238
239 // Constants
240 static constexpr int PARAM_EDGE_LENGTH = 1;
241 static constexpr int PARAM_ALPHA = 2;
242
243 // Members
244 const Geometry* inputGeometry;
245 double maxEdgeLengthRatio;
246 double alpha;
247 bool isHolesAllowed;
248 int criteriaType;
249 double maxSizeInHull;
250 const GeometryFactory* geomFactory;
251
252 // Methods
253 static double computeTargetEdgeLength(
254 TriList<HullTri>& triList,
255 double edgeLengthFactor);
256
257 void computeHull(TriList<HullTri>& triList);
258 void computeHullBorder(TriList<HullTri>& triList);
259 void createBorderQueue(HullTriQueue& queue, TriList<HullTri>& triList);
260
271 void addBorderTri(HullTri* tri, HullTriQueue& queue);
272 void computeHullHoles(TriList<HullTri>& triList);
273 void setSize(HullTri* tri);
274
275
288 static std::vector<HullTri*> findCandidateHoles(
289 TriList<HullTri>& triList, double maxSizeInHull);
290
291 void removeHole(TriList<HullTri>& triList, HullTri* triHole);
292 void setSize(TriList<HullTri>& triList);
293
301 bool isInHull(const HullTri* tri) const;
302
303 bool isRemovableBorder(const HullTri* tri) const;
304 bool isRemovableHole(const HullTri* tri) const;
305
306 std::unique_ptr<Geometry> toGeometry(
307 TriList<HullTri>& triList,
308 const GeometryFactory* factory);
309
310
311};
312
313
314} // geos::algorithm::hull
315} // geos::algorithm
316} // geos
317
Definition ConcaveHull.h:95
static std::unique_ptr< Geometry > concaveHullByLengthRatio(const Geometry *geom, double lengthRatio, bool isHolesAllowed)
static std::unique_ptr< Geometry > concaveHullByLengthRatio(const Geometry *geom, double lengthRatio)
void setHolesAllowed(bool holesAllowed)
void setAlpha(double newAlpha)
static double uniformEdgeLength(const Geometry *geom)
static std::unique_ptr< Geometry > alphaShape(const Geometry *geom, double alpha, bool isHolesAllowed)
static std::unique_ptr< Geometry > concaveHullByLength(const Geometry *geom, double maxLength)
void setMaximumEdgeLength(double edgeLength)
void setMaximumEdgeLengthRatio(double edgeLengthRatio)
std::unique_ptr< Geometry > getHull()
Coordinate is the lightweight class used to store coordinates.
Definition Coordinate.h:216
Supplies a set of utility methods for building Geometry objects from CoordinateSequence or other Geom...
Definition GeometryFactory.h:65
Basic implementation of Geometry, constructed and destructed by GeometryFactory.
Definition Geometry.h:186
const GeometryFactory * getFactory() const
Gets the factory which contains the context in which this geometry was created.
Definition Geometry.h:216
Represents a planar triangle, and provides methods for calculating various properties of triangles.
Definition Triangle.h:28
A class that contains the QuadEdges representing a planar subdivision that models a triangulation.
Definition QuadEdgeSubdivision.h:83
A class that represents the edge data structure which implements the quadedge algebra.
Definition QuadEdge.h:53
An interface for algorithms which process the triangles in a QuadEdgeSubdivision.
Definition TriangleVisitor.h:33
Definition TriList.h:54
Definition Tri.h:49
Basic namespace for all GEOS functionalities.
Definition geos.h:39