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"
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.
17
class SweepTree:public AVLTree
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.)
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
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.
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);
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);
71
#endif /* !INKSCAPE_LIVAROT_SWEEP_TREE_H */
76
c-file-style:"stroustrup"
77
c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
82
// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :