src/livarot/Shape.h

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