#ifndef INKSCAPE_LIVAROT_SWEEP_TREE_H #define INKSCAPE_LIVAROT_SWEEP_TREE_H #include "libnr/nr-point.h" #include "livarot/AVL.h" class Shape; class SweepEvent; class SweepEventQueue; class SweepTreeList; /** * One node in the AVL tree of edges. * Note that these nodes will be stored in a dynamically allocated array, hence the Relocate() function. */ 00017 class SweepTree:public AVLTree { public: 00020 SweepEvent *evt[2]; ///< Intersection with the edge on the left and right (if any). 00022 Shape *src; /**< Shape from which the edge comes. (When doing boolean operation on polygons, * edges can come from 2 different polygons.) */ 00025 int bord; ///< Edge index in the Shape. 00026 bool sens; ///< true= top->bottom; false= bottom->top. 00027 int startPoint; ///< point index in the result Shape associated with the upper end of the edge SweepTree(); virtual ~SweepTree(); // Inits a brand new node. void MakeNew(Shape *iSrc, int iBord, int iWeight, int iStartPoint); // changes the edge associated with this node // goal: reuse the node when an edge follows another, which is the most common case void ConvertTo(Shape *iSrc, int iBord, int iWeight, int iStartPoint); // Delete the contents of node. void MakeDelete(); // utilites // the find function that was missing in the AVLTrree class // the return values are defined in LivarotDefs.h int Find(NR::Point const &iPt, SweepTree *newOne, SweepTree *&insertL, SweepTree *&insertR, bool sweepSens = true); int Find(NR::Point const &iPt, SweepTree *&insertL, SweepTree *&insertR); /// Remove sweepevents attached to this node. void RemoveEvents(SweepEventQueue &queue); void RemoveEvent(SweepEventQueue &queue, Side s); // overrides of the AVLTree functions, to account for the sorting in the tree // and some other stuff int Remove(SweepTreeList &list, SweepEventQueue &queue, bool rebalance = true); int Insert(SweepTreeList &list, SweepEventQueue &queue, Shape *iDst, int iAtPoint, bool rebalance = true, bool sweepSens = true); int InsertAt(SweepTreeList &list, SweepEventQueue &queue, Shape *iDst, SweepTree *insNode, int fromPt, bool rebalance = true, bool sweepSens = true); /// Swap nodes, or more exactly, swap the edges in them. void SwapWithRight(SweepTreeList &list, SweepEventQueue &queue); void Avance(Shape *dst, int nPt, Shape *a, Shape *b); void Relocate(SweepTree *to); }; #endif /* !INKSCAPE_LIVAROT_SWEEP_TREE_H */ /* Local Variables: mode:c++ c-file-style:"stroustrup" c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) indent-tabs-mode:nil fill-column:99 End: */ // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :