GCC Code Coverage Report


Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 87.5% 21 / 0 / 24
Functions: 80.0% 8 / 0 / 10
Branches: -% 0 / 0 / 0

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