GEOS 3.11.2
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
26namespace geos {
27namespace geom {
28class Coordinate;
30class Polygon;
31class Envelope;
32}
33}
34
42
43namespace geos {
44namespace triangulate {
45namespace polygon {
46
47
68class GEOS_DLL PolygonEarClipper {
69
70private:
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
172 bool isCornerInvalid(const std::array<Coordinate, 3>& pts) const;
173
174
175public:
176
182 PolygonEarClipper(const std::vector<Coordinate>& polyShell);
183
190 static void triangulate(const std::vector<Coordinate>& polyShell, TriList<Tri>& triListResult);
191 static void triangulate(const CoordinateSequence& polyShell, TriList<Tri>& triListResult);
192
209 void setSkipFlatCorners(bool p_isFlatCornersSkipped);
210
211 void compute(TriList<Tri>& triList);
212
213 std::unique_ptr<Polygon> toGeometry() const;
214
215
216};
217
218
219
220} // namespace geos.triangulate.polygon
221} // namespace geos.triangulate
222} // namespace geos
The internal representation of a list of coordinates inside a Geometry.
Definition CoordinateSequence.h:44
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:68
PolygonEarClipper(const std::vector< Coordinate > &polyShell)
void setSkipFlatCorners(bool p_isFlatCornersSkipped)
static void triangulate(const std::vector< Coordinate > &polyShell, TriList< Tri > &triListResult)
Definition TriList.h:54
Definition Tri.h:49
Basic namespace for all GEOS functionalities.
Definition geos.h:39