src/livarot/sweep-tree.h

   1 #ifndef INKSCAPE_LIVAROT_SWEEP_TREE_H
   2 #define INKSCAPE_LIVAROT_SWEEP_TREE_H
   3
   4 #include "libnr/nr-point.h"
   5 #include "livarot/AVL.h"
   6
   7 class Shape;
   8 class SweepEvent;
   9 class SweepEventQueue;
  10 class SweepTreeList;
  11
  12
  13 /**
  14  * One node in the AVL tree of edges.
  15  * Note that these nodes will be stored in a dynamically allocated array, hence the Relocate() function.
  16  */
  17 class SweepTree:public AVLTree
  18 {
  19 public:
  20     SweepEvent *evt[2];   ///< Intersection with the edge on the left and right (if any).
  21
  22     Shape *src;   /**< Shape from which the edge comes.  (When doing boolean operation on polygons,
  23                    *   edges can come from 2 different polygons.)
  24                    */
  25     int bord;     ///< Edge index in the Shape.
  26     bool sens;    ///< true= top->bottom; false= bottom->top.
  27     int startPoint;   ///< point index in the result Shape associated with the upper end of the edge
  28
  29     SweepTree();
  30     virtual ~SweepTree();
  31
  32     // Inits a brand new node.
  33     void MakeNew(Shape *iSrc, int iBord, int iWeight, int iStartPoint);
  34     // changes the edge associated with this node
  35     // goal: reuse the node when an edge follows another, which is the most common case
  36     void ConvertTo(Shape *iSrc, int iBord, int iWeight, int iStartPoint);
  37
  38     // Delete the contents of node.
  39     void MakeDelete();
  40
  41     // utilites
  42
  43     // the find function that was missing in the AVLTrree class
  44     // the return values are defined in LivarotDefs.h
  45     int Find(Geom::Point const &iPt, SweepTree *newOne, SweepTree *&insertL,
  46              SweepTree *&insertR, bool sweepSens = true);
  47     int Find(Geom::Point const &iPt, SweepTree *&insertL, SweepTree *&insertR);
  48
  49     /// Remove sweepevents attached to this node.
  50     void RemoveEvents(SweepEventQueue &queue);
  51
  52     void RemoveEvent(SweepEventQueue &queue, Side s);
  53
  54     // overrides of the AVLTree functions, to account for the sorting in the tree
  55     // and some other stuff
  56     int Remove(SweepTreeList &list, SweepEventQueue &queue, bool rebalance = true);
  57     int Insert(SweepTreeList &list, SweepEventQueue &queue, Shape *iDst,
  58                int iAtPoint, bool rebalance = true, bool sweepSens = true);
  59     int InsertAt(SweepTreeList &list, SweepEventQueue &queue, Shape *iDst,
  60                  SweepTree *insNode, int fromPt, bool rebalance = true, bool sweepSens = true);
  61
  62     /// Swap nodes, or more exactly, swap the edges in them.
  63     void SwapWithRight(SweepTreeList &list, SweepEventQueue &queue);
  64
  65     void Avance(Shape *dst, int nPt, Shape *a, Shape *b);
  66
  67     void Relocate(SweepTree *to);
  68 };
  69
  70
  71 #endif /* !INKSCAPE_LIVAROT_SWEEP_TREE_H */
  72
  73 /*
  74   Local Variables:
  75   mode:c++
  76   c-file-style:"stroustrup"
  77   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
  78   indent-tabs-mode:nil
  79   fill-column:99
  80   End:
  81 */
  82 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :