GEOS  3.13.0dev
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 
26 namespace geos {
27 namespace geom {
28 class Coordinate;
29 class Geometry;
30 class GeometryFactory;
31 }
32 namespace triangulate {
33 namespace quadedge {
34 class Quadedge;
36 }
37 }
38 }
39 
49 
50 namespace geos {
51 namespace algorithm { // geos::algorithm
52 namespace hull { // geos::algorithm::hull
53 
54 
55 typedef std::priority_queue<HullTri*, std::vector<HullTri*>, HullTri::HullTriCompare> HullTriQueue;
56 
57 
95 class GEOS_DLL ConcaveHull {
96 
97 public:
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 
237 private:
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
std::unique_ptr< Geometry > getHull()
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)
void setMaximumEdgeLength(double edgeLength)
static std::unique_ptr< Geometry > concaveHullByLength(const Geometry *geom, double maxLength)
void setMaximumEdgeLengthRatio(double edgeLengthRatio)
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:78
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: Angle.h:25