Adding upstream version 1.2.2.upstream/1.2.2upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

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 :