GEOS  3.10.1
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/triangulate/polygon/VertexSequencePackedRtree.h>
18 
19 #include <array>
20 #include <memory>
21 #include <limits>
22 
23 // Forward declarations
24 namespace geos {
25 namespace geom {
26 class Coordinate;
27 class Polygon;
28 class Envelope;
29 }
30 namespace triangulate {
31 namespace tri {
32 class TriList;
33 }
34 }
35 }
36 
41 
42 
43 namespace geos {
44 namespace triangulate {
45 namespace polygon {
46 
47 
68 class GEOS_DLL PolygonEarClipper {
69 
70 private:
71 
72  // Members
73 
74  static constexpr std::size_t NO_VERTEX_INDEX = std::numeric_limits<std::size_t>::max();
75 
76  bool isFlatCornersSkipped = false;
77 
83  std::vector<Coordinate> vertex;
84  std::vector<std::size_t> vertexNext;
85  std::size_t vertexSize;
86 
87  // first available vertex index
88  std::size_t vertexFirst;
89 
90  // indices for current corner
91  std::array<std::size_t, 3> cornerIndex;
92 
97  VertexSequencePackedRtree vertexCoordIndex;
98 
99  // Methods
100 
101  std::vector<std::size_t> createNextLinks(std::size_t size) const;
102 
103  bool isValidEar(std::size_t cornerIndex, const std::array<Coordinate, 3>& corner);
104 
117  std::size_t findIntersectingVertex(std::size_t cornerIndex, const std::array<Coordinate, 3>& corner) const;
118 
128  bool isValidEarScan(std::size_t cornerIndex, const std::array<Coordinate, 3>& corner) const;
129 
130  /* private */
131  static Envelope envelope(const std::array<Coordinate, 3>& corner);
132 
136  void removeCorner();
137 
138  bool isRemoved(std::size_t vertexIndex) const;
139 
140  void initCornerIndex();
141 
147  void fetchCorner(std::array<Coordinate, 3>& cornerVertex) const;
148 
152  void nextCorner(std::array<Coordinate, 3>& cornerVertex);
153 
161  std::size_t nextIndex(std::size_t index) const;
162 
163  bool isConvex(const std::array<Coordinate, 3>& pts) const;
164 
165  bool isFlat(const std::array<Coordinate, 3>& pts) const;
166 
167  bool hasRepeatedPoint(const std::array<Coordinate, 3>& pts) const;
168 
169 
170 public:
171 
177  PolygonEarClipper(std::vector<Coordinate>& polyShell);
178 
186  static void triangulate(std::vector<Coordinate>& polyShell, TriList& triListResult);
187 
204  void setSkipFlatCorners(bool p_isFlatCornersSkipped);
205 
206  void compute(TriList& triList);
207 
208  std::unique_ptr<Polygon> toGeometry() const;
209 
210 
211 };
212 
213 
214 
215 } // namespace geos.triangulate.polygon
216 } // namespace geos.triangulate
217 } // namespace geos
Coordinate is the lightweight class used to store coordinates.
Definition: Coordinate.h:60
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:64
Definition: PolygonEarClipper.h:68
PolygonEarClipper(std::vector< Coordinate > &polyShell)
void setSkipFlatCorners(bool p_isFlatCornersSkipped)
static void triangulate(std::vector< Coordinate > &polyShell, TriList &triListResult)
Definition: VertexSequencePackedRtree.h:50
Definition: TriList.h:48
Basic namespace for all GEOS functionalities.
Definition: Angle.h:26