Horizon
Loading...
Searching...
No Matches
polypartition.h
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 <list>
28#include <set>
29
30typedef double tppl_float;
31
32enum TPPLOrientation {
33 TPPL_ORIENTATION_CW = -1,
34 TPPL_ORIENTATION_NONE = 0,
35 TPPL_ORIENTATION_CCW = 1,
36};
37
38enum TPPLVertexType {
39 TPPL_VERTEXTYPE_REGULAR = 0,
40 TPPL_VERTEXTYPE_START = 1,
41 TPPL_VERTEXTYPE_END = 2,
42 TPPL_VERTEXTYPE_SPLIT = 3,
43 TPPL_VERTEXTYPE_MERGE = 4,
44};
45
46// 2D point structure.
47struct TPPLPoint {
48 tppl_float x;
49 tppl_float y;
50 // User-specified vertex identifier. Note that this isn't used internally
51 // by the library, but will be faithfully copied around.
52 int id;
53
54 TPPLPoint operator+(const TPPLPoint &p) const {
55 TPPLPoint r;
56 r.x = x + p.x;
57 r.y = y + p.y;
58 return r;
59 }
60
61 TPPLPoint operator-(const TPPLPoint &p) const {
62 TPPLPoint r;
63 r.x = x - p.x;
64 r.y = y - p.y;
65 return r;
66 }
67
68 TPPLPoint operator*(const tppl_float f) const {
69 TPPLPoint r;
70 r.x = x * f;
71 r.y = y * f;
72 return r;
73 }
74
75 TPPLPoint operator/(const tppl_float f) const {
76 TPPLPoint r;
77 r.x = x / f;
78 r.y = y / f;
79 return r;
80 }
81
82 bool operator==(const TPPLPoint &p) const {
83 return ((x == p.x) && (y == p.y));
84 }
85
86 bool operator!=(const TPPLPoint &p) const {
87 return !((x == p.x) && (y == p.y));
88 }
89};
90
91// Polygon implemented as an array of points with a "hole" flag.
92class TPPLPoly {
93 protected:
94 TPPLPoint *points;
95 long numpoints;
96 bool hole;
97
98 public:
99 // Constructors and destructors.
100 TPPLPoly();
101 ~TPPLPoly();
102
103 TPPLPoly(const TPPLPoly &src);
104 TPPLPoly &operator=(const TPPLPoly &src);
105
106 // Getters and setters.
107 long GetNumPoints() const {
108 return numpoints;
109 }
110
111 bool IsHole() const {
112 return hole;
113 }
114
115 void SetHole(bool hole) {
116 this->hole = hole;
117 }
118
119 TPPLPoint &GetPoint(long i) {
120 return points[i];
121 }
122
123 const TPPLPoint &GetPoint(long i) const {
124 return points[i];
125 }
126
127 TPPLPoint *GetPoints() {
128 return points;
129 }
130
131 TPPLPoint &operator[](int i) {
132 return points[i];
133 }
134
135 const TPPLPoint &operator[](int i) const {
136 return points[i];
137 }
138
139 // Clears the polygon points.
140 void Clear();
141
142 // Inits the polygon with numpoints vertices.
143 void Init(long numpoints);
144
145 // Creates a triangle with points p1, p2, and p3.
146 void Triangle(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3);
147
148 // Inverts the orfer of vertices.
149 void Invert();
150
151 // Returns the orientation of the polygon.
152 // Possible values:
153 // TPPL_ORIENTATION_CCW: Polygon vertices are in counter-clockwise order.
154 // TPPL_ORIENTATION_CW: Polygon vertices are in clockwise order.
155 // TPPL_ORIENTATION_NONE: The polygon has no (measurable) area.
156 TPPLOrientation GetOrientation() const;
157
158 // Sets the polygon orientation.
159 // Possible values:
160 // TPPL_ORIENTATION_CCW: Sets vertices in counter-clockwise order.
161 // TPPL_ORIENTATION_CW: Sets vertices in clockwise order.
162 // TPPL_ORIENTATION_NONE: Reverses the orientation of the vertices if there
163 // is one, otherwise does nothing (if orientation is already NONE).
164 void SetOrientation(TPPLOrientation orientation);
165
166 // Checks whether a polygon is valid or not.
167 inline bool Valid() const { return this->numpoints >= 3; }
168};
169
170#ifdef TPPL_ALLOCATOR
171typedef std::list<TPPLPoly, TPPL_ALLOCATOR(TPPLPoly)> TPPLPolyList;
172#else
173typedef std::list<TPPLPoly> TPPLPolyList;
174#endif
175
177 protected:
179 bool isActive;
180 bool isConvex;
181 bool isEar;
182
183 TPPLPoint p;
184 tppl_float angle;
185 PartitionVertex *previous;
186 PartitionVertex *next;
187
189 };
190
192 TPPLPoint p;
193 long previous;
194 long next;
195 };
196
198 MonotoneVertex *vertices;
199
200public:
202 vertices(v) {}
203 bool operator()(long index1, long index2);
204 };
205
206 struct Diagonal {
207 long index1;
208 long index2;
209 };
210
211#ifdef TPPL_ALLOCATOR
212 typedef std::list<Diagonal, TPPL_ALLOCATOR(Diagonal)> DiagonalList;
213#else
214 typedef std::list<Diagonal> DiagonalList;
215#endif
216
217 // Dynamic programming state for minimum-weight triangulation.
218 struct DPState {
219 bool visible;
220 tppl_float weight;
221 long bestvertex;
222 };
223
224 // Dynamic programming state for convex partitioning.
225 struct DPState2 {
226 bool visible;
227 long weight;
228 DiagonalList pairs;
229 };
230
231 // Edge that intersects the scanline.
233 mutable long index;
234 TPPLPoint p1;
235 TPPLPoint p2;
236
237 // Determines if the edge is to the left of another edge.
238 bool operator<(const ScanLineEdge &other) const;
239
240 bool IsConvex(const TPPLPoint &p1, const TPPLPoint &p2, const TPPLPoint &p3) const;
241 };
242
243 // Standard helper functions.
244 bool IsConvex(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3);
245 bool IsReflex(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3);
246 bool IsInside(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3, TPPLPoint &p);
247
248 bool InCone(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3, TPPLPoint &p);
249 bool InCone(PartitionVertex *v, TPPLPoint &p);
250
251 int Intersects(TPPLPoint &p11, TPPLPoint &p12, TPPLPoint &p21, TPPLPoint &p22);
252
253 TPPLPoint Normalize(const TPPLPoint &p);
254 tppl_float Distance(const TPPLPoint &p1, const TPPLPoint &p2);
255
256 // Helper functions for Triangulate_EC.
257 void UpdateVertexReflexity(PartitionVertex *v);
258 void UpdateVertex(PartitionVertex *v, PartitionVertex *vertices, long numvertices);
259
260 // Helper functions for ConvexPartition_OPT.
261 void UpdateState(long a, long b, long w, long i, long j, DPState2 **dpstates);
262 void TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates);
263 void TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates);
264
265 // Helper functions for MonotonePartition.
266 bool Below(TPPLPoint &p1, TPPLPoint &p2);
267 void AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2,
268 TPPLVertexType *vertextypes, std::set<ScanLineEdge>::iterator *edgeTreeIterators,
269 std::set<ScanLineEdge> *edgeTree, long *helpers);
270
271 // Triangulates a monotone polygon, used in Triangulate_MONO.
272 int TriangulateMonotone(TPPLPoly *inPoly, TPPLPolyList *triangles);
273
274 public:
275 // Simple heuristic procedure for removing holes from a list of polygons.
276 // It works by creating a diagonal from the right-most hole vertex
277 // to some other visible vertex.
278 // Time complexity: O(h*(n^2)), h is the # of holes, n is the # of vertices.
279 // Space complexity: O(n)
280 // params:
281 // inpolys:
282 // A list of polygons that can contain holes.
283 // Vertices of all non-hole polys have to be in counter-clockwise order.
284 // Vertices of all hole polys have to be in clockwise order.
285 // outpolys:
286 // A list of polygons without holes.
287 // Returns 1 on success, 0 on failure.
288 int RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys);
289
290 // Triangulates a polygon by ear clipping.
291 // Time complexity: O(n^2), n is the number of vertices.
292 // Space complexity: O(n)
293 // params:
294 // poly:
295 // An input polygon to be triangulated.
296 // Vertices have to be in counter-clockwise order.
297 // triangles:
298 // A list of triangles (result).
299 // Returns 1 on success, 0 on failure.
300 int Triangulate_EC(TPPLPoly *poly, TPPLPolyList *triangles);
301
302 // Triangulates a list of polygons that may contain holes by ear clipping
303 // algorithm. It first calls RemoveHoles to get rid of the holes, and then
304 // calls Triangulate_EC for each resulting polygon.
305 // Time complexity: O(h*(n^2)), h is the # of holes, n is the # of vertices.
306 // Space complexity: O(n)
307 // params:
308 // inpolys:
309 // A list of polygons to be triangulated (can contain holes).
310 // Vertices of all non-hole polys have to be in counter-clockwise order.
311 // Vertices of all hole polys have to be in clockwise order.
312 // triangles:
313 // A list of triangles (result).
314 // Returns 1 on success, 0 on failure.
315 int Triangulate_EC(TPPLPolyList *inpolys, TPPLPolyList *triangles);
316
317 // Creates an optimal polygon triangulation in terms of minimal edge length.
318 // Time complexity: O(n^3), n is the number of vertices
319 // Space complexity: O(n^2)
320 // params:
321 // poly:
322 // An input polygon to be triangulated.
323 // Vertices have to be in counter-clockwise order.
324 // triangles:
325 // A list of triangles (result).
326 // Returns 1 on success, 0 on failure.
327 int Triangulate_OPT(TPPLPoly *poly, TPPLPolyList *triangles);
328
329 // Triangulates a polygon by first partitioning it into monotone polygons.
330 // Time complexity: O(n*log(n)), n is the number of vertices.
331 // Space complexity: O(n)
332 // params:
333 // poly:
334 // An input polygon to be triangulated.
335 // Vertices have to be in counter-clockwise order.
336 // triangles:
337 // A list of triangles (result).
338 // Returns 1 on success, 0 on failure.
339 int Triangulate_MONO(TPPLPoly *poly, TPPLPolyList *triangles);
340
341 // Triangulates a list of polygons by first
342 // partitioning them into monotone polygons.
343 // Time complexity: O(n*log(n)), n is the number of vertices.
344 // Space complexity: O(n)
345 // params:
346 // inpolys:
347 // A list of polygons to be triangulated (can contain holes).
348 // Vertices of all non-hole polys have to be in counter-clockwise order.
349 // Vertices of all hole polys have to be in clockwise order.
350 // triangles:
351 // A list of triangles (result).
352 // Returns 1 on success, 0 on failure.
353 int Triangulate_MONO(TPPLPolyList *inpolys, TPPLPolyList *triangles);
354
355 // Creates a monotone partition of a list of polygons that
356 // can contain holes. Triangulates a set of polygons by
357 // first partitioning them into monotone polygons.
358 // Time complexity: O(n*log(n)), n is the number of vertices.
359 // Space complexity: O(n)
360 // params:
361 // inpolys:
362 // A list of polygons to be triangulated (can contain holes).
363 // Vertices of all non-hole polys have to be in counter-clockwise order.
364 // Vertices of all hole polys have to be in clockwise order.
365 // monotonePolys:
366 // A list of monotone polygons (result).
367 // Returns 1 on success, 0 on failure.
368 int MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monotonePolys);
369
370 // Partitions a polygon into convex polygons by using the
371 // Hertel-Mehlhorn algorithm. The algorithm gives at most four times
372 // the number of parts as the optimal algorithm, however, in practice
373 // it works much better than that and often gives optimal partition.
374 // It uses triangulation obtained by ear clipping as intermediate result.
375 // Time complexity O(n^2), n is the number of vertices.
376 // Space complexity: O(n)
377 // params:
378 // poly:
379 // An input polygon to be partitioned.
380 // Vertices have to be in counter-clockwise order.
381 // parts:
382 // Resulting list of convex polygons.
383 // Returns 1 on success, 0 on failure.
384 int ConvexPartition_HM(TPPLPoly *poly, TPPLPolyList *parts);
385
386 // Partitions a list of polygons into convex parts by using the
387 // Hertel-Mehlhorn algorithm. The algorithm gives at most four times
388 // the number of parts as the optimal algorithm, however, in practice
389 // it works much better than that and often gives optimal partition.
390 // It uses triangulation obtained by ear clipping as intermediate result.
391 // Time complexity O(n^2), n is the number of vertices.
392 // Space complexity: O(n)
393 // params:
394 // inpolys:
395 // An input list of polygons to be partitioned. Vertices of
396 // all non-hole polys have to be in counter-clockwise order.
397 // Vertices of all hole polys have to be in clockwise order.
398 // parts:
399 // Resulting list of convex polygons.
400 // Returns 1 on success, 0 on failure.
401 int ConvexPartition_HM(TPPLPolyList *inpolys, TPPLPolyList *parts);
402
403 // Optimal convex partitioning (in terms of number of resulting
404 // convex polygons) using the Keil-Snoeyink algorithm.
405 // For reference, see M. Keil, J. Snoeyink, "On the time bound for
406 // convex decomposition of simple polygons", 1998.
407 // Time complexity O(n^3), n is the number of vertices.
408 // Space complexity: O(n^3)
409 // params:
410 // poly:
411 // An input polygon to be partitioned.
412 // Vertices have to be in counter-clockwise order.
413 // parts:
414 // Resulting list of convex polygons.
415 // Returns 1 on success, 0 on failure.
416 int ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts);
417};
418
419#endif
Definition polypartition.h:197
Definition polypartition.h:176
Definition polypartition.h:92
Definition polypartition.h:225
Definition polypartition.h:218
Definition polypartition.h:206
Definition polypartition.h:191
Definition polypartition.h:178
Definition polypartition.h:232
Definition polypartition.h:47