1 #ifndef INKSCAPE_LIVAROT_SWEEP_TREE_H
2 #define INKSCAPE_LIVAROT_SWEEP_TREE_H
4 #include "libnr/nr-point.h"
5 #include "livarot/AVL.h"
7 class Shape;
8 class SweepEvent;
9 class SweepEventQueue;
10 class SweepTreeList;
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).
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
29 SweepTree();
30 ~SweepTree();
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);
38 // Delete the contents of node.
39 void MakeDelete();
41 // utilites
43 // the find function that was missing in the AVLTrree class
44 // the return values are defined in LivarotDefs.h
45 int Find(NR::Point const &iPt, SweepTree *newOne, SweepTree *&insertL,
46 SweepTree *&insertR, bool sweepSens = true);
47 int Find(NR::Point const &iPt, SweepTree *&insertL, SweepTree *&insertR);
49 /// Remove sweepevents attached to this node.
50 void RemoveEvents(SweepEventQueue &queue);
52 void RemoveEvent(SweepEventQueue &queue, Side s);
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);
62 /// Swap nodes, or more exactly, swap the edges in them.
63 void SwapWithRight(SweepTreeList &list, SweepEventQueue &queue);
65 void Avance(Shape *dst, int nPt, Shape *a, Shape *b);
67 void Relocate(SweepTree *to);
68 };
71 #endif /* !INKSCAPE_LIVAROT_SWEEP_TREE_H */
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:encoding=utf-8:textwidth=99 :