1
//Copyright (C) 2011 by Ivan Fratric
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:
10
//The above copyright notice and this permission notice shall be included in
11
//all copies or substantial portions of the Software.
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
25
typedef double tppl_float;
35
TPPLPoint operator + (const TPPLPoint& p) const {
42
TPPLPoint operator - (const TPPLPoint& p) const {
49
TPPLPoint operator * (const tppl_float f ) const {
56
TPPLPoint operator / (const tppl_float f ) const {
63
bool operator==(const TPPLPoint& p) const {
64
if((x == p.x)&&(y==p.y)) return true;
68
bool operator!=(const TPPLPoint& p) const {
69
if((x == p.x)&&(y==p.y)) return false;
74
//Polygon implemented as an array of points with a 'hole' flag
84
//constructors/destructors
88
TPPLPoly(const TPPLPoly &src);
89
TPPLPoly& operator=(const TPPLPoly &src);
100
void SetHole(bool hole) {
104
TPPLPoint &GetPoint(long i) {
108
TPPLPoint *GetPoints() {
112
TPPLPoint& operator[] (int i) {
116
//clears the polygon points
119
//inits the polygon with numpoints vertices
120
void Init(long numpoints);
122
//creates a triangle with points p1,p2,p3
123
void Triangle(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3);
125
//inverts the orfer of vertices
128
//returns the orientation of the polygon
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();
135
//sets the polygon orientation
137
// TPPL_CCW : sets vertices in counter-clockwise order
138
// TPPL_CW : sets vertices in clockwise order
139
void SetOrientation(int orientation);
142
class TPPLPartition {
144
struct PartitionVertex {
151
PartitionVertex *previous;
152
PartitionVertex *next;
155
struct MonotoneVertex {
162
MonotoneVertex *vertices;
164
VertexSorter(MonotoneVertex *v) : vertices(v) {}
165
bool operator() (long index1, long index2);
173
//dynamic programming state for minimum-weight triangulation
180
//dynamic programming state for convex partitioning
184
list<Diagonal> pairs;
187
//edge that intersects the scanline
188
struct ScanLineEdge {
193
//determines if the edge is to the left of another edge
194
bool operator< (const ScanLineEdge & other) const;
196
bool IsConvex(const TPPLPoint& p1, const TPPLPoint& p2, const TPPLPoint& p3) const;
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);
204
bool InCone(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3, TPPLPoint &p);
205
bool InCone(PartitionVertex *v, TPPLPoint &p);
207
int Intersects(TPPLPoint &p11, TPPLPoint &p12, TPPLPoint &p21, TPPLPoint &p22);
209
TPPLPoint Normalize(const TPPLPoint &p);
210
tppl_float Distance(const TPPLPoint &p1, const TPPLPoint &p2);
212
//helper functions for Triangulate_EC
213
void UpdateVertexReflexity(PartitionVertex *v);
214
void UpdateVertex(PartitionVertex *v,PartitionVertex *vertices, long numvertices);
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);
221
//helper functions for MonotonePartition
222
bool Below(TPPLPoint &p1, TPPLPoint &p2);
223
void AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2);
225
//triangulates a monotone polygon, used in Triangulate_MONO
226
int TriangulateMonotone(TPPLPoly *inPoly, list<TPPLPoly> *triangles);
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)
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);
242
//triangulates a polygon by ear clipping
243
//time complexity O(n^2), n is the number of vertices
244
//space complexity: O(n)
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);
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)
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);
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)
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);
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)
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);
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)
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);
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)
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);
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)
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);
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)
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);
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);