← Back to branch summary

~ubuntu-branches/ubuntu/utopic/slic3r/utopic

« back to all changes in this revision

Viewing changes to xs/src/polypartition.h

  • Committer: Package Import Robot
  • Author(s): Chow Loong Jin
  • Date: 2014-06-17 01:27:26 UTC
  • Revision ID: package-import@ubuntu.com-20140617012726-2wrs4zdo251nr4vg
Tags: upstream-1.1.4+dfsg
Import upstream version 1.1.4+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
xs/src/polypartition.h
 
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
 
 
22
#include <list>
 
23
using namespace std;
 
24
 
 
25
typedef double tppl_float;
 
26
 
 
27
#define TPPL_CCW 1
 
28
#define TPPL_CW -1
 
29
 
 
30
//2D point structure
 
31
struct TPPLPoint {
 
32
        tppl_float x;
 
33
        tppl_float y;
 
34
 
 
35
        TPPLPoint operator + (const TPPLPoint& p) const {
 
36
                TPPLPoint r;
 
37
                r.x = x + p.x;
 
38
                r.y = y + p.y;
 
39
                return r;
 
40
        }
 
41
 
 
42
        TPPLPoint operator - (const TPPLPoint& p) const {
 
43
                TPPLPoint r;
 
44
                r.x = x - p.x;
 
45
                r.y = y - p.y;
 
46
                return r;
 
47
        }
 
48
 
 
49
        TPPLPoint operator * (const tppl_float f ) const {
 
50
                TPPLPoint r;
 
51
                r.x = x*f;
 
52
                r.y = y*f;
 
53
                return r;
 
54
        }
 
55
 
 
56
        TPPLPoint operator / (const tppl_float f ) const {
 
57
                TPPLPoint r;
 
58
                r.x = x/f;
 
59
                r.y = y/f;
 
60
                return r;
 
61
        }
 
62
 
 
63
        bool operator==(const TPPLPoint& p) const {
 
64
                if((x == p.x)&&(y==p.y)) return true;
 
65
                else return false;
 
66
        }
 
67
 
 
68
        bool operator!=(const TPPLPoint& p) const {
 
69
                if((x == p.x)&&(y==p.y)) return false;
 
70
                else return true;
 
71
        }
 
72
};
 
73
 
 
74
//Polygon implemented as an array of points with a 'hole' flag
 
75
class TPPLPoly {
 
76
protected:
 
77
 
 
78
        TPPLPoint *points;
 
79
        long numpoints;
 
80
        bool hole;
 
81
 
 
82
public:
 
83
 
 
84
        //constructors/destructors
 
85
        TPPLPoly();
 
86
        ~TPPLPoly();
 
87
 
 
88
        TPPLPoly(const TPPLPoly &src);
 
89
        TPPLPoly& operator=(const TPPLPoly &src);
 
90
 
 
91
        //getters and setters
 
92
        long GetNumPoints() {
 
93
                return numpoints;
 
94
        }
 
95
 
 
96
        bool IsHole() {
 
97
                return hole;
 
98
        }
 
99
 
 
100
        void SetHole(bool hole) {
 
101
                this->hole = hole;
 
102
        }
 
103
 
 
104
        TPPLPoint &GetPoint(long i) {
 
105
                return points[i];
 
106
        }
 
107
 
 
108
        TPPLPoint *GetPoints() {
 
109
                return points;
 
110
        }
 
111
 
 
112
        TPPLPoint& operator[] (int i) {
 
113
                return points[i];       
 
114
        }
 
115
 
 
116
        //clears the polygon points
 
117
        void Clear();
 
118
 
 
119
        //inits the polygon with numpoints vertices
 
120
        void Init(long numpoints);
 
121
 
 
122
        //creates a triangle with points p1,p2,p3
 
123
        void Triangle(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3);
 
124
 
 
125
        //inverts the orfer of vertices
 
126
        void Invert();
 
127
 
 
128
        //returns the orientation of the polygon
 
129
        //possible values:
 
130
        //   TPPL_CCW : polygon vertices are in counter-clockwise order
 
131
        //   TPPL_CW : polygon vertices are in clockwise order
 
132
        //       0 : the polygon has no (measurable) area
 
133
        int GetOrientation();
 
134
 
 
135
        //sets the polygon orientation
 
136
        //orientation can be
 
137
        //   TPPL_CCW : sets vertices in counter-clockwise order
 
138
        //   TPPL_CW : sets vertices in clockwise order
 
139
        void SetOrientation(int orientation);
 
140
};
 
141
 
 
142
class TPPLPartition {
 
143
protected:
 
144
        struct PartitionVertex {
 
145
                bool isActive;
 
146
                bool isConvex;
 
147
                bool isEar;
 
148
 
 
149
                TPPLPoint p;
 
150
                tppl_float angle;
 
151
                PartitionVertex *previous;
 
152
                PartitionVertex *next;
 
153
        };
 
154
 
 
155
        struct MonotoneVertex {
 
156
                TPPLPoint p;
 
157
                long previous;
 
158
                long next;
 
159
        };
 
160
 
 
161
        class VertexSorter{
 
162
                MonotoneVertex *vertices;
 
163
        public:
 
164
                VertexSorter(MonotoneVertex *v) : vertices(v) {}
 
165
                bool operator() (long index1, long index2);
 
166
        };
 
167
 
 
168
        struct Diagonal {
 
169
                long index1;
 
170
                long index2;
 
171
        };
 
172
 
 
173
        //dynamic programming state for minimum-weight triangulation
 
174
        struct DPState {
 
175
                bool visible;
 
176
                tppl_float weight;
 
177
                long bestvertex;
 
178
        };
 
179
 
 
180
        //dynamic programming state for convex partitioning
 
181
        struct DPState2 {
 
182
                bool visible;
 
183
                long weight;
 
184
                list<Diagonal> pairs;
 
185
        };
 
186
 
 
187
        //edge that intersects the scanline
 
188
        struct ScanLineEdge {
 
189
                long index;
 
190
                TPPLPoint p1;
 
191
                TPPLPoint p2;
 
192
 
 
193
                //determines if the edge is to the left of another edge
 
194
                bool operator< (const ScanLineEdge & other) const;
 
195
 
 
196
                bool IsConvex(const TPPLPoint& p1, const TPPLPoint& p2, const TPPLPoint& p3) const;
 
197
        };
 
198
 
 
199
        //standard helper functions
 
200
        bool IsConvex(TPPLPoint& p1, TPPLPoint& p2, TPPLPoint& p3);
 
201
        bool IsReflex(TPPLPoint& p1, TPPLPoint& p2, TPPLPoint& p3);
 
202
        bool IsInside(TPPLPoint& p1, TPPLPoint& p2, TPPLPoint& p3, TPPLPoint &p);
 
203
        
 
204
        bool InCone(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3, TPPLPoint &p);
 
205
        bool InCone(PartitionVertex *v, TPPLPoint &p);
 
206
 
 
207
        int Intersects(TPPLPoint &p11, TPPLPoint &p12, TPPLPoint &p21, TPPLPoint &p22);
 
208
 
 
209
        TPPLPoint Normalize(const TPPLPoint &p);
 
210
        tppl_float Distance(const TPPLPoint &p1, const TPPLPoint &p2);
 
211
 
 
212
        //helper functions for Triangulate_EC
 
213
        void UpdateVertexReflexity(PartitionVertex *v);
 
214
        void UpdateVertex(PartitionVertex *v,PartitionVertex *vertices, long numvertices);
 
215
 
 
216
        //helper functions for ConvexPartition_OPT
 
217
        void UpdateState(long a, long b, long w, long i, long j, DPState2 **dpstates);
 
218
        void TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates);
 
219
        void TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates);
 
220
 
 
221
        //helper functions for MonotonePartition
 
222
        bool Below(TPPLPoint &p1, TPPLPoint &p2);
 
223
        void AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2);
 
224
 
 
225
        //triangulates a monotone polygon, used in Triangulate_MONO
 
226
        int TriangulateMonotone(TPPLPoly *inPoly, list<TPPLPoly> *triangles);
 
227
 
 
228
public:
 
229
 
 
230
        //simple heuristic procedure for removing holes from a list of polygons
 
231
        //works by creating a diagonal from the rightmost hole vertex to some visible vertex
 
232
        //time complexity: O(h*(n^2)), h is the number of holes, n is the number of vertices
 
233
        //space complexity: O(n)
 
234
        //params:
 
235
        //   inpolys : a list of polygons that can contain holes
 
236
        //             vertices of all non-hole polys have to be in counter-clockwise order
 
237
        //             vertices of all hole polys have to be in clockwise order
 
238
        //   outpolys : a list of polygons without holes
 
239
        //returns 1 on success, 0 on failure
 
240
        int RemoveHoles(list<TPPLPoly> *inpolys, list<TPPLPoly> *outpolys);
 
241
 
 
242
        //triangulates a polygon by ear clipping
 
243
        //time complexity O(n^2), n is the number of vertices
 
244
        //space complexity: O(n)
 
245
        //params:
 
246
        //   poly : an input polygon to be triangulated
 
247
        //          vertices have to be in counter-clockwise order
 
248
        //   triangles : a list of triangles (result)
 
249
        //returns 1 on success, 0 on failure
 
250
        int Triangulate_EC(TPPLPoly *poly, list<TPPLPoly> *triangles);
 
251
 
 
252
        //triangulates a list of polygons that may contain holes by ear clipping algorithm
 
253
        //first calls RemoveHoles to get rid of the holes, and then Triangulate_EC for each resulting polygon
 
254
        //time complexity: O(h*(n^2)), h is the number of holes, n is the number of vertices
 
255
        //space complexity: O(n)
 
256
        //params:
 
257
        //   inpolys : a list of polygons to be triangulated (can contain holes)
 
258
        //             vertices of all non-hole polys have to be in counter-clockwise order
 
259
        //             vertices of all hole polys have to be in clockwise order
 
260
        //   triangles : a list of triangles (result)
 
261
        //returns 1 on success, 0 on failure
 
262
        int Triangulate_EC(list<TPPLPoly> *inpolys, list<TPPLPoly> *triangles);
 
263
 
 
264
        //creates an optimal polygon triangulation in terms of minimal edge length
 
265
        //time complexity: O(n^3), n is the number of vertices
 
266
        //space complexity: O(n^2)
 
267
        //params:
 
268
        //   poly : an input polygon to be triangulated
 
269
        //          vertices have to be in counter-clockwise order
 
270
        //   triangles : a list of triangles (result)
 
271
        //returns 1 on success, 0 on failure
 
272
        int Triangulate_OPT(TPPLPoly *poly, list<TPPLPoly> *triangles);
 
273
 
 
274
        //triangulates a polygons by firstly partitioning it into monotone polygons
 
275
        //time complexity: O(n*log(n)), n is the number of vertices
 
276
        //space complexity: O(n)
 
277
        //params:
 
278
        //   poly : an input polygon to be triangulated
 
279
        //          vertices have to be in counter-clockwise order
 
280
        //   triangles : a list of triangles (result)
 
281
        //returns 1 on success, 0 on failure
 
282
        int Triangulate_MONO(TPPLPoly *poly, list<TPPLPoly> *triangles);
 
283
 
 
284
        //triangulates a list of polygons by firstly partitioning them into monotone polygons
 
285
        //time complexity: O(n*log(n)), n is the number of vertices
 
286
        //space complexity: O(n)
 
287
        //params:
 
288
        //   inpolys : a list of polygons to be triangulated (can contain holes)
 
289
        //             vertices of all non-hole polys have to be in counter-clockwise order
 
290
        //             vertices of all hole polys have to be in clockwise order
 
291
        //   triangles : a list of triangles (result)
 
292
        //returns 1 on success, 0 on failure
 
293
        int Triangulate_MONO(list<TPPLPoly> *inpolys, list<TPPLPoly> *triangles);
 
294
 
 
295
        //creates a monotone partition of a list of polygons that can contain holes
 
296
        //time complexity: O(n*log(n)), n is the number of vertices
 
297
        //space complexity: O(n)
 
298
        //params:
 
299
        //   inpolys : a list of polygons to be triangulated (can contain holes)
 
300
        //             vertices of all non-hole polys have to be in counter-clockwise order
 
301
        //             vertices of all hole polys have to be in clockwise order
 
302
        //   monotonePolys : a list of monotone polygons (result)
 
303
        //returns 1 on success, 0 on failure
 
304
        int MonotonePartition(list<TPPLPoly> *inpolys, list<TPPLPoly> *monotonePolys);
 
305
 
 
306
        //partitions a polygon into convex polygons by using Hertel-Mehlhorn algorithm
 
307
        //the algorithm gives at most four times the number of parts as the optimal algorithm
 
308
        //however, in practice it works much better than that and often gives optimal partition
 
309
        //uses triangulation obtained by ear clipping as intermediate result
 
310
        //time complexity O(n^2), n is the number of vertices
 
311
        //space complexity: O(n)
 
312
        //params:
 
313
        //   poly : an input polygon to be partitioned
 
314
        //          vertices have to be in counter-clockwise order
 
315
        //   parts : resulting list of convex polygons
 
316
        //returns 1 on success, 0 on failure
 
317
        int ConvexPartition_HM(TPPLPoly *poly, list<TPPLPoly> *parts);
 
318
 
 
319
        //partitions a list of polygons into convex parts by using Hertel-Mehlhorn algorithm
 
320
        //the algorithm gives at most four times the number of parts as the optimal algorithm
 
321
        //however, in practice it works much better than that and often gives optimal partition
 
322
        //uses triangulation obtained by ear clipping as intermediate result
 
323
        //time complexity O(n^2), n is the number of vertices
 
324
        //space complexity: O(n)
 
325
        //params:
 
326
        //   inpolys : an input list of polygons to be partitioned
 
327
        //             vertices of all non-hole polys have to be in counter-clockwise order
 
328
        //             vertices of all hole polys have to be in clockwise order
 
329
        //   parts : resulting list of convex polygons
 
330
        //returns 1 on success, 0 on failure
 
331
        int ConvexPartition_HM(list<TPPLPoly> *inpolys, list<TPPLPoly> *parts);
 
332
 
 
333
        //optimal convex partitioning (in terms of number of resulting convex polygons)
 
334
        //using the Keil-Snoeyink algorithm
 
335
        //M. Keil, J. Snoeyink, "On the time bound for convex decomposition of simple polygons", 1998
 
336
        //time complexity O(n^3), n is the number of vertices
 
337
        //space complexity: O(n^3)
 
338
        //   poly : an input polygon to be partitioned
 
339
        //          vertices have to be in counter-clockwise order
 
340
        //   parts : resulting list of convex polygons
 
341
        //returns 1 on success, 0 on failure
 
342
        int ConvexPartition_OPT(TPPLPoly *poly, list<TPPLPoly> *parts);
 
343
};