Horizon
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 
30 typedef double tppl_float;
31 
32 enum TPPLOrientation {
33  TPPL_ORIENTATION_CW = -1,
34  TPPL_ORIENTATION_NONE = 0,
35  TPPL_ORIENTATION_CCW = 1,
36 };
37 
38 enum 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.
47 struct 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.
92 class 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
171 typedef std::list<TPPLPoly, TPPL_ALLOCATOR(TPPLPoly)> TPPLPolyList;
172 #else
173 typedef 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 
188  PartitionVertex();
189  };
190 
191  struct MonotoneVertex {
192  TPPLPoint p;
193  long previous;
194  long next;
195  };
196 
197  class VertexSorter {
198  MonotoneVertex *vertices;
199 
200 public:
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.
232  struct ScanLineEdge {
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