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 |