summaryrefslogtreecommitdiffstats
path: root/src/livarot/sweep-tree.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/livarot/sweep-tree.h91
1 files changed, 91 insertions, 0 deletions
diff --git a/src/livarot/sweep-tree.h b/src/livarot/sweep-tree.h
new file mode 100644
index 0000000..13e1f76
--- /dev/null
+++ b/src/livarot/sweep-tree.h
@@ -0,0 +1,91 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/** @file
+ * TODO: insert short description here
+ *//*
+ * Authors: see git history
+ *
+ * Copyright (C) 2018 Authors
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#ifndef INKSCAPE_LIVAROT_SWEEP_TREE_H
+#define INKSCAPE_LIVAROT_SWEEP_TREE_H
+
+#include "livarot/AVL.h"
+#include <2geom/point.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.
+ */
+class SweepTree:public AVLTree
+{
+public:
+ SweepEvent *evt[2]; ///< Intersection with the edge on the left and right (if any).
+
+ Shape *src; /**< Shape from which the edge comes. (When doing boolean operation on polygons,
+ * edges can come from 2 different polygons.)
+ */
+ int bord; ///< Edge index in the Shape.
+ bool sens; ///< true= top->bottom; false= bottom->top.
+ int startPoint; ///< point index in the result Shape associated with the upper end of the edge
+
+ SweepTree();
+ ~SweepTree() override;
+
+ // 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(Geom::Point const &iPt, SweepTree *newOne, SweepTree *&insertL,
+ SweepTree *&insertR, bool sweepSens = true);
+ int Find(Geom::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:fileencoding=utf-8:textwidth=99 :