diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 18:24:48 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 18:24:48 +0000 |
commit | cca66b9ec4e494c1d919bff0f71a820d8afab1fa (patch) | |
tree | 146f39ded1c938019e1ed42d30923c2ac9e86789 /src/livarot/sweep-tree.cpp | |
parent | Initial commit. (diff) | |
download | inkscape-upstream.tar.xz inkscape-upstream.zip |
Adding upstream version 1.2.2.upstream/1.2.2upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
-rw-r--r-- | src/livarot/sweep-tree.cpp | 567 |
1 files changed, 567 insertions, 0 deletions
diff --git a/src/livarot/sweep-tree.cpp b/src/livarot/sweep-tree.cpp new file mode 100644 index 0000000..dc350c4 --- /dev/null +++ b/src/livarot/sweep-tree.cpp @@ -0,0 +1,567 @@ +// 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. + */ +#include "livarot/sweep-event-queue.h" +#include "livarot/sweep-tree-list.h" +#include "livarot/sweep-tree.h" +#include "livarot/sweep-event.h" +#include "livarot/Shape.h" + + +/* + * the AVL tree holding the edges intersecting the sweepline + * that structure is very sensitive to anything + * you have edges stored in nodes, the nodes are sorted in increasing x-order of intersection + * with the sweepline, you have the 2 potential intersections of the edge in the node with its + * neighbours, plus the fact that it's stored in an array that's realloc'd + */ + +SweepTree::SweepTree() +{ + src = nullptr; + bord = -1; + startPoint = -1; + evt[LEFT] = evt[RIGHT] = nullptr; + sens = true; + //invDirLength=1; +} + +SweepTree::~SweepTree() +{ + MakeDelete(); +} + +void +SweepTree::MakeNew(Shape *iSrc, int iBord, int iWeight, int iStartPoint) +{ + AVLTree::MakeNew(); + ConvertTo(iSrc, iBord, iWeight, iStartPoint); +} + +void +SweepTree::ConvertTo(Shape *iSrc, int iBord, int iWeight, int iStartPoint) +{ + src = iSrc; + bord = iBord; + evt[LEFT] = evt[RIGHT] = nullptr; + startPoint = iStartPoint; + if (src->getEdge(bord).st < src->getEdge(bord).en) { + if (iWeight >= 0) + sens = true; + else + sens = false; + } else { + if (iWeight >= 0) + sens = false; + else + sens = true; + } + //invDirLength=src->eData[bord].isqlength; + //invDirLength=1/sqrt(src->getEdge(bord).dx*src->getEdge(bord).dx+src->getEdge(bord).dy*src->getEdge(bord).dy); +} + + +void SweepTree::MakeDelete() +{ + for (int i = 0; i < 2; i++) { + if (evt[i]) { + evt[i]->sweep[1 - i] = nullptr; + } + evt[i] = nullptr; + } + + AVLTree::MakeDelete(); +} + + +// find the position at which node "newOne" should be inserted in the subtree rooted here +// we want to order with respect to the order of intersections with the sweepline, currently +// lying at y=px[1]. +// px is the upper endpoint of newOne +int +SweepTree::Find(Geom::Point const &px, SweepTree *newOne, SweepTree *&insertL, + SweepTree *&insertR, bool sweepSens) +{ + // get the edge associated with this node: one point+one direction + // since we're dealing with line, the direction (bNorm) is taken downwards + Geom::Point bOrig, bNorm; + bOrig = src->pData[src->getEdge(bord).st].rx; + bNorm = src->eData[bord].rdx; + if (src->getEdge(bord).st > src->getEdge(bord).en) { + bNorm = -bNorm; + } + // rotate to get the normal to the edge + bNorm=bNorm.ccw(); + + Geom::Point diff; + diff = px - bOrig; + + // compute (px-orig)^dir to know on which side of this edge the point px lies + double y = 0; + //if ( startPoint == newOne->startPoint ) { + // y=0; + //} else { + y = dot(bNorm, diff); + //} + //y*=invDirLength; + if (fabs(y) < 0.000001) { + // that damn point px lies on me, so i need to consider to direction of the edge in + // newOne to know if it goes toward my left side or my right side + // sweepSens is needed (actually only used by the Scan() functions) because if the sweepline goes upward, + // signs change + // prendre en compte les directions + Geom::Point nNorm; + nNorm = newOne->src->eData[newOne->bord].rdx; + if (newOne->src->getEdge(newOne->bord).st > + newOne->src->getEdge(newOne->bord).en) + { + nNorm = -nNorm; + } + nNorm=nNorm.ccw(); + + if (sweepSens) { + y = cross(bNorm, nNorm); + } else { + y = cross(nNorm, bNorm); + } + if (y == 0) { + y = dot(bNorm, nNorm); + if (y == 0) { + insertL = this; + insertR = static_cast<SweepTree *>(elem[RIGHT]); + return found_exact; + } + } + } + if (y < 0) { + if (child[LEFT]) { + return (static_cast<SweepTree *>(child[LEFT]))->Find(px, newOne, + insertL, insertR, + sweepSens); + } else { + insertR = this; + insertL = static_cast<SweepTree *>(elem[LEFT]); + if (insertL) { + return found_between; + } else { + return found_on_left; + } + } + } else { + if (child[RIGHT]) { + return (static_cast<SweepTree *>(child[RIGHT]))->Find(px, newOne, + insertL, insertR, + sweepSens); + } else { + insertL = this; + insertR = static_cast<SweepTree *>(elem[RIGHT]); + if (insertR) { + return found_between; + } else { + return found_on_right; + } + } + } + return not_found; +} + +// only find a point's position +int +SweepTree::Find(Geom::Point const &px, SweepTree * &insertL, + SweepTree * &insertR) +{ + Geom::Point bOrig, bNorm; + bOrig = src->pData[src->getEdge(bord).st].rx; + bNorm = src->eData[bord].rdx; + if (src->getEdge(bord).st > src->getEdge(bord).en) + { + bNorm = -bNorm; + } + bNorm=bNorm.ccw(); + + Geom::Point diff; + diff = px - bOrig; + + double y = 0; + y = dot(bNorm, diff); + if (y == 0) + { + insertL = this; + insertR = static_cast<SweepTree *>(elem[RIGHT]); + return found_exact; + } + if (y < 0) + { + if (child[LEFT]) + { + return (static_cast<SweepTree *>(child[LEFT]))->Find(px, insertL, + insertR); + } + else + { + insertR = this; + insertL = static_cast<SweepTree *>(elem[LEFT]); + if (insertL) + { + return found_between; + } + else + { + return found_on_left; + } + } + } + else + { + if (child[RIGHT]) + { + return (static_cast<SweepTree *>(child[RIGHT]))->Find(px, insertL, + insertR); + } + else + { + insertL = this; + insertR = static_cast<SweepTree *>(elem[RIGHT]); + if (insertR) + { + return found_between; + } + else + { + return found_on_right; + } + } + } + return not_found; +} + +void +SweepTree::RemoveEvents(SweepEventQueue & queue) +{ + RemoveEvent(queue, LEFT); + RemoveEvent(queue, RIGHT); +} + +void SweepTree::RemoveEvent(SweepEventQueue &queue, Side s) +{ + if (evt[s]) { + queue.remove(evt[s]); + evt[s] = nullptr; + } +} + +int +SweepTree::Remove(SweepTreeList &list, SweepEventQueue &queue, + bool rebalance) +{ + RemoveEvents(queue); + AVLTree *tempR = static_cast<AVLTree *>(list.racine); + int err = AVLTree::Remove(tempR, rebalance); + list.racine = static_cast<SweepTree *>(tempR); + MakeDelete(); + if (list.nbTree <= 1) + { + list.nbTree = 0; + list.racine = nullptr; + } + else + { + if (list.racine == list.trees + (list.nbTree - 1)) + list.racine = this; + list.trees[--list.nbTree].Relocate(this); + } + return err; +} + +int +SweepTree::Insert(SweepTreeList &list, SweepEventQueue &queue, + Shape *iDst, int iAtPoint, bool rebalance, bool sweepSens) +{ + if (list.racine == nullptr) + { + list.racine = this; + return avl_no_err; + } + SweepTree *insertL = nullptr; + SweepTree *insertR = nullptr; + int insertion = + list.racine->Find(iDst->getPoint(iAtPoint).x, this, + insertL, insertR, sweepSens); + + if (insertion == found_exact) { + if (insertR) { + insertR->RemoveEvent(queue, LEFT); + } + if (insertL) { + insertL->RemoveEvent(queue, RIGHT); + } + + } else if (insertion == found_between) { + insertR->RemoveEvent(queue, LEFT); + insertL->RemoveEvent(queue, RIGHT); + } + + AVLTree *tempR = static_cast<AVLTree *>(list.racine); + int err = + AVLTree::Insert(tempR, insertion, static_cast<AVLTree *>(insertL), + static_cast<AVLTree *>(insertR), rebalance); + list.racine = static_cast<SweepTree *>(tempR); + return err; +} + +// insertAt() is a speedup on the regular sweepline: if the polygon contains a point of high degree, you +// get a set of edge that are to be added in the same position. thus you insert one edge with a regular insert(), +// and then insert all the other in a doubly-linked list fashion. this avoids the Find() call, but is O(d^2) worst-case +// where d is the number of edge to add in this fashion. hopefully d remains small + +int +SweepTree::InsertAt(SweepTreeList &list, SweepEventQueue &queue, + Shape */*iDst*/, SweepTree *insNode, int fromPt, + bool rebalance, bool sweepSens) +{ + if (list.racine == nullptr) + { + list.racine = this; + return avl_no_err; + } + + Geom::Point fromP; + fromP = src->pData[fromPt].rx; + Geom::Point nNorm; + nNorm = src->getEdge(bord).dx; + if (src->getEdge(bord).st > src->getEdge(bord).en) + { + nNorm = -nNorm; + } + if (sweepSens == false) + { + nNorm = -nNorm; + } + + Geom::Point bNorm; + bNorm = insNode->src->getEdge(insNode->bord).dx; + if (insNode->src->getEdge(insNode->bord).st > + insNode->src->getEdge(insNode->bord).en) + { + bNorm = -bNorm; + } + + SweepTree *insertL = nullptr; + SweepTree *insertR = nullptr; + double ang = cross(bNorm, nNorm); + if (ang == 0) + { + insertL = insNode; + insertR = static_cast<SweepTree *>(insNode->elem[RIGHT]); + } + else if (ang > 0) + { + insertL = insNode; + insertR = static_cast<SweepTree *>(insNode->elem[RIGHT]); + + while (insertL) + { + if (insertL->src == src) + { + if (insertL->src->getEdge(insertL->bord).st != fromPt + && insertL->src->getEdge(insertL->bord).en != fromPt) + { + break; + } + } + else + { + int ils = insertL->src->getEdge(insertL->bord).st; + int ile = insertL->src->getEdge(insertL->bord).en; + if ((insertL->src->pData[ils].rx[0] != fromP[0] + || insertL->src->pData[ils].rx[1] != fromP[1]) + && (insertL->src->pData[ile].rx[0] != fromP[0] + || insertL->src->pData[ile].rx[1] != fromP[1])) + { + break; + } + } + bNorm = insertL->src->getEdge(insertL->bord).dx; + if (insertL->src->getEdge(insertL->bord).st > + insertL->src->getEdge(insertL->bord).en) + { + bNorm = -bNorm; + } + ang = cross(bNorm, nNorm); + if (ang <= 0) + { + break; + } + insertR = insertL; + insertL = static_cast<SweepTree *>(insertR->elem[LEFT]); + } + } + else if (ang < 0) + { + insertL = insNode; + insertR = static_cast<SweepTree *>(insNode->elem[RIGHT]); + + while (insertR) + { + if (insertR->src == src) + { + if (insertR->src->getEdge(insertR->bord).st != fromPt + && insertR->src->getEdge(insertR->bord).en != fromPt) + { + break; + } + } + else + { + int ils = insertR->src->getEdge(insertR->bord).st; + int ile = insertR->src->getEdge(insertR->bord).en; + if ((insertR->src->pData[ils].rx[0] != fromP[0] + || insertR->src->pData[ils].rx[1] != fromP[1]) + && (insertR->src->pData[ile].rx[0] != fromP[0] + || insertR->src->pData[ile].rx[1] != fromP[1])) + { + break; + } + } + bNorm = insertR->src->getEdge(insertR->bord).dx; + if (insertR->src->getEdge(insertR->bord).st > + insertR->src->getEdge(insertR->bord).en) + { + bNorm = -bNorm; + } + ang = cross(bNorm, nNorm); + if (ang > 0) + { + break; + } + insertL = insertR; + insertR = static_cast<SweepTree *>(insertL->elem[RIGHT]); + } + } + + int insertion = found_between; + + if (insertL == nullptr) { + insertion = found_on_left; + } + if (insertR == nullptr) { + insertion = found_on_right; + } + + if (insertion == found_exact) { + /* FIXME: surely this can never be called? */ + if (insertR) { + insertR->RemoveEvent(queue, LEFT); + } + if (insertL) { + insertL->RemoveEvent(queue, RIGHT); + } + } else if (insertion == found_between) { + insertR->RemoveEvent(queue, LEFT); + insertL->RemoveEvent(queue, RIGHT); + } + + AVLTree *tempR = static_cast<AVLTree *>(list.racine); + int err = + AVLTree::Insert(tempR, insertion, static_cast<AVLTree *>(insertL), + static_cast<AVLTree *>(insertR), rebalance); + list.racine = static_cast<SweepTree *>(tempR); + return err; +} + +void +SweepTree::Relocate(SweepTree * to) +{ + if (this == to) + return; + AVLTree::Relocate(to); + to->src = src; + to->bord = bord; + to->sens = sens; + to->evt[LEFT] = evt[LEFT]; + to->evt[RIGHT] = evt[RIGHT]; + to->startPoint = startPoint; + if (unsigned(bord) < src->swsData.size()) + src->swsData[bord].misc = to; + if (unsigned(bord) < src->swrData.size()) + src->swrData[bord].misc = to; + if (evt[LEFT]) + evt[LEFT]->sweep[RIGHT] = to; + if (evt[RIGHT]) + evt[RIGHT]->sweep[LEFT] = to; +} + +// TODO check if ignoring these parameters is bad +void +SweepTree::SwapWithRight(SweepTreeList &/*list*/, SweepEventQueue &/*queue*/) +{ + SweepTree *tL = this; + SweepTree *tR = static_cast<SweepTree *>(elem[RIGHT]); + + tL->src->swsData[tL->bord].misc = tR; + tR->src->swsData[tR->bord].misc = tL; + + { + Shape *swap = tL->src; + tL->src = tR->src; + tR->src = swap; + } + { + int swap = tL->bord; + tL->bord = tR->bord; + tR->bord = swap; + } + { + int swap = tL->startPoint; + tL->startPoint = tR->startPoint; + tR->startPoint = swap; + } + //{double swap=tL->invDirLength;tL->invDirLength=tR->invDirLength;tR->invDirLength=swap;} + { + bool swap = tL->sens; + tL->sens = tR->sens; + tR->sens = swap; + } +} + +void +SweepTree::Avance(Shape */*dstPts*/, int /*curPoint*/, Shape */*a*/, Shape */*b*/) +{ + return; +/* if ( curPoint != startPoint ) { + int nb=-1; + if ( sens ) { +// nb=dstPts->AddEdge(startPoint,curPoint); + } else { +// nb=dstPts->AddEdge(curPoint,startPoint); + } + if ( nb >= 0 ) { + dstPts->swsData[nb].misc=(void*)((src==b)?1:0); + int wp=waitingPoint; + dstPts->eData[nb].firstLinkedPoint=waitingPoint; + waitingPoint=-1; + while ( wp >= 0 ) { + dstPts->pData[wp].edgeOnLeft=nb; + wp=dstPts->pData[wp].nextLinkedPoint; + } + } + startPoint=curPoint; + }*/ +} + +/* + 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 : |