GEOS  3.13.1
ConcaveHullOfPolygons.h
1 /**********************************************************************
2  *
3  * GEOS - Geometry Engine Open Source
4  * http://geos.osgeo.org
5  *
6  * Copyright (C) 2022 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/triangulate/tri/TriList.h>
18 
19 #include <set>
20 #include <deque>
21 #include <map>
22 
23 namespace geos {
24 namespace geom {
25 class Coordinate;
26 class CoordinateSequence;
27 class Envelope;
28 class Geometry;
29 class GeometryCollection;
30 class GeometryFactory;
31 class LinearRing;
32 class Polygon;
33 }
34 namespace triangulate {
35 namespace tri {
36 class Tri;
37 }
38 }
39 }
40 
41 #include <geos/triangulate/tri/Tri.h>
42 
43 
54 
55 
56 namespace geos {
57 namespace algorithm { // geos::algorithm
58 namespace hull { // geos::algorithm::hull
59 
60 
97 class GEOS_DLL ConcaveHullOfPolygons {
98 
99 private:
100 
101  /* Members */
102 
103  static constexpr int FRAME_EXPAND_FACTOR = 4;
104 
105  const Geometry* inputPolygons;
106  const GeometryFactory* geomFactory;
107  double maxEdgeLength;
108  double maxEdgeLengthRatio;
109  bool isHolesAllowed;
110  bool isTight;
111 
112  std::set<Tri*> hullTris;
113  std::deque<Tri*> borderTriQue;
114  std::vector<const LinearRing*> polygonRings;
115  TriList<Tri> triList;
116 
121  std::map<Tri*, TriIndex> borderEdgeMap;
122 
123  /* Methods */
124 
125  std::unique_ptr<Geometry> createEmptyHull();
126 
127  void buildHullTris();
128 
140  std::unique_ptr<Polygon> createFrame(
141  const Envelope* polygonsEnv);
142 
143  double computeTargetEdgeLength(
144  TriList<Tri>& triList,
145  const CoordinateSequence* frameCorners,
146  double edgeLengthRatio) const;
147 
148  bool isFrameTri(
149  const Tri* tri,
150  const CoordinateSequence* frameCorners) const;
151 
152  void removeFrameCornerTris(
153  TriList<Tri>& tris,
154  const CoordinateSequence* frameCorners);
155 
164  TriIndex vertexIndex(
165  const Tri* tri,
166  const CoordinateSequence* pts) const;
167 
168  void removeBorderTris();
169 
170  void removeHoleTris();
171 
172  Tri* findHoleSeedTri() const;
173 
174  bool isHoleSeedTri(const Tri* tri) const;
175 
176  bool isBorderTri(const Tri* tri) const;
177 
178  bool isRemovable(const Tri* tri) const;
179 
189  bool isTouchingSinglePolygon(const Tri* tri) const;
190 
191  void addBorderTris(Tri* tri);
192 
205  void addBorderTri(Tri* tri, TriIndex index);
206 
207  void removeBorderTri(Tri* tri);
208 
209  bool hasAllVertices(const LinearRing* ring, const Tri* tri) const;
210 
211  bool hasVertex(const LinearRing* ring, const Coordinate& v) const;
212 
213  void envelope(const Tri* tri, Envelope& env) const;
214 
215  std::unique_ptr<Geometry> createHullGeometry(bool isIncludeInput);
216 
217 
218 public:
219 
228  static std::unique_ptr<Geometry>
229  concaveHullByLength(const Geometry* polygons, double maxLength);
230 
243  static std::unique_ptr<Geometry>
245  const Geometry* polygons, double maxLength,
246  bool isTight, bool isHolesAllowed);
247 
256  static std::unique_ptr<Geometry>
257  concaveHullByLengthRatio(const Geometry* polygons, double lengthRatio);
258 
271  static std::unique_ptr<Geometry>
273  const Geometry* polygons, double lengthRatio,
274  bool isTight, bool isHolesAllowed);
275 
284  static std::unique_ptr<Geometry>
285  concaveFillByLength(const Geometry* polygons, double maxLength);
286 
295  static std::unique_ptr<Geometry>
296  concaveFillByLengthRatio(const Geometry* polygons, double lengthRatio);
297 
304 
318  void setMaximumEdgeLength(double edgeLength);
319 
334  void setMaximumEdgeLengthRatio(double edgeLengthRatio);
335 
341  void setHolesAllowed(bool p_isHolesAllowed);
342 
349  void setTight(bool p_isTight);
350 
356  std::unique_ptr<Geometry> getHull();
357 
364  std::unique_ptr<Geometry> getFill();
365 
366 
367 };
368 
369 
370 
371 } // geos::algorithm::hull
372 } // geos::algorithm
373 } // geos
Definition: ConcaveHullOfPolygons.h:97
std::unique_ptr< Geometry > getHull()
static std::unique_ptr< Geometry > concaveHullByLength(const Geometry *polygons, double maxLength, bool isTight, bool isHolesAllowed)
std::unique_ptr< Geometry > getFill()
static std::unique_ptr< Geometry > concaveHullByLengthRatio(const Geometry *polygons, double lengthRatio)
static std::unique_ptr< Geometry > concaveFillByLength(const Geometry *polygons, double maxLength)
static std::unique_ptr< Geometry > concaveHullByLength(const Geometry *polygons, double maxLength)
static std::unique_ptr< Geometry > concaveFillByLengthRatio(const Geometry *polygons, double lengthRatio)
static std::unique_ptr< Geometry > concaveHullByLengthRatio(const Geometry *polygons, double lengthRatio, bool isTight, bool isHolesAllowed)
void setMaximumEdgeLength(double edgeLength)
void setHolesAllowed(bool p_isHolesAllowed)
void setMaximumEdgeLengthRatio(double edgeLengthRatio)
The internal representation of a list of coordinates inside a Geometry.
Definition: CoordinateSequence.h:56
Coordinate is the lightweight class used to store coordinates.
Definition: Coordinate.h:217
An Envelope defines a rectangulare region of the 2D coordinate plane.
Definition: Envelope.h:59
Represents a collection of heterogeneous Geometry objects.
Definition: GeometryCollection.h:51
Supplies a set of utility methods for building Geometry objects from CoordinateSequence or other Geom...
Definition: GeometryFactory.h:70
Basic implementation of Geometry, constructed and destructed by GeometryFactory.
Definition: Geometry.h:197
Models an OGC SFS LinearRing. A LinearRing is a LineString which is both closed and simple.
Definition: LinearRing.h:54
Represents a linear polygon, which may include holes.
Definition: Polygon.h:61
Definition: TriList.h:54
Definition: Tri.h:49
Basic namespace for all GEOS functionalities.
Definition: Angle.h:25