GEOS  3.11.0rc0
PolygonEarClipper.h
1 /**********************************************************************
2  *
3  * GEOS - Geometry Engine Open Source
4  * http://geos.osgeo.org
5  *
6  * Copyright (C) 2020 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/index/VertexSequencePackedRtree.h>
18 #include <geos/triangulate/tri/TriList.h>
19 #include <geos/triangulate/tri/Tri.h>
20 
21 #include <array>
22 #include <memory>
23 #include <limits>
24 
25 // Forward declarations
26 namespace geos {
27 namespace geom {
28 class Coordinate;
29 class Polygon;
30 class Envelope;
31 }
32 }
33 
40 
41 namespace geos {
42 namespace triangulate {
43 namespace polygon {
44 
45 
66 class GEOS_DLL PolygonEarClipper {
67 
68 private:
69 
70  // Members
71 
72  static constexpr std::size_t NO_VERTEX_INDEX = std::numeric_limits<std::size_t>::max();
73 
74  bool isFlatCornersSkipped = false;
75 
81  std::vector<Coordinate> vertex;
82  std::vector<std::size_t> vertexNext;
83  std::size_t vertexSize;
84 
85  // first available vertex index
86  std::size_t vertexFirst;
87 
88  // indices for current corner
89  std::array<std::size_t, 3> cornerIndex;
90 
95  VertexSequencePackedRtree vertexCoordIndex;
96 
97  // Methods
98 
99  std::vector<std::size_t> createNextLinks(std::size_t size) const;
100 
101  bool isValidEar(std::size_t cornerIndex, const std::array<Coordinate, 3>& corner);
102 
115  std::size_t findIntersectingVertex(std::size_t cornerIndex, const std::array<Coordinate, 3>& corner) const;
116 
126  bool isValidEarScan(std::size_t cornerIndex, const std::array<Coordinate, 3>& corner) const;
127 
128  /* private */
129  static Envelope envelope(const std::array<Coordinate, 3>& corner);
130 
134  void removeCorner();
135 
136  bool isRemoved(std::size_t vertexIndex) const;
137 
138  void initCornerIndex();
139 
145  void fetchCorner(std::array<Coordinate, 3>& cornerVertex) const;
146 
150  void nextCorner(std::array<Coordinate, 3>& cornerVertex);
151 
159  std::size_t nextIndex(std::size_t index) const;
160 
161  bool isConvex(const std::array<Coordinate, 3>& pts) const;
162 
163  bool isFlat(const std::array<Coordinate, 3>& pts) const;
164 
170  bool isCornerInvalid(const std::array<Coordinate, 3>& pts) const;
171 
172 
173 public:
174 
180  PolygonEarClipper(std::vector<Coordinate>& polyShell);
181 
189  static void triangulate(std::vector<Coordinate>& polyShell, TriList<Tri>& triListResult);
190 
207  void setSkipFlatCorners(bool p_isFlatCornersSkipped);
208 
209  void compute(TriList<Tri>& triList);
210 
211  std::unique_ptr<Polygon> toGeometry() const;
212 
213 
214 };
215 
216 
217 
218 } // namespace geos.triangulate.polygon
219 } // namespace geos.triangulate
220 } // namespace geos
Coordinate is the lightweight class used to store coordinates.
Definition: Coordinate.h:58
An Envelope defines a rectangulare region of the 2D coordinate plane.
Definition: Envelope.h:58
Represents a linear polygon, which may include holes.
Definition: Polygon.h:61
Definition: VertexSequencePackedRtree.h:49
Definition: PolygonEarClipper.h:66
PolygonEarClipper(std::vector< Coordinate > &polyShell)
static void triangulate(std::vector< Coordinate > &polyShell, TriList< Tri > &triListResult)
void setSkipFlatCorners(bool p_isFlatCornersSkipped)
Definition: TriList.h:54
Definition: Tri.h:49
Basic namespace for all GEOS functionalities.
Definition: Angle.h:25