1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /** @file 3 * TODO: insert short description here 4 *//* 5 * Authors: see git history 6 * 7 * Copyright (C) 2018 Authors 8 * Released under GNU GPL v2+, read the file 'COPYING' for more information. 9 */ 10 11 #ifndef my_shape 12 #define my_shape 13 14 #include <cmath> 15 #include <cstdio> 16 #include <cstdlib> 17 #include <cstring> 18 #include <vector> 19 #include <2geom/point.h> 20 21 #include "livarot/LivarotDefs.h" 22 #include "object/object-set.h" // For BooleanOp 23 24 class Path; 25 class FloatLigne; 26 27 class SweepTree; 28 class SweepTreeList; 29 class SweepEventQueue; 30 31 enum { 32 tweak_mode_grow, 33 tweak_mode_push, 34 tweak_mode_repel, 35 tweak_mode_roughen 36 }; 37 38 /* 39 * the Shape class (was the Digraph class, as the header says) stores digraphs (no kidding!) of which 40 * a very interesting kind are polygons. 41 * the main use of this class is the ConvertToShape() (or Booleen(), quite the same) function, which 42 * removes all problems a polygon can present: duplicate points or edges, self-intersection. you end up with a 43 * full-fledged polygon 44 */ 45 46 // possible values for the "type" field in the Shape class: 47 enum 48 { 49 shape_graph = 0, // it's just a graph; a bunch of edges, maybe intersections 50 shape_polygon = 1, // a polygon: intersection-free, edges oriented so that the inside is on their left 51 shape_polypatch = 2 // a graph without intersection; each face is a polygon (not yet used) 52 }; 53 54 class BitLigne; 55 class AlphaLigne; 56 57 class Shape 58 { 59 public: 60 61 struct back_data 62 { 63 int pathID, pieceID; 64 double tSt, tEn; 65 }; 66 67 struct voronoi_point 68 { // info for points treated as points of a voronoi diagram (obtained by MakeShape()) 69 double value; // distance to source 70 int winding; // winding relatively to source 71 }; 72 73 struct voronoi_edge 74 { // info for edges, treated as approximation of edges of the voronoi diagram 75 int leF, riF; // left and right site 76 double leStX, leStY, riStX, riStY; // on the left side: (leStX,leStY) is the smallest vector from the source to st 77 // etc... 78 double leEnX, leEnY, riEnX, riEnY; 79 }; 80 81 struct quick_raster_data 82 { 83 double x; // x-position on the sweepline 84 int bord; // index of the edge 85 int ind; // index of qrsData elem for edge (ie inverse of the bord) 86 int next,prev; // dbl linkage 87 }; 88 89 enum sTreeChangeType 90 { 91 EDGE_INSERTED = 0, 92 EDGE_REMOVED = 1, 93 INTERSECTION = 2 94 }; 95 96 struct sTreeChange 97 { 98 sTreeChangeType type; // type of modification to the sweepline: 99 int ptNo; // point at which the modification takes place 100 101 Shape *src; // left edge (or unique edge if not an intersection) involved in the event 102 int bord; 103 Shape *osrc; // right edge (if intersection) 104 int obord; 105 Shape *lSrc; // edge directly on the left in the sweepline at the moment of the event 106 int lBrd; 107 Shape *rSrc; // edge directly on the right 108 int rBrd; 109 }; 110 111 struct incidenceData 112 { 113 int nextInc; // next incidence in the linked list 114 int pt; // point incident to the edge (there is one list per edge) 115 double theta; // coordinate of the incidence on the edge 116 }; 117 118 Shape(); 119 virtual ~Shape(); 120 121 void MakeBackData(bool nVal); 122 void MakeVoronoiData(bool nVal); 123 124 void Affiche(); 125 126 // insertion/deletion/movement of elements in the graph 127 void Copy(Shape *a); 128 // -reset the graph, and ensure there's room for n points and m edges 129 void Reset(int n = 0, int m = 0); 130 // -points: 131 int AddPoint(const Geom::Point x); // as the function name says 132 // returns the index at which the point has been added in the array 133 void SubPoint(int p); // removes the point at index p 134 // nota: this function relocates the last point to the index p 135 // so don't trust point indices if you use SubPoint 136 void SwapPoints(int a, int b); // swaps 2 points at indices a and b 137 void SwapPoints(int a, int b, int c); // swaps 3 points: c <- a <- b <- c 138 void SortPoints(); // sorts the points if needed (checks the need_points_sorting flag) 139 140 // -edges: 141 // add an edge between points of indices st and en 142 int AddEdge(int st, int en); 143 // return the edge index in the array 144 145 // add an edge between points of indices st and en 146 int AddEdge(int st, int en, int leF, int riF); 147 // return the edge index in the array 148 149 // version for the voronoi (with faces IDs) 150 void SubEdge(int e); // removes the edge at index e (same remarks as for SubPoint) 151 void SwapEdges(int a, int b); // swaps 2 edges 152 void SwapEdges(int a, int b, int c); // swaps 3 edges 153 void SortEdges(); // sort the edges if needed (checks the need_edges_sorting falg) 154 155 // primitives for topological manipulations 156 157 // endpoint of edge at index b that is different from the point p Other(int p,int b)158 inline int Other(int p, int b) const 159 { 160 if (getEdge(b).st == p) { 161 return getEdge(b).en; 162 } 163 return getEdge(b).st; 164 } 165 166 // next edge (after edge b) in the double-linked list at point p NextAt(int p,int b)167 inline int NextAt(int p, int b) const 168 { 169 if (p == getEdge(b).st) { 170 return getEdge(b).nextS; 171 } 172 else if (p == getEdge(b).en) { 173 return getEdge(b).nextE; 174 } 175 176 return -1; 177 } 178 179 // previous edge PrevAt(int p,int b)180 inline int PrevAt(int p, int b) const 181 { 182 if (p == getEdge(b).st) { 183 return getEdge(b).prevS; 184 } 185 else if (p == getEdge(b).en) { 186 return getEdge(b).prevE; 187 } 188 189 return -1; 190 } 191 192 // same as NextAt, but the list is considered circular CycleNextAt(int p,int b)193 inline int CycleNextAt(int p, int b) const 194 { 195 if (p == getEdge(b).st) { 196 if (getEdge(b).nextS < 0) { 197 return getPoint(p).incidentEdge[FIRST]; 198 } 199 return getEdge(b).nextS; 200 } else if (p == getEdge(b).en) { 201 if (getEdge(b).nextE < 0) { 202 return getPoint(p).incidentEdge[FIRST]; 203 } 204 205 return getEdge(b).nextE; 206 } 207 208 return -1; 209 } 210 211 // same as PrevAt, but the list is considered circular CyclePrevAt(int p,int b)212 inline int CyclePrevAt(int p, int b) const 213 { 214 if (p == getEdge(b).st) { 215 if (getEdge(b).prevS < 0) { 216 return getPoint(p).incidentEdge[LAST]; 217 } 218 return getEdge(b).prevS; 219 } else if (p == getEdge(b).en) { 220 if (getEdge(b).prevE < 0) { 221 return getPoint(p).incidentEdge[LAST]; 222 } 223 return getEdge(b).prevE; 224 } 225 226 return -1; 227 } 228 229 void ConnectStart(int p, int b); // set the point p as the start of edge b 230 void ConnectEnd(int p, int b); // set the point p as the end of edge b 231 void DisconnectStart(int b); // disconnect edge b from its start point 232 void DisconnectEnd(int b); // disconnect edge b from its end point 233 234 // reverses edge b (start <-> end) 235 void Inverse(int b); 236 // calc bounding box and sets leftX,rightX,topY and bottomY to their values 237 void CalcBBox(bool strict_degree = false); 238 239 // debug function: plots the graph (mac only) 240 void Plot(double ix, double iy, double ir, double mx, double my, bool doPoint, 241 bool edgesNo, bool pointNo, bool doDir, char *fileName); 242 243 // transforms a polygon in a "forme" structure, ie a set of contours, which can be holes (see ShapeUtils.h) 244 // return NULL in case it's not possible 245 void ConvertToForme(Path *dest); 246 247 // version to use when conversion was done with ConvertWithBackData(): will attempt to merge segment belonging to 248 // the same curve 249 // nota: apparently the function doesn't like very small segments of arc 250 void ConvertToForme(Path *dest, int nbP, Path **orig, bool splitWhenForced = false); 251 // version trying to recover the nesting of subpaths (ie: holes) 252 void ConvertToFormeNested(Path *dest, int nbP, Path **orig, int wildPath, int &nbNest, 253 int *&nesting, int *&contStart, bool splitWhenForced = false); 254 255 // sweeping a digraph to produce a intersection-free polygon 256 // return 0 if everything is ok and a return code otherwise (see LivarotDefs.h) 257 // the input is the Shape "a" 258 // directed=true <=> non-zero fill rule 259 int ConvertToShape(Shape *a, FillRule directed = fill_nonZero, bool invert = false); 260 // directed=false <=> even-odd fill rule 261 // invert=true: make as if you inverted all edges in the source 262 int Reoriente(Shape *a); // subcase of ConvertToShape: the input a is already intersection-free 263 // all that's missing are the correct directions of the edges 264 // Reoriented is equivalent to ConvertToShape(a,false,false) , but faster sicne 265 // it doesn't computes interections nor adjacencies 266 void ForceToPolygon(); // force the Shape to believe it's a polygon (eulerian+intersection-free+no 267 // duplicate edges+no duplicate points) 268 // be careful when using this function 269 270 // the coordinate rounding function Round(double x)271 inline static double Round(double x) 272 { 273 return ldexp(rint(ldexp(x, 9)), -9); 274 } 275 276 // 2 miscannellous variations on it, to scale to and back the rounding grid HalfRound(double x)277 inline static double HalfRound(double x) 278 { 279 return ldexp(x, -9); 280 } 281 IHalfRound(double x)282 inline static double IHalfRound(double x) 283 { 284 return ldexp(x, 9); 285 } 286 287 // boolean operations on polygons (requests intersection-free poylygons) 288 // boolean operation types are defined in LivarotDefs.h 289 // same return code as ConvertToShape 290 int Booleen(Shape *a, Shape *b, BooleanOp mod, int cutPathID = -1); 291 292 // create a graph that is an offseted version of the graph "of" 293 // the offset is dec, with joins between edges of type "join" (see LivarotDefs.h) 294 // the result is NOT a polygon; you need a subsequent call to ConvertToShape to get a real polygon 295 int MakeOffset(Shape *of, double dec, JoinType join, double miter, bool do_profile=false, double cx = 0, double cy = 0, double radius = 0, Geom::Affine *i2doc = nullptr); 296 297 int MakeTweak (int mode, Shape *a, double dec, JoinType join, double miter, bool do_profile, Geom::Point c, Geom::Point vector, double radius, Geom::Affine *i2doc); 298 299 int PtWinding(const Geom::Point px) const; // plus rapide 300 int Winding(const Geom::Point px) const; 301 302 // rasterization 303 void BeginRaster(float &pos, int &curPt); 304 void EndRaster(); 305 void BeginQuickRaster(float &pos, int &curPt); 306 void EndQuickRaster(); 307 308 void Scan(float &pos, int &curP, float to, float step); 309 void QuickScan(float &pos, int &curP, float to, bool doSort, float step); 310 void DirectScan(float &pos, int &curP, float to, float step); 311 void DirectQuickScan(float &pos, int &curP, float to, bool doSort, float step); 312 313 void Scan(float &pos, int &curP, float to, FloatLigne *line, bool exact, float step); 314 void Scan(float &pos, int &curP, float to, FillRule directed, BitLigne *line, bool exact, float step); 315 void Scan(float &pos, int &curP, float to, AlphaLigne *line, bool exact, float step); 316 317 void QuickScan(float &pos, int &curP, float to, FloatLigne* line, float step); 318 void QuickScan(float &pos, int &curP, float to, FillRule directed, BitLigne* line, float step); 319 void QuickScan(float &pos, int &curP, float to, AlphaLigne* line, float step); 320 Transform(Geom::Affine const & tr)321 void Transform(Geom::Affine const &tr) 322 {for(auto & _pt : _pts) _pt.x*=tr;} 323 324 std::vector<back_data> ebData; 325 std::vector<voronoi_point> vorpData; 326 std::vector<voronoi_edge> voreData; 327 328 int nbQRas; 329 int firstQRas; 330 int lastQRas; 331 quick_raster_data *qrsData; 332 333 std::vector<sTreeChange> chgts; 334 int nbInc; 335 int maxInc; 336 337 incidenceData *iData; 338 // these ones are allocated at the beginning of each sweep and freed at the end of the sweep 339 SweepTreeList *sTree; 340 SweepEventQueue *sEvts; 341 342 // bounding box stuff 343 double leftX, topY, rightX, bottomY; 344 345 // topological information: who links who? 346 struct dg_point 347 { 348 Geom::Point x; // position 349 int dI, dO; // indegree and outdegree 350 int incidentEdge[2]; // first and last incident edge 351 int oldDegree; 352 totalDegreedg_point353 int totalDegree() const { return dI + dO; } 354 }; 355 356 struct dg_arete 357 { 358 Geom::Point dx; // edge vector 359 int st, en; // start and end points of the edge 360 int nextS, prevS; // next and previous edge in the double-linked list at the start point 361 int nextE, prevE; // next and previous edge in the double-linked list at the end point 362 }; 363 364 // lists of the nodes and edges 365 int maxPt; // [FIXME: remove this] 366 int maxAr; // [FIXME: remove this] 367 368 // flags 369 int type; 370 numberOfPoints()371 inline int numberOfPoints() const { return _pts.size(); } hasPoints()372 inline bool hasPoints() const { return (_pts.empty() == false); } numberOfEdges()373 inline int numberOfEdges() const { return _aretes.size(); } hasEdges()374 inline bool hasEdges() const { return (_aretes.empty() == false); } 375 needPointsSorting()376 inline void needPointsSorting() { _need_points_sorting = true; } needEdgesSorting()377 inline void needEdgesSorting() { _need_edges_sorting = true; } 378 hasBackData()379 inline bool hasBackData() const { return _has_back_data; } 380 getPoint(int n)381 inline dg_point const &getPoint(int n) const { return _pts[n]; } getEdge(int n)382 inline dg_arete const &getEdge(int n) const { return _aretes[n]; } 383 384 private: 385 386 friend class SweepTree; 387 friend class SweepEvent; 388 friend class SweepEventQueue; 389 390 // temporary data for the various algorithms 391 struct edge_data 392 { 393 int weight; // weight of the edge (to handle multiple edges) 394 Geom::Point rdx; // rounded edge vector 395 double length, sqlength, ilength, isqlength; // length^2, length, 1/length^2, 1/length 396 double siEd, coEd; // siEd=abs(rdy/length) and coEd=rdx/length edge_dataedge_data397 edge_data() : weight(0), length(0.0), sqlength(0.0), ilength(0.0), isqlength(0.0), siEd(0.0), coEd(0.0) {} 398 // used to determine the "most horizontal" edge between 2 edges 399 }; 400 401 struct sweep_src_data 402 { 403 void *misc; // pointer to the SweepTree* in the sweepline 404 int firstLinkedPoint; // not used 405 int stPt, enPt; // start- end end- points for this edge in the resulting polygon 406 int ind; // for the GetAdjacencies function: index in the sliceSegs array (for quick deletions) 407 int leftRnd, rightRnd; // leftmost and rightmost points (in the result polygon) that are incident to 408 // the edge, for the current sweep position 409 // not set if the edge doesn't start/end or intersect at the current sweep position 410 Shape *nextSh; // nextSh and nextBo identify the next edge in the list 411 int nextBo; // they are used to maintain a linked list of edge that start/end or intersect at 412 // the current sweep position 413 int curPoint, doneTo; 414 double curT; 415 }; 416 417 struct sweep_dest_data 418 { 419 void *misc; // used to check if an edge has already been seen during the depth-first search 420 int suivParc, precParc; // previous and current next edge in the depth-first search 421 int leW, riW; // left and right winding numbers for this edge 422 int ind; // order of the edges during the depth-first search 423 }; 424 425 struct raster_data 426 { 427 SweepTree *misc; // pointer to the associated SweepTree* in the sweepline 428 double lastX, lastY, curX, curY; // curX;curY is the current intersection of the edge with the sweepline 429 // lastX;lastY is the intersection with the previous sweepline 430 bool sens; // true if the edge goes down, false otherwise 431 double calcX; // horizontal position of the intersection of the edge with the 432 // previous sweepline 433 double dxdy, dydx; // horizontal change per unit vertical move of the intersection with the sweepline 434 int guess; 435 }; 436 437 struct point_data 438 { 439 int oldInd, newInd; // back and forth indices used when sorting the points, to know where they have 440 // been relocated in the array 441 int pending; // number of intersection attached to this edge, and also used when sorting arrays 442 int edgeOnLeft; // not used (should help speeding up winding calculations) 443 int nextLinkedPoint; // not used 444 Shape *askForWindingS; 445 int askForWindingB; 446 Geom::Point rx; // rounded coordinates of the point 447 }; 448 449 450 struct edge_list 451 { // temporary array of edges for easier sorting 452 int no; 453 bool starting; 454 Geom::Point x; 455 }; 456 457 void initialisePointData(); 458 void initialiseEdgeData(); 459 void clearIncidenceData(); 460 461 void _countUpDown(int P, int *numberUp, int *numberDown, int *upEdge, int *downEdge) const; 462 void _countUpDownTotalDegree2(int P, int *numberUp, int *numberDown, int *upEdge, int *downEdge) const; 463 void _updateIntersection(int e, int p); 464 465 // activation/deactivation of the temporary data arrays 466 void MakePointData(bool nVal); 467 void MakeEdgeData(bool nVal); 468 void MakeSweepSrcData(bool nVal); 469 void MakeSweepDestData(bool nVal); 470 void MakeRasterData(bool nVal); 471 void MakeQuickRasterData(bool nVal); 472 473 void SortPoints(int s, int e); 474 void SortPointsByOldInd(int s, int e); 475 476 // fonctions annexes pour ConvertToShape et Booleen 477 void ResetSweep(); // allocates sweep structures 478 void CleanupSweep(); // deallocates them 479 480 // edge sorting function 481 void SortEdgesList(edge_list *edges, int s, int e); 482 483 void TesteIntersection(SweepTree *t, Side s, bool onlyDiff); // test if there is an intersection 484 bool TesteIntersection(SweepTree *iL, SweepTree *iR, Geom::Point &atx, double &atL, double &atR, bool onlyDiff); 485 bool TesteIntersection(Shape *iL, Shape *iR, int ilb, int irb, 486 Geom::Point &atx, double &atL, double &atR, 487 bool onlyDiff); 488 bool TesteAdjacency(Shape *iL, int ilb, const Geom::Point atx, int nPt, 489 bool push); 490 int PushIncidence(Shape *a, int cb, int pt, double theta); 491 int CreateIncidence(Shape *a, int cb, int pt); 492 void AssemblePoints(Shape *a); 493 int AssemblePoints(int st, int en); 494 void AssembleAretes(FillRule directed = fill_nonZero); 495 void AddChgt(int lastPointNo, int lastChgtPt, Shape *&shapeHead, 496 int &edgeHead, sTreeChangeType type, Shape *lS, int lB, Shape *rS, 497 int rB); 498 void CheckAdjacencies(int lastPointNo, int lastChgtPt, Shape *shapeHead, int edgeHead); 499 void CheckEdges(int lastPointNo, int lastChgtPt, Shape *a, Shape *b, BooleanOp mod); 500 void Avance(int lastPointNo, int lastChgtPt, Shape *iS, int iB, Shape *a, Shape *b, BooleanOp mod); 501 void DoEdgeTo(Shape *iS, int iB, int iTo, bool direct, bool sens); 502 void GetWindings(Shape *a, Shape *b = nullptr, BooleanOp mod = bool_op_union, bool brutal = false); 503 504 void Validate(); 505 506 int Winding(int nPt) const; 507 void SortPointsRounded(); 508 void SortPointsRounded(int s, int e); 509 510 void CreateEdge(int no, float to, float step); 511 void AvanceEdge(int no, float to, bool exact, float step); 512 void DestroyEdge(int no, float to, FloatLigne *line); 513 void AvanceEdge(int no, float to, FloatLigne *line, bool exact, float step); 514 void DestroyEdge(int no, BitLigne *line); 515 void AvanceEdge(int no, float to, BitLigne *line, bool exact, float step); 516 void DestroyEdge(int no, AlphaLigne *line); 517 void AvanceEdge(int no, float to, AlphaLigne *line, bool exact, float step); 518 519 void AddContour(Path * dest, int nbP, Path **orig, int startBord, 520 int curBord, bool splitWhenForced); 521 int ReFormeLineTo(int bord, int curBord, Path *dest, Path *orig); 522 int ReFormeArcTo(int bord, int curBord, Path *dest, Path *orig); 523 int ReFormeCubicTo(int bord, int curBord, Path *dest, Path *orig); 524 int ReFormeBezierTo(int bord, int curBord, Path *dest, Path *orig); 525 void ReFormeBezierChunk(const Geom::Point px, const Geom::Point nx, 526 Path *dest, int inBezier, int nbInterm, 527 Path *from, int p, double ts, double te); 528 529 int QuickRasterChgEdge(int oBord, int nbord, double x); 530 int QuickRasterAddEdge(int bord, double x, int guess); 531 void QuickRasterSubEdge(int bord); 532 void QuickRasterSwapEdge(int a, int b); 533 void QuickRasterSort(); 534 535 bool _need_points_sorting; ///< points have been added or removed: we need to sort the points again 536 bool _need_edges_sorting; ///< edges have been added: maybe they are not ordered clockwise 537 ///< nota: if you remove an edge, the clockwise order still holds 538 bool _has_points_data; ///< the pData array is allocated 539 bool _point_data_initialised;///< the pData array is up to date 540 bool _has_edges_data; ///< the eData array is allocated 541 bool _has_sweep_src_data; ///< the swsData array is allocated 542 bool _has_sweep_dest_data; ///< the swdData array is allocated 543 bool _has_raster_data; ///< the swrData array is allocated 544 bool _has_quick_raster_data;///< the swrData array is allocated 545 bool _has_back_data; //< the ebData array is allocated 546 bool _has_voronoi_data; 547 bool _bbox_up_to_date; ///< the leftX/rightX/topY/bottomY are up to date 548 549 std::vector<dg_point> _pts; 550 std::vector<dg_arete> _aretes; 551 552 // the arrays of temporary data 553 // these ones are dynamically kept at a length of maxPt or maxAr 554 std::vector<edge_data> eData; 555 std::vector<sweep_src_data> swsData; 556 std::vector<sweep_dest_data> swdData; 557 std::vector<raster_data> swrData; 558 std::vector<point_data> pData; 559 CmpQRs(const quick_raster_data & p1,const quick_raster_data & p2)560 static int CmpQRs(const quick_raster_data &p1, const quick_raster_data &p2) { 561 if ( fabs(p1.x - p2.x) < 0.00001 ) { 562 return 0; 563 } 564 565 return ( ( p1.x < p2.x ) ? -1 : 1 ); 566 }; 567 568 // edge direction comparison function 569 static int CmpToVert(const Geom::Point ax, const Geom::Point bx, bool as, bool bs); 570 }; 571 572 bool directedEulerian(Shape const *s); 573 double distance(Shape const *s, Geom::Point const &p); 574 bool distanceLessThanOrEqual(Shape const *s, Geom::Point const &p, double const max_l2); 575 576 #endif 577