1/*************************************************************************/
2/* Copyright (c) 2011-2021 Ivan Fratric and contributors. */
3/* */
4/* Permission is hereby granted, free of charge, to any person obtaining */
5/* a copy of this software and associated documentation files (the */
6/* "Software"), to deal in the Software without restriction, including */
7/* without limitation the rights to use, copy, modify, merge, publish, */
8/* distribute, sublicense, and/or sell copies of the Software, and to */
9/* permit persons to whom the Software is furnished to do so, subject to */
10/* the following conditions: */
11/* */
12/* The above copyright notice and this permission notice shall be */
13/* included in all copies or substantial portions of the Software. */
14/* */
15/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
16/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
17/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/
18/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
19/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
20/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
21/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
22/*************************************************************************/
23
24#ifndef POLYPARTITION_H
25#define POLYPARTITION_H
26
27#include "core/math/vector2.h"
28#include "core/templates/list.h"
29#include "core/templates/rb_set.h"
30
31typedef double tppl_float;
32
33enum TPPLOrientation {
34 TPPL_ORIENTATION_CW = -1,
35 TPPL_ORIENTATION_NONE = 0,
36 TPPL_ORIENTATION_CCW = 1,
37};
38
39enum TPPLVertexType {
40 TPPL_VERTEXTYPE_REGULAR = 0,
41 TPPL_VERTEXTYPE_START = 1,
42 TPPL_VERTEXTYPE_END = 2,
43 TPPL_VERTEXTYPE_SPLIT = 3,
44 TPPL_VERTEXTYPE_MERGE = 4,
45};
46
47// 2D point structure.
48typedef Vector2 TPPLPoint;
49
50// Polygon implemented as an array of points with a "hole" flag.
51class TPPLPoly {
52 protected:
53 TPPLPoint *points;
54 long numpoints;
55 bool hole;
56
57 public:
58 // Constructors and destructors.
59 TPPLPoly();
60 ~TPPLPoly();
61
62 TPPLPoly(const TPPLPoly &src);
63 TPPLPoly &operator=(const TPPLPoly &src);
64
65 // Getters and setters.
66 long GetNumPoints() const {
67 return numpoints;
68 }
69
70 bool IsHole() const {
71 return hole;
72 }
73
74 void SetHole(bool p_hole) {
75 this->hole = p_hole;
76 }
77
78 TPPLPoint &GetPoint(long i) {
79 return points[i];
80 }
81
82 const TPPLPoint &GetPoint(long i) const {
83 return points[i];
84 }
85
86 TPPLPoint *GetPoints() {
87 return points;
88 }
89
90 TPPLPoint &operator[](int i) {
91 return points[i];
92 }
93
94 const TPPLPoint &operator[](int i) const {
95 return points[i];
96 }
97
98 // Clears the polygon points.
99 void Clear();
100
101 // Inits the polygon with numpoints vertices.
102 void Init(long numpoints);
103
104 // Creates a triangle with points p1, p2, and p3.
105 void Triangle(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3);
106
107 // Inverts the orfer of vertices.
108 void Invert();
109
110 // Returns the orientation of the polygon.
111 // Possible values:
112 // TPPL_ORIENTATION_CCW: Polygon vertices are in counter-clockwise order.
113 // TPPL_ORIENTATION_CW: Polygon vertices are in clockwise order.
114 // TPPL_ORIENTATION_NONE: The polygon has no (measurable) area.
115 TPPLOrientation GetOrientation() const;
116
117 // Sets the polygon orientation.
118 // Possible values:
119 // TPPL_ORIENTATION_CCW: Sets vertices in counter-clockwise order.
120 // TPPL_ORIENTATION_CW: Sets vertices in clockwise order.
121 // TPPL_ORIENTATION_NONE: Reverses the orientation of the vertices if there
122 // is one, otherwise does nothing (if orientation is already NONE).
123 void SetOrientation(TPPLOrientation orientation);
124
125 // Checks whether a polygon is valid or not.
126 inline bool Valid() const { return this->numpoints >= 3; }
127};
128
129#ifdef TPPL_ALLOCATOR
130typedef List<TPPLPoly, TPPL_ALLOCATOR(TPPLPoly)> TPPLPolyList;
131#else
132typedef List<TPPLPoly> TPPLPolyList;
133#endif
134
135class TPPLPartition {
136 protected:
137 struct PartitionVertex {
138 bool isActive;
139 bool isConvex;
140 bool isEar;
141
142 TPPLPoint p;
143 tppl_float angle;
144 PartitionVertex *previous;
145 PartitionVertex *next;
146
147 PartitionVertex();
148 };
149
150 struct MonotoneVertex {
151 TPPLPoint p;
152 long previous;
153 long next;
154 };
155
156 class VertexSorter {
157 MonotoneVertex *vertices;
158
159public:
160 VertexSorter(MonotoneVertex *v) :
161 vertices(v) {}
162 bool operator()(long index1, long index2);
163 };
164
165 struct Diagonal {
166 long index1;
167 long index2;
168 };
169
170#ifdef TPPL_ALLOCATOR
171 typedef List<Diagonal, TPPL_ALLOCATOR(Diagonal)> DiagonalList;
172#else
173 typedef List<Diagonal> DiagonalList;
174#endif
175
176 // Dynamic programming state for minimum-weight triangulation.
177 struct DPState {
178 bool visible;
179 tppl_float weight;
180 long bestvertex;
181 };
182
183 // Dynamic programming state for convex partitioning.
184 struct DPState2 {
185 bool visible;
186 long weight;
187 DiagonalList pairs;
188 };
189
190 // Edge that intersects the scanline.
191 struct ScanLineEdge {
192 mutable long index;
193 TPPLPoint p1;
194 TPPLPoint p2;
195
196 // Determines if the edge is to the left of another edge.
197 bool operator<(const ScanLineEdge &other) const;
198
199 bool IsConvex(const TPPLPoint &p1, const TPPLPoint &p2, const TPPLPoint &p3) const;
200 };
201
202 // Standard helper functions.
203 bool IsConvex(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3);
204 bool IsReflex(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3);
205 bool IsInside(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3, TPPLPoint &p);
206
207 bool InCone(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3, TPPLPoint &p);
208 bool InCone(PartitionVertex *v, TPPLPoint &p);
209
210 int Intersects(TPPLPoint &p11, TPPLPoint &p12, TPPLPoint &p21, TPPLPoint &p22);
211
212 TPPLPoint Normalize(const TPPLPoint &p);
213 tppl_float Distance(const TPPLPoint &p1, const TPPLPoint &p2);
214
215 // Helper functions for Triangulate_EC.
216 void UpdateVertexReflexity(PartitionVertex *v);
217 void UpdateVertex(PartitionVertex *v, PartitionVertex *vertices, long numvertices);
218
219 // Helper functions for ConvexPartition_OPT.
220 void UpdateState(long a, long b, long w, long i, long j, DPState2 **dpstates);
221 void TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates);
222 void TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates);
223
224 // Helper functions for MonotonePartition.
225 bool Below(TPPLPoint &p1, TPPLPoint &p2);
226 void AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2,
227 TPPLVertexType *vertextypes, RBSet<ScanLineEdge>::Element **edgeTreeIterators,
228 RBSet<ScanLineEdge> *edgeTree, long *helpers);
229
230 // Triangulates a monotone polygon, used in Triangulate_MONO.
231 int TriangulateMonotone(TPPLPoly *inPoly, TPPLPolyList *triangles);
232
233 public:
234 // Simple heuristic procedure for removing holes from a list of polygons.
235 // It works by creating a diagonal from the right-most hole vertex
236 // to some other visible vertex.
237 // Time complexity: O(h*(n^2)), h is the # of holes, n is the # of vertices.
238 // Space complexity: O(n)
239 // params:
240 // inpolys:
241 // A list of polygons that can contain holes.
242 // Vertices of all non-hole polys have to be in counter-clockwise order.
243 // Vertices of all hole polys have to be in clockwise order.
244 // outpolys:
245 // A list of polygons without holes.
246 // Returns 1 on success, 0 on failure.
247 int RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys);
248
249 // Triangulates a polygon by ear clipping.
250 // Time complexity: O(n^2), n is the number of vertices.
251 // Space complexity: O(n)
252 // params:
253 // poly:
254 // An input polygon to be triangulated.
255 // Vertices have to be in counter-clockwise order.
256 // triangles:
257 // A list of triangles (result).
258 // Returns 1 on success, 0 on failure.
259 int Triangulate_EC(TPPLPoly *poly, TPPLPolyList *triangles);
260
261 // Triangulates a list of polygons that may contain holes by ear clipping
262 // algorithm. It first calls RemoveHoles to get rid of the holes, and then
263 // calls Triangulate_EC for each resulting polygon.
264 // Time complexity: O(h*(n^2)), h is the # of holes, n is the # of vertices.
265 // Space complexity: O(n)
266 // params:
267 // inpolys:
268 // A list of polygons to be triangulated (can contain holes).
269 // Vertices of all non-hole polys have to be in counter-clockwise order.
270 // Vertices of all hole polys have to be in clockwise order.
271 // triangles:
272 // A list of triangles (result).
273 // Returns 1 on success, 0 on failure.
274 int Triangulate_EC(TPPLPolyList *inpolys, TPPLPolyList *triangles);
275
276 // Creates an optimal polygon triangulation in terms of minimal edge length.
277 // Time complexity: O(n^3), n is the number of vertices
278 // Space complexity: O(n^2)
279 // params:
280 // poly:
281 // An input polygon to be triangulated.
282 // Vertices have to be in counter-clockwise order.
283 // triangles:
284 // A list of triangles (result).
285 // Returns 1 on success, 0 on failure.
286 int Triangulate_OPT(TPPLPoly *poly, TPPLPolyList *triangles);
287
288 // Triangulates a polygon by first partitioning it into monotone polygons.
289 // Time complexity: O(n*log(n)), n is the number of vertices.
290 // Space complexity: O(n)
291 // params:
292 // poly:
293 // An input polygon to be triangulated.
294 // Vertices have to be in counter-clockwise order.
295 // triangles:
296 // A list of triangles (result).
297 // Returns 1 on success, 0 on failure.
298 int Triangulate_MONO(TPPLPoly *poly, TPPLPolyList *triangles);
299
300 // Triangulates a list of polygons by first
301 // partitioning them into monotone polygons.
302 // Time complexity: O(n*log(n)), n is the number of vertices.
303 // Space complexity: O(n)
304 // params:
305 // inpolys:
306 // A list of polygons to be triangulated (can contain holes).
307 // Vertices of all non-hole polys have to be in counter-clockwise order.
308 // Vertices of all hole polys have to be in clockwise order.
309 // triangles:
310 // A list of triangles (result).
311 // Returns 1 on success, 0 on failure.
312 int Triangulate_MONO(TPPLPolyList *inpolys, TPPLPolyList *triangles);
313
314 // Creates a monotone partition of a list of polygons that
315 // can contain holes. Triangulates a set of polygons by
316 // first partitioning them into monotone polygons.
317 // Time complexity: O(n*log(n)), n is the number of vertices.
318 // Space complexity: O(n)
319 // params:
320 // inpolys:
321 // A list of polygons to be triangulated (can contain holes).
322 // Vertices of all non-hole polys have to be in counter-clockwise order.
323 // Vertices of all hole polys have to be in clockwise order.
324 // monotonePolys:
325 // A list of monotone polygons (result).
326 // Returns 1 on success, 0 on failure.
327 int MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monotonePolys);
328
329 // Partitions a polygon into convex polygons by using the
330 // Hertel-Mehlhorn algorithm. The algorithm gives at most four times
331 // the number of parts as the optimal algorithm, however, in practice
332 // it works much better than that and often gives optimal partition.
333 // It uses triangulation obtained by ear clipping as intermediate result.
334 // Time complexity O(n^2), n is the number of vertices.
335 // Space complexity: O(n)
336 // params:
337 // poly:
338 // An input polygon to be partitioned.
339 // Vertices have to be in counter-clockwise order.
340 // parts:
341 // Resulting list of convex polygons.
342 // Returns 1 on success, 0 on failure.
343 int ConvexPartition_HM(TPPLPoly *poly, TPPLPolyList *parts);
344
345 // Partitions a list of polygons into convex parts by using the
346 // Hertel-Mehlhorn algorithm. The algorithm gives at most four times
347 // the number of parts as the optimal algorithm, however, in practice
348 // it works much better than that and often gives optimal partition.
349 // It uses triangulation obtained by ear clipping as intermediate result.
350 // Time complexity O(n^2), n is the number of vertices.
351 // Space complexity: O(n)
352 // params:
353 // inpolys:
354 // An input list of polygons to be partitioned. Vertices of
355 // all non-hole polys have to be in counter-clockwise order.
356 // Vertices of all hole polys have to be in clockwise order.
357 // parts:
358 // Resulting list of convex polygons.
359 // Returns 1 on success, 0 on failure.
360 int ConvexPartition_HM(TPPLPolyList *inpolys, TPPLPolyList *parts);
361
362 // Optimal convex partitioning (in terms of number of resulting
363 // convex polygons) using the Keil-Snoeyink algorithm.
364 // For reference, see M. Keil, J. Snoeyink, "On the time bound for
365 // convex decomposition of simple polygons", 1998.
366 // Time complexity O(n^3), n is the number of vertices.
367 // Space complexity: O(n^3)
368 // params:
369 // poly:
370 // An input polygon to be partitioned.
371 // Vertices have to be in counter-clockwise order.
372 // parts:
373 // Resulting list of convex polygons.
374 // Returns 1 on success, 0 on failure.
375 int ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts);
376};
377
378#endif
379