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