Adding upstream version 1.2.2.upstream/1.2.2upstream

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

1 files changed, 3317 insertions, 0 deletions

diff --git a/src/livarot/ShapeSweep.cpp b/src/livarot/ShapeSweep.cpp
new file mode 100644
index 0000000..9b5d276
--- /dev/null
+++ b/src/livarot/ShapeSweep.cpp
@@ -0,0 +1,3317 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/** @file
+ * TODO: insert short description here
+ *//*
+ * Authors:
+ * see git history
+ * Fred
+ *
+ * Copyright (C) 2018 Authors
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+
+#include <cstdio>
+#include <cstdlib>
+#include <cstring>
+#include <glib.h>
+#include <2geom/affine.h>
+#include "Shape.h"
+#include "livarot/sweep-event-queue.h"
+#include "livarot/sweep-tree-list.h"
+#include "livarot/sweep-tree.h"
+
+//int   doDebug=0;
+
+/*
+ * El Intersector.
+ * algorithm: 1) benley ottman to get intersections of all the polygon's edges
+ *            2) rounding of the points of the polygon, Hooby's algorithm
+ *            3) DFS with clockwise choice of the edge to compute the windings
+ *            4) choose edges according to winding numbers and fill rule
+ * some additional nastyness: step 2 needs a seed winding number for the upper-left point of each 
+ * connex subgraph of the graph. computing these brutally is O(n^3): baaaad. so during the sweeping in 1)
+ * we keep for each point the edge of the resulting graph (not the original) that lies just on its left; 
+ * when the time comes for the point to get its winding number computed, that edge must have been treated,
+ * because its upper end lies above the aforementioned point, meaning we know the winding number of the point.
+ * only, there is a catch: since we're sweeping the polygon, the edge we want to link the point to has not yet been
+ * added (that would be too easy...). so the points are put on a linked list on the original shape's edge, and the list
+ * is flushed when the edge is added.
+ * rounding: to do the rounding, we need to find which edges cross the surrounding of the rounded points (at 
+ * each sweepline position). grunt method tries all combination of "rounded points in the sweepline"x"edges crossing 
+ * the sweepline". That's bad (and that's what polyboolean does, if i am not mistaken). so for each point 
+ * rounded in a given sweepline, keep immediate left and right edges at the time the point is treated.
+ * when edges/points crossing are searched, walk the edge list (in the  sweepline at the end of the batch) starting 
+ * from the rounded points' left and right from that time. may sound strange, but it works because edges that
+ * end or start in the batch have at least one end in the batch.
+ * all these are the cause of the numerous linked lists of points and edges maintained in the sweeping
+ */
+
+void
+Shape::ResetSweep ()
+{
+  MakePointData (true);
+  MakeEdgeData (true);
+  MakeSweepSrcData (true);
+}
+
+void
+Shape::CleanupSweep ()
+{
+  MakePointData (false);
+  MakeEdgeData (false);
+  MakeSweepSrcData (false);
+}
+
+void
+Shape::ForceToPolygon ()
+{
+  type = shape_polygon;
+}
+
+int
+Shape::Reoriente (Shape * a)
+{
+  Reset (0, 0);
+  if (a->numberOfPoints() <= 1 || a->numberOfEdges() <= 1)
+    return 0;
+  if (directedEulerian(a) == false)
+    return shape_input_err;
+
+  _pts = a->_pts;
+  if (numberOfPoints() > maxPt)
+    {
+      maxPt = numberOfPoints();
+      if (_has_points_data) {
+        pData.resize(maxPt);
+        _point_data_initialised = false;
+        _bbox_up_to_date = false;
+        }
+    }
+
+  _aretes = a->_aretes;
+  if (numberOfEdges() > maxAr)
+    {
+      maxAr = numberOfEdges();
+      if (_has_edges_data)
+	eData.resize(maxAr);
+      if (_has_sweep_src_data)
+	swsData.resize(maxAr);
+      if (_has_sweep_dest_data)
+	swdData.resize(maxAr);
+      if (_has_raster_data)
+	swrData.resize(maxAr);
+    }
+
+  MakePointData (true);
+  MakeEdgeData (true);
+  MakeSweepDestData (true);
+
+  initialisePointData();
+
+  for (int i = 0; i < numberOfPoints(); i++) {
+      _pts[i].x = pData[i].rx;
+      _pts[i].oldDegree = getPoint(i).totalDegree();
+  }
+  
+  for (int i = 0; i < a->numberOfEdges(); i++)
+    {
+      eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
+      eData[i].weight = 1;
+      _aretes[i].dx = eData[i].rdx;
+    }
+
+  SortPointsRounded ();
+
+  _need_edges_sorting = true;
+  GetWindings (this, nullptr, bool_op_union, true);
+
+//      Plot(341,56,8,400,400,true,true,false,true);
+  for (int i = 0; i < numberOfEdges(); i++)
+    {
+      swdData[i].leW %= 2;
+      swdData[i].riW %= 2;
+      if (swdData[i].leW < 0)
+	swdData[i].leW = -swdData[i].leW;
+      if (swdData[i].riW < 0)
+	swdData[i].riW = -swdData[i].riW;
+      if (swdData[i].leW > 0 && swdData[i].riW <= 0)
+	{
+	  eData[i].weight = 1;
+	}
+      else if (swdData[i].leW <= 0 && swdData[i].riW > 0)
+	{
+	  Inverse (i);
+	  eData[i].weight = 1;
+	}
+      else
+	{
+	  eData[i].weight = 0;
+	  SubEdge (i);
+	  i--;
+	}
+    }
+
+  MakePointData (false);
+  MakeEdgeData (false);
+  MakeSweepDestData (false);
+
+  if (directedEulerian(this) == false)
+    {
+//              printf( "pas euclidian2");
+      _pts.clear();
+      _aretes.clear();
+      return shape_euler_err;
+    }
+
+  type = shape_polygon;
+  return 0;
+}
+
+int
+Shape::ConvertToShape (Shape * a, FillRule directed, bool invert)
+{
+    Reset (0, 0);
+
+    if (a->numberOfPoints() <= 1 || a->numberOfEdges() <= 1) {
+	return 0;
+    }
+    
+    if ( directed != fill_justDont && directedEulerian(a) == false ) {
+  			g_warning ("Shape error in ConvertToShape: directedEulerian(a) == false\n");
+				return shape_input_err;
+    }
+  
+    a->ResetSweep();
+
+    if (sTree == nullptr) {
+	sTree = new SweepTreeList(a->numberOfEdges());
+    }
+    if (sEvts == nullptr) {
+	sEvts = new SweepEventQueue(a->numberOfEdges());
+    }
+  
+    MakePointData(true);
+    MakeEdgeData(true);
+    MakeSweepSrcData(true);
+    MakeSweepDestData(true);
+    MakeBackData(a->_has_back_data);
+
+    a->initialisePointData();
+    a->initialiseEdgeData();
+
+    a->SortPointsRounded();
+
+    chgts.clear();
+
+    double lastChange = a->pData[0].rx[1] - 1.0;
+    int lastChgtPt = 0;
+    int edgeHead = -1;
+    Shape *shapeHead = nullptr;
+
+    clearIncidenceData();
+    
+    int curAPt = 0;
+
+    while (curAPt < a->numberOfPoints() || sEvts->size() > 0) {
+	Geom::Point ptX;
+      double ptL, ptR;
+      SweepTree *intersL = nullptr;
+      SweepTree *intersR = nullptr;
+      int nPt = -1;
+      Shape *ptSh = nullptr;
+      bool isIntersection = false;
+      if (sEvts->peek(intersL, intersR, ptX, ptL, ptR))
+	{
+	  if (a->pData[curAPt].pending > 0
+	      || (a->pData[curAPt].rx[1] > ptX[1]
+		  || (a->pData[curAPt].rx[1] == ptX[1]
+		      && a->pData[curAPt].rx[0] > ptX[0])))
+	    {
+	      /* FIXME: could just be pop? */
+	      sEvts->extract(intersL, intersR, ptX, ptL, ptR);
+	      isIntersection = true;
+	    }
+	  else
+	    {
+	      nPt = curAPt++;
+	      ptSh = a;
+	      ptX = ptSh->pData[nPt].rx;
+	      isIntersection = false;
+	    }
+	}
+      else
+	{
+	  nPt = curAPt++;
+	  ptSh = a;
+	  ptX = ptSh->pData[nPt].rx;
+	  isIntersection = false;
+	}
+
+      if (isIntersection == false)
+	{
+	  if (ptSh->getPoint(nPt).dI == 0 && ptSh->getPoint(nPt).dO == 0)
+	    continue;
+	}
+
+      Geom::Point rPtX;
+      rPtX[0]= Round (ptX[0]);
+      rPtX[1]= Round (ptX[1]);
+      int lastPointNo = AddPoint (rPtX);
+      pData[lastPointNo].rx = rPtX;
+
+      if (rPtX[1] > lastChange)
+	{
+	  int lastI = AssemblePoints (lastChgtPt, lastPointNo);
+
+	  Shape *curSh = shapeHead;
+	  int curBo = edgeHead;
+	  while (curSh)
+	    {
+	      curSh->swsData[curBo].leftRnd =
+		pData[curSh->swsData[curBo].leftRnd].newInd;
+	      curSh->swsData[curBo].rightRnd =
+		pData[curSh->swsData[curBo].rightRnd].newInd;
+
+	      Shape *neSh = curSh->swsData[curBo].nextSh;
+	      curBo = curSh->swsData[curBo].nextBo;
+	      curSh = neSh;
+	    }
+
+	  for (auto & chgt : chgts)
+	    {
+	      chgt.ptNo = pData[chgt.ptNo].newInd;
+	      if (chgt.type == 0)
+		{
+		  if (chgt.src->getEdge(chgt.bord).st <
+		      chgt.src->getEdge(chgt.bord).en)
+		    {
+		      chgt.src->swsData[chgt.bord].stPt =
+			chgt.ptNo;
+		    }
+		  else
+		    {
+		      chgt.src->swsData[chgt.bord].enPt =
+			chgt.ptNo;
+		    }
+		}
+	      else if (chgt.type == 1)
+		{
+		  if (chgt.src->getEdge(chgt.bord).st >
+		      chgt.src->getEdge(chgt.bord).en)
+		    {
+		      chgt.src->swsData[chgt.bord].stPt =
+			chgt.ptNo;
+		    }
+		  else
+		    {
+		      chgt.src->swsData[chgt.bord].enPt =
+			chgt.ptNo;
+		    }
+		}
+	    }
+
+	  CheckAdjacencies (lastI, lastChgtPt, shapeHead, edgeHead);
+
+	  CheckEdges (lastI, lastChgtPt, a, nullptr, bool_op_union);
+
+	  for (int i = lastChgtPt; i < lastI; i++) {
+	    if (pData[i].askForWindingS) {
+		    Shape *windS = pData[i].askForWindingS;
+		    int windB = pData[i].askForWindingB;
+		    pData[i].nextLinkedPoint = windS->swsData[windB].firstLinkedPoint;
+		    windS->swsData[windB].firstLinkedPoint = i;
+		  }
+	   }
+
+    if (lastI < lastPointNo) {
+          _pts[lastI] = getPoint(lastPointNo);
+	   pData[lastI] = pData[lastPointNo];
+	  }
+	  lastPointNo = lastI;
+	  _pts.resize(lastI + 1);
+
+	  lastChgtPt = lastPointNo;
+	  lastChange = rPtX[1];
+	  chgts.clear();
+	  edgeHead = -1;
+	  shapeHead = nullptr;
+	}
+
+
+      if (isIntersection)
+	{
+//                      printf("(%i %i [%i %i]) ",intersL->bord,intersR->bord,intersL->startPoint,intersR->startPoint);
+	  intersL->RemoveEvent (*sEvts, LEFT);
+	  intersR->RemoveEvent (*sEvts, RIGHT);
+
+	  AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, INTERSECTION,
+		   intersL->src, intersL->bord, intersR->src, intersR->bord);
+
+	  intersL->SwapWithRight (*sTree, *sEvts);
+
+	  TesteIntersection (intersL, LEFT, false);
+	  TesteIntersection (intersR, RIGHT, false);
+	}
+      else
+	{
+	  int cb;
+
+	  int nbUp = 0, nbDn = 0;
+	  int upNo = -1, dnNo = -1;
+	  cb = ptSh->getPoint(nPt).incidentEdge[FIRST];
+	  while (cb >= 0 && cb < ptSh->numberOfEdges())
+	    {
+	      if ((ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
+		   && nPt == ptSh->getEdge(cb).en)
+		  || (ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
+		      && nPt == ptSh->getEdge(cb).st))
+		{
+		  upNo = cb;
+		  nbUp++;
+		}
+	      if ((ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
+		   && nPt == ptSh->getEdge(cb).en)
+		  || (ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
+		      && nPt == ptSh->getEdge(cb).st))
+		{
+		  dnNo = cb;
+		  nbDn++;
+		}
+	      cb = ptSh->NextAt (nPt, cb);
+	    }
+
+	  if (nbDn <= 0)
+	    {
+	      upNo = -1;
+	    }
+	  if (upNo >= 0 && (SweepTree *) ptSh->swsData[upNo].misc == nullptr)
+	    {
+	      upNo = -1;
+	    }
+
+	  bool doWinding = true;
+
+	  if (nbUp > 0)
+	    {
+	      cb = ptSh->getPoint(nPt).incidentEdge[FIRST];
+	      while (cb >= 0 && cb < ptSh->numberOfEdges())
+		{
+		  if ((ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
+		       && nPt == ptSh->getEdge(cb).en)
+		      || (ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
+			  && nPt == ptSh->getEdge(cb).st))
+		    {
+		      if (cb != upNo)
+			{
+			  SweepTree *node =
+			    (SweepTree *) ptSh->swsData[cb].misc;
+			  if (node == nullptr)
+			    {
+			    }
+			  else
+			    {
+			      AddChgt (lastPointNo, lastChgtPt, shapeHead,
+				       edgeHead, EDGE_REMOVED, node->src, node->bord,
+				       nullptr, -1);
+			      ptSh->swsData[cb].misc = nullptr;
+
+			      int onLeftB = -1, onRightB = -1;
+			      Shape *onLeftS = nullptr;
+			      Shape *onRightS = nullptr;
+			      if (node->elem[LEFT])
+				{
+				  onLeftB =
+				    (static_cast <
+				     SweepTree * >(node->elem[LEFT]))->bord;
+				  onLeftS =
+				    (static_cast <
+				     SweepTree * >(node->elem[LEFT]))->src;
+				}
+			      if (node->elem[RIGHT])
+				{
+				  onRightB =
+				    (static_cast <
+				     SweepTree * >(node->elem[RIGHT]))->bord;
+				  onRightS =
+				    (static_cast <
+				     SweepTree * >(node->elem[RIGHT]))->src;
+				}
+
+			      node->Remove (*sTree, *sEvts, true);
+			      if (onLeftS && onRightS)
+				{
+				  SweepTree *onLeft =
+				    (SweepTree *) onLeftS->swsData[onLeftB].
+				    misc;
+				  if (onLeftS == ptSh
+				      && (onLeftS->getEdge(onLeftB).en == nPt
+					  || onLeftS->getEdge(onLeftB).st ==
+					  nPt))
+				    {
+				    }
+				  else
+				    {
+				      if (onRightS == ptSh
+					  && (onRightS->getEdge(onRightB).en ==
+					      nPt
+					      || onRightS->getEdge(onRightB).
+					      st == nPt))
+					{
+					}
+				      else
+					{
+					  TesteIntersection (onLeft, RIGHT, false);
+					}
+				    }
+				}
+			    }
+			}
+		    }
+		  cb = ptSh->NextAt (nPt, cb);
+		}
+	    }
+
+	  // traitement du "upNo devient dnNo"
+	  SweepTree *insertionNode = nullptr;
+	  if (dnNo >= 0)
+	    {
+	      if (upNo >= 0)
+		{
+		  SweepTree *node = (SweepTree *) ptSh->swsData[upNo].misc;
+
+		  AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, EDGE_REMOVED,
+			   node->src, node->bord, nullptr, -1);
+
+		  ptSh->swsData[upNo].misc = nullptr;
+
+		  node->RemoveEvents (*sEvts);
+		  node->ConvertTo (ptSh, dnNo, 1, lastPointNo);
+		  ptSh->swsData[dnNo].misc = node;
+		  TesteIntersection (node, RIGHT, false);
+		  TesteIntersection (node, LEFT, false);
+		  insertionNode = node;
+
+		  ptSh->swsData[dnNo].curPoint = lastPointNo;
+		  AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, EDGE_INSERTED,
+			   node->src, node->bord, nullptr, -1);
+		}
+	      else
+		{
+		  SweepTree *node = sTree->add(ptSh, dnNo, 1, lastPointNo, this);
+		  ptSh->swsData[dnNo].misc = node;
+		  node->Insert (*sTree, *sEvts, this, lastPointNo, true);
+		  if (doWinding)
+		    {
+		      SweepTree *myLeft =
+			static_cast < SweepTree * >(node->elem[LEFT]);
+		      if (myLeft)
+			{
+			  pData[lastPointNo].askForWindingS = myLeft->src;
+			  pData[lastPointNo].askForWindingB = myLeft->bord;
+			}
+		      else
+			{
+			  pData[lastPointNo].askForWindingB = -1;
+			}
+		      doWinding = false;
+		    }
+		  TesteIntersection (node, RIGHT, false);
+		  TesteIntersection (node, LEFT, false);
+		  insertionNode = node;
+
+		  ptSh->swsData[dnNo].curPoint = lastPointNo;
+		  AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, EDGE_INSERTED,
+			   node->src, node->bord, nullptr, -1);
+		}
+	    }
+
+	  if (nbDn > 1)
+	    {			// si nbDn == 1 , alors dnNo a deja ete traite
+	      cb = ptSh->getPoint(nPt).incidentEdge[FIRST];
+	      while (cb >= 0 && cb < ptSh->numberOfEdges())
+		{
+		  if ((ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
+		       && nPt == ptSh->getEdge(cb).en)
+		      || (ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
+			  && nPt == ptSh->getEdge(cb).st))
+		    {
+		      if (cb != dnNo)
+			{
+			  SweepTree *node = sTree->add(ptSh, cb, 1, lastPointNo, this);
+			  ptSh->swsData[cb].misc = node;
+			  node->InsertAt (*sTree, *sEvts, this, insertionNode,
+					  nPt, true);
+			  if (doWinding)
+			    {
+			      SweepTree *myLeft =
+				static_cast < SweepTree * >(node->elem[LEFT]);
+			      if (myLeft)
+				{
+				  pData[lastPointNo].askForWindingS =
+				    myLeft->src;
+				  pData[lastPointNo].askForWindingB =
+				    myLeft->bord;
+				}
+			      else
+				{
+				  pData[lastPointNo].askForWindingB = -1;
+				}
+			      doWinding = false;
+			    }
+			  TesteIntersection (node, RIGHT, false);
+			  TesteIntersection (node, LEFT, false);
+
+			  ptSh->swsData[cb].curPoint = lastPointNo;
+			  AddChgt (lastPointNo, lastChgtPt, shapeHead,
+				   edgeHead, EDGE_INSERTED, node->src, node->bord, nullptr,
+				   -1);
+			}
+		    }
+		  cb = ptSh->NextAt (nPt, cb);
+		}
+	    }
+	}
+    }
+  {
+    int lastI = AssemblePoints (lastChgtPt, numberOfPoints());
+
+
+    Shape *curSh = shapeHead;
+    int curBo = edgeHead;
+    while (curSh)
+      {
+	curSh->swsData[curBo].leftRnd =
+	  pData[curSh->swsData[curBo].leftRnd].newInd;
+	curSh->swsData[curBo].rightRnd =
+	  pData[curSh->swsData[curBo].rightRnd].newInd;
+
+	Shape *neSh = curSh->swsData[curBo].nextSh;
+	curBo = curSh->swsData[curBo].nextBo;
+	curSh = neSh;
+      }
+
+    for (auto & chgt : chgts)
+      {
+	chgt.ptNo = pData[chgt.ptNo].newInd;
+	if (chgt.type == 0)
+	  {
+	    if (chgt.src->getEdge(chgt.bord).st <
+		chgt.src->getEdge(chgt.bord).en)
+	      {
+		chgt.src->swsData[chgt.bord].stPt = chgt.ptNo;
+	      }
+	    else
+	      {
+		chgt.src->swsData[chgt.bord].enPt = chgt.ptNo;
+	      }
+	  }
+	else if (chgt.type == 1)
+	  {
+	    if (chgt.src->getEdge(chgt.bord).st >
+		chgt.src->getEdge(chgt.bord).en)
+	      {
+		chgt.src->swsData[chgt.bord].stPt = chgt.ptNo;
+	      }
+	    else
+	      {
+		chgt.src->swsData[chgt.bord].enPt = chgt.ptNo;
+	      }
+	  }
+      }
+
+    CheckAdjacencies (lastI, lastChgtPt, shapeHead, edgeHead);
+
+    CheckEdges (lastI, lastChgtPt, a, nullptr, bool_op_union);
+
+    for (int i = lastChgtPt; i < lastI; i++)
+      {
+	if (pData[i].askForWindingS)
+	  {
+	    Shape *windS = pData[i].askForWindingS;
+	    int windB = pData[i].askForWindingB;
+	    pData[i].nextLinkedPoint = windS->swsData[windB].firstLinkedPoint;
+	    windS->swsData[windB].firstLinkedPoint = i;
+	  }
+      }
+
+    _pts.resize(lastI);
+
+    edgeHead = -1;
+    shapeHead = nullptr;
+  }
+
+    chgts.clear();
+
+//  Plot (98.0, 112.0, 8.0, 400.0, 400.0, true, true, true, true);
+//      Plot(200.0,200.0,2.0,400.0,400.0,true,true,true,true);
+
+  //      AssemblePoints(a);
+
+//      GetAdjacencies(a);
+
+//      MakeAretes(a);
+    clearIncidenceData();
+
+  AssembleAretes (directed);
+
+//  Plot (98.0, 112.0, 8.0, 400.0, 400.0, true, true, true, true);
+
+  for (int i = 0; i < numberOfPoints(); i++)
+    {
+      _pts[i].oldDegree = getPoint(i).totalDegree();
+    }
+//      Validate();
+
+  _need_edges_sorting = true;
+  if ( directed == fill_justDont ) {
+    SortEdges();
+  } else {
+    GetWindings (a);
+  }
+//  Plot (98.0, 112.0, 8.0, 400.0, 400.0, true, true, true, true);
+//   if ( doDebug ) {
+//   a->CalcBBox();
+//     a->Plot(a->leftX,a->topY,32.0,0.0,0.0,true,true,true,true,"orig.svg");
+//     Plot(a->leftX,a->topY,32.0,0.0,0.0,true,true,true,true,"winded.svg");
+//   }
+  if (directed == fill_positive)
+  {
+    if (invert)
+    {
+      for (int i = 0; i < numberOfEdges(); i++)
+	    {
+	      if (swdData[i].leW < 0 && swdData[i].riW >= 0)
+        {
+          eData[i].weight = 1;
+        }
+	      else if (swdData[i].leW >= 0 && swdData[i].riW < 0)
+        {
+          Inverse (i);
+          eData[i].weight = 1;
+        }
+	      else
+        {
+          eData[i].weight = 0;
+          SubEdge (i);
+          i--;
+        }
+	    }
+    }
+    else
+    {
+      for (int i = 0; i < numberOfEdges(); i++)
+	    {
+	      if (swdData[i].leW > 0 && swdData[i].riW <= 0)
+        {
+          eData[i].weight = 1;
+        }
+	      else if (swdData[i].leW <= 0 && swdData[i].riW > 0)
+        {
+          Inverse (i);
+          eData[i].weight = 1;
+        }
+	      else
+        {
+           eData[i].weight = 0;
+          SubEdge (i);
+          i--;
+        }
+	    }
+    }
+  }
+  else if (directed == fill_nonZero)
+  {
+    if (invert)
+    {
+      for (int i = 0; i < numberOfEdges(); i++)
+	    {
+	      if (swdData[i].leW < 0 && swdData[i].riW == 0)
+        {
+          eData[i].weight = 1;
+        }
+	      else if (swdData[i].leW > 0 && swdData[i].riW == 0)
+        {
+          eData[i].weight = 1;
+        }
+	      else if (swdData[i].leW == 0 && swdData[i].riW < 0)
+        {
+          Inverse (i);
+          eData[i].weight = 1;
+        }
+	      else if (swdData[i].leW == 0 && swdData[i].riW > 0)
+        {
+          Inverse (i);
+          eData[i].weight = 1;
+        }
+	      else
+        {
+          eData[i].weight = 0;
+          SubEdge (i);
+          i--;
+        }
+	    }
+    }
+    else
+    {
+      for (int i = 0; i < numberOfEdges(); i++)
+	    {
+	      if (swdData[i].leW > 0 && swdData[i].riW == 0)
+        {
+          eData[i].weight = 1;
+        }
+	      else if (swdData[i].leW < 0 && swdData[i].riW == 0)
+        {
+          eData[i].weight = 1;
+        }
+	      else if (swdData[i].leW == 0 && swdData[i].riW > 0)
+        {
+          Inverse (i);
+          eData[i].weight = 1;
+        }
+	      else if (swdData[i].leW == 0 && swdData[i].riW < 0)
+        {
+          Inverse (i);
+          eData[i].weight = 1;
+        }
+	      else
+        {
+          eData[i].weight = 0;
+          SubEdge (i);
+          i--;
+        }
+	    }
+    }
+  }
+  else if (directed == fill_oddEven)
+  {
+    for (int i = 0; i < numberOfEdges(); i++)
+    {
+      swdData[i].leW %= 2;
+      swdData[i].riW %= 2;
+      if (swdData[i].leW < 0)
+        swdData[i].leW = -swdData[i].leW;
+      if (swdData[i].riW < 0)
+        swdData[i].riW = -swdData[i].riW;
+      if (swdData[i].leW > 0 && swdData[i].riW <= 0)
+	    {
+	      eData[i].weight = 1;
+	    }
+      else if (swdData[i].leW <= 0 && swdData[i].riW > 0)
+	    {
+	      Inverse (i);
+	      eData[i].weight = 1;
+	    }
+      else
+	    {
+	      eData[i].weight = 0;
+	      SubEdge (i);
+	      i--;
+	    }
+    }
+  } else if ( directed == fill_justDont ) {
+    for (int i=0;i<numberOfEdges();i++) {
+      if ( getEdge(i).st < 0 || getEdge(i).en < 0 ) {
+        SubEdge(i);
+        i--;
+      } else {
+	      eData[i].weight = 0;
+      }
+    }
+  }
+  
+//      Plot(200.0,200.0,2.0,400.0,400.0,true,true,true,true);
+
+  delete sTree;
+  sTree = nullptr;
+  delete sEvts;
+  sEvts = nullptr;
+
+  MakePointData (false);
+  MakeEdgeData (false);
+  MakeSweepSrcData (false);
+  MakeSweepDestData (false);
+  a->CleanupSweep ();
+  type = shape_polygon;
+  return 0;
+}
+
+// technically it's just a ConvertToShape() on 2 polygons at the same time, and different rules
+// for choosing the edges according to their winding numbers.
+// probably one of the biggest function i ever wrote.
+int
+Shape::Booleen (Shape * a, Shape * b, BooleanOp mod,int cutPathID)
+{
+  if (a == b || a == nullptr || b == nullptr)
+    return shape_input_err;
+  Reset (0, 0);
+  if (a->numberOfPoints() <= 1 || a->numberOfEdges() <= 1)
+    return 0;
+  if (b->numberOfPoints() <= 1 || b->numberOfEdges() <= 1)
+    return 0;
+  if ( mod == bool_op_cut ) {
+  } else if ( mod == bool_op_slice ) {
+  } else {
+    if (a->type != shape_polygon)
+      return shape_input_err;
+    if (b->type != shape_polygon)
+      return shape_input_err;
+  }
+
+  a->ResetSweep ();
+  b->ResetSweep ();
+
+  if (sTree == nullptr) {
+      sTree = new SweepTreeList(a->numberOfEdges() + b->numberOfEdges());
+  }
+  if (sEvts == nullptr) {
+      sEvts = new SweepEventQueue(a->numberOfEdges() + b->numberOfEdges());
+  }
+  
+  MakePointData (true);
+  MakeEdgeData (true);
+  MakeSweepSrcData (true);
+  MakeSweepDestData (true);
+  if (a->hasBackData () && b->hasBackData ())
+    {
+      MakeBackData (true);
+    }
+  else
+    {
+      MakeBackData (false);
+    }
+
+  a->initialisePointData();
+  b->initialisePointData();
+
+  a->initialiseEdgeData();
+  b->initialiseEdgeData();
+
+  a->SortPointsRounded ();
+  b->SortPointsRounded ();
+
+  chgts.clear();
+
+  double lastChange =
+    (a->pData[0].rx[1] <
+     b->pData[0].rx[1]) ? a->pData[0].rx[1] - 1.0 : b->pData[0].rx[1] - 1.0;
+  int lastChgtPt = 0;
+  int edgeHead = -1;
+  Shape *shapeHead = nullptr;
+
+  clearIncidenceData();
+
+  int curAPt = 0;
+  int curBPt = 0;
+
+  while (curAPt < a->numberOfPoints() || curBPt < b->numberOfPoints() || sEvts->size() > 0)
+    {
+/*		for (int i=0;i<sEvts.nbEvt;i++) {
+			printf("%f %f %i %i\n",sEvts.events[i].posx,sEvts.events[i].posy,sEvts.events[i].leftSweep->bord,sEvts.events[i].rightSweep->bord); // localizing ok
+		}
+		//		cout << endl;
+		if ( sTree.racine ) {
+			SweepTree*  ct=static_cast <SweepTree*> (sTree.racine->Leftmost());
+			while ( ct ) {
+				printf("%i %i [%i\n",ct->bord,ct->startPoint,(ct->src==a)?1:0);
+				ct=static_cast <SweepTree*> (ct->elem[RIGHT]);
+			}
+		}
+		printf("\n");*/
+
+    Geom::Point ptX;
+      double ptL, ptR;
+      SweepTree *intersL = nullptr;
+      SweepTree *intersR = nullptr;
+      int nPt = -1;
+      Shape *ptSh = nullptr;
+      bool isIntersection = false;
+
+      if (sEvts->peek(intersL, intersR, ptX, ptL, ptR))
+	{
+	  if (curAPt < a->numberOfPoints())
+	    {
+	      if (curBPt < b->numberOfPoints())
+		{
+		  if (a->pData[curAPt].rx[1] < b->pData[curBPt].rx[1]
+		      || (a->pData[curAPt].rx[1] == b->pData[curBPt].rx[1]
+			  && a->pData[curAPt].rx[0] < b->pData[curBPt].rx[0]))
+		    {
+		      if (a->pData[curAPt].pending > 0
+			  || (a->pData[curAPt].rx[1] > ptX[1]
+			      || (a->pData[curAPt].rx[1] == ptX[1]
+				  && a->pData[curAPt].rx[0] > ptX[0])))
+			{
+			  /* FIXME: could be pop? */
+			  sEvts->extract(intersL, intersR, ptX, ptL, ptR);
+			  isIntersection = true;
+			}
+		      else
+			{
+			  nPt = curAPt++;
+			  ptSh = a;
+			  ptX = ptSh->pData[nPt].rx;
+			  isIntersection = false;
+			}
+		    }
+		  else
+		    {
+		      if (b->pData[curBPt].pending > 0
+			  || (b->pData[curBPt].rx[1] > ptX[1]
+			      || (b->pData[curBPt].rx[1] == ptX[1]
+				  && b->pData[curBPt].rx[0] > ptX[0])))
+			{
+			  /* FIXME: could be pop? */
+			  sEvts->extract(intersL, intersR, ptX, ptL, ptR);
+			  isIntersection = true;
+			}
+		      else
+			{
+			  nPt = curBPt++;
+			  ptSh = b;
+			  ptX = ptSh->pData[nPt].rx;
+			  isIntersection = false;
+			}
+		    }
+		}
+	      else
+		{
+		  if (a->pData[curAPt].pending > 0
+		      || (a->pData[curAPt].rx[1] > ptX[1]
+			  || (a->pData[curAPt].rx[1] == ptX[1]
+			      && a->pData[curAPt].rx[0] > ptX[0])))
+		    {
+		      /* FIXME: could be pop? */
+		      sEvts->extract(intersL, intersR, ptX, ptL, ptR);
+		      isIntersection = true;
+		    }
+		  else
+		    {
+		      nPt = curAPt++;
+		      ptSh = a;
+		      ptX = ptSh->pData[nPt].rx;
+		      isIntersection = false;
+		    }
+		}
+	    }
+	  else
+	    {
+	      if (b->pData[curBPt].pending > 0
+		  || (b->pData[curBPt].rx[1] > ptX[1]
+		      || (b->pData[curBPt].rx[1] == ptX[1]
+			  && b->pData[curBPt].rx[0] > ptX[0])))
+		{
+		  /* FIXME: could be pop? */
+		  sEvts->extract(intersL, intersR, ptX,  ptL, ptR);
+		  isIntersection = true;
+		}
+	      else
+		{
+		  nPt = curBPt++;
+		  ptSh = b;
+		  ptX = ptSh->pData[nPt].rx;
+		  isIntersection = false;
+		}
+	    }
+	}
+      else
+	{
+	  if (curAPt < a->numberOfPoints())
+	    {
+	      if (curBPt < b->numberOfPoints())
+		{
+		  if (a->pData[curAPt].rx[1] < b->pData[curBPt].rx[1]
+		      || (a->pData[curAPt].rx[1] == b->pData[curBPt].rx[1]
+			  && a->pData[curAPt].rx[0] < b->pData[curBPt].rx[0]))
+		    {
+		      nPt = curAPt++;
+		      ptSh = a;
+		    }
+		  else
+		    {
+		      nPt = curBPt++;
+		      ptSh = b;
+		    }
+		}
+	      else
+		{
+		  nPt = curAPt++;
+		  ptSh = a;
+		}
+	    }
+	  else
+	    {
+	      nPt = curBPt++;
+	      ptSh = b;
+	    }
+	  ptX = ptSh->pData[nPt].rx;
+	  isIntersection = false;
+	}
+
+      if (isIntersection == false)
+	{
+	  if (ptSh->getPoint(nPt).dI == 0 && ptSh->getPoint(nPt).dO == 0)
+	    continue;
+	}
+
+      Geom::Point rPtX;
+      rPtX[0]= Round (ptX[0]);
+      rPtX[1]= Round (ptX[1]);
+      int lastPointNo = AddPoint (rPtX);
+      pData[lastPointNo].rx = rPtX;
+
+      if (rPtX[1] > lastChange)
+	{
+	  int lastI = AssemblePoints (lastChgtPt, lastPointNo);
+
+
+	  Shape *curSh = shapeHead;
+	  int curBo = edgeHead;
+	  while (curSh)
+	    {
+	      curSh->swsData[curBo].leftRnd =
+		pData[curSh->swsData[curBo].leftRnd].newInd;
+	      curSh->swsData[curBo].rightRnd =
+		pData[curSh->swsData[curBo].rightRnd].newInd;
+
+	      Shape *neSh = curSh->swsData[curBo].nextSh;
+	      curBo = curSh->swsData[curBo].nextBo;
+	      curSh = neSh;
+	    }
+
+	  for (auto & chgt : chgts)
+	    {
+	      chgt.ptNo = pData[chgt.ptNo].newInd;
+	      if (chgt.type == 0)
+		{
+		  if (chgt.src->getEdge(chgt.bord).st <
+		      chgt.src->getEdge(chgt.bord).en)
+		    {
+		      chgt.src->swsData[chgt.bord].stPt =
+			chgt.ptNo;
+		    }
+		  else
+		    {
+		      chgt.src->swsData[chgt.bord].enPt =
+			chgt.ptNo;
+		    }
+		}
+	      else if (chgt.type == 1)
+		{
+		  if (chgt.src->getEdge(chgt.bord).st >
+		      chgt.src->getEdge(chgt.bord).en)
+		    {
+		      chgt.src->swsData[chgt.bord].stPt =
+			chgt.ptNo;
+		    }
+		  else
+		    {
+		      chgt.src->swsData[chgt.bord].enPt =
+			chgt.ptNo;
+		    }
+		}
+	    }
+
+	  CheckAdjacencies (lastI, lastChgtPt, shapeHead, edgeHead);
+
+	  CheckEdges (lastI, lastChgtPt, a, b, mod);
+
+	  for (int i = lastChgtPt; i < lastI; i++)
+	    {
+	      if (pData[i].askForWindingS)
+		{
+		  Shape *windS = pData[i].askForWindingS;
+		  int windB = pData[i].askForWindingB;
+		  pData[i].nextLinkedPoint =
+		    windS->swsData[windB].firstLinkedPoint;
+		  windS->swsData[windB].firstLinkedPoint = i;
+		}
+	    }
+
+    if (lastI < lastPointNo)
+	    {
+	      _pts[lastI] = getPoint(lastPointNo);
+	      pData[lastI] = pData[lastPointNo];
+	    }
+	  lastPointNo = lastI;
+	  _pts.resize(lastI + 1);
+
+	  lastChgtPt = lastPointNo;
+	  lastChange = rPtX[1];
+	  chgts.clear();
+	  edgeHead = -1;
+	  shapeHead = nullptr;
+	}
+
+
+      if (isIntersection)
+	{
+	  // les 2 events de part et d'autre de l'intersection
+	  // (celui de l'intersection a deja ete depile)
+	  intersL->RemoveEvent (*sEvts, LEFT);
+	  intersR->RemoveEvent (*sEvts, RIGHT);
+
+	  AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, INTERSECTION,
+		   intersL->src, intersL->bord, intersR->src, intersR->bord);
+
+	  intersL->SwapWithRight (*sTree, *sEvts);
+
+	  TesteIntersection (intersL, LEFT, true);
+	  TesteIntersection (intersR, RIGHT, true);
+	}
+      else
+	{
+	  int cb;
+
+	  int nbUp = 0, nbDn = 0;
+	  int upNo = -1, dnNo = -1;
+	  cb = ptSh->getPoint(nPt).incidentEdge[FIRST];
+	  while (cb >= 0 && cb < ptSh->numberOfEdges())
+	    {
+	      if ((ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
+		   && nPt == ptSh->getEdge(cb).en)
+		  || (ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
+		      && nPt == ptSh->getEdge(cb).st))
+		{
+		  upNo = cb;
+		  nbUp++;
+		}
+	      if ((ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
+		   && nPt == ptSh->getEdge(cb).en)
+		  || (ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
+		      && nPt == ptSh->getEdge(cb).st))
+		{
+		  dnNo = cb;
+		  nbDn++;
+		}
+	      cb = ptSh->NextAt (nPt, cb);
+	    }
+
+	  if (nbDn <= 0)
+	    {
+	      upNo = -1;
+	    }
+	  if (upNo >= 0 && (SweepTree *) ptSh->swsData[upNo].misc == nullptr)
+	    {
+	      upNo = -1;
+	    }
+
+//                      upNo=-1;
+
+	  bool doWinding = true;
+
+	  if (nbUp > 0)
+	    {
+	      cb = ptSh->getPoint(nPt).incidentEdge[FIRST];
+	      while (cb >= 0 && cb < ptSh->numberOfEdges())
+		{
+		  if ((ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
+		       && nPt == ptSh->getEdge(cb).en)
+		      || (ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
+			  && nPt == ptSh->getEdge(cb).st))
+		    {
+		      if (cb != upNo)
+			{
+			  SweepTree *node =
+			    (SweepTree *) ptSh->swsData[cb].misc;
+			  if (node == nullptr)
+			    {
+			    }
+			  else
+			    {
+			      AddChgt (lastPointNo, lastChgtPt, shapeHead,
+				       edgeHead, EDGE_REMOVED, node->src, node->bord,
+				       nullptr, -1);
+			      ptSh->swsData[cb].misc = nullptr;
+
+			      int onLeftB = -1, onRightB = -1;
+			      Shape *onLeftS = nullptr;
+			      Shape *onRightS = nullptr;
+			      if (node->elem[LEFT])
+				{
+				  onLeftB =
+				    (static_cast <
+				     SweepTree * >(node->elem[LEFT]))->bord;
+				  onLeftS =
+				    (static_cast <
+				     SweepTree * >(node->elem[LEFT]))->src;
+				}
+			      if (node->elem[RIGHT])
+				{
+				  onRightB =
+				    (static_cast <
+				     SweepTree * >(node->elem[RIGHT]))->bord;
+				  onRightS =
+				    (static_cast <
+				     SweepTree * >(node->elem[RIGHT]))->src;
+				}
+
+			      node->Remove (*sTree, *sEvts, true);
+			      if (onLeftS && onRightS)
+				{
+				  SweepTree *onLeft =
+				    (SweepTree *) onLeftS->swsData[onLeftB].
+				    misc;
+//                                                                      SweepTree* onRight=(SweepTree*)onRightS->swsData[onRightB].misc;
+				  if (onLeftS == ptSh
+				      && (onLeftS->getEdge(onLeftB).en == nPt
+					  || onLeftS->getEdge(onLeftB).st ==
+					  nPt))
+				    {
+				    }
+				  else
+				    {
+				      if (onRightS == ptSh
+					  && (onRightS->getEdge(onRightB).en ==
+					      nPt
+					      || onRightS->getEdge(onRightB).
+					      st == nPt))
+					{
+					}
+				      else
+					{
+					  TesteIntersection (onLeft, RIGHT, true);
+					}
+				    }
+				}
+			    }
+			}
+		    }
+		  cb = ptSh->NextAt (nPt, cb);
+		}
+	    }
+
+	  // traitement du "upNo devient dnNo"
+	  SweepTree *insertionNode = nullptr;
+	  if (dnNo >= 0)
+	    {
+	      if (upNo >= 0)
+		{
+		  SweepTree *node = (SweepTree *) ptSh->swsData[upNo].misc;
+
+		  AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, EDGE_REMOVED,
+			   node->src, node->bord, nullptr, -1);
+
+		  ptSh->swsData[upNo].misc = nullptr;
+
+		  node->RemoveEvents (*sEvts);
+		  node->ConvertTo (ptSh, dnNo, 1, lastPointNo);
+		  ptSh->swsData[dnNo].misc = node;
+		  TesteIntersection (node, RIGHT, true);
+		  TesteIntersection (node, LEFT, true);
+		  insertionNode = node;
+
+		  ptSh->swsData[dnNo].curPoint = lastPointNo;
+
+		  AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, EDGE_INSERTED,
+			   node->src, node->bord, nullptr, -1);
+		}
+	      else
+		{
+		  SweepTree *node = sTree->add(ptSh, dnNo, 1, lastPointNo, this);
+		  ptSh->swsData[dnNo].misc = node;
+		  node->Insert (*sTree, *sEvts, this, lastPointNo, true);
+
+		  if (doWinding)
+		    {
+		      SweepTree *myLeft =
+			static_cast < SweepTree * >(node->elem[LEFT]);
+		      if (myLeft)
+			{
+			  pData[lastPointNo].askForWindingS = myLeft->src;
+			  pData[lastPointNo].askForWindingB = myLeft->bord;
+			}
+		      else
+			{
+			  pData[lastPointNo].askForWindingB = -1;
+			}
+		      doWinding = false;
+		    }
+
+		  TesteIntersection (node, RIGHT, true);
+		  TesteIntersection (node, LEFT, true);
+		  insertionNode = node;
+
+		  ptSh->swsData[dnNo].curPoint = lastPointNo;
+
+		  AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, EDGE_INSERTED,
+			   node->src, node->bord, nullptr, -1);
+		}
+	    }
+
+	  if (nbDn > 1)
+	    {			// si nbDn == 1 , alors dnNo a deja ete traite
+	      cb = ptSh->getPoint(nPt).incidentEdge[FIRST];
+	      while (cb >= 0 && cb < ptSh->numberOfEdges())
+		{
+		  if ((ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
+		       && nPt == ptSh->getEdge(cb).en)
+		      || (ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
+			  && nPt == ptSh->getEdge(cb).st))
+		    {
+		      if (cb != dnNo)
+			{
+			  SweepTree *node = sTree->add(ptSh, cb, 1, lastPointNo, this);
+			  ptSh->swsData[cb].misc = node;
+//                                                      node->Insert(sTree,*sEvts,this,lastPointNo,true);
+			  node->InsertAt (*sTree, *sEvts, this, insertionNode,
+					  nPt, true);
+
+			  if (doWinding)
+			    {
+			      SweepTree *myLeft =
+				static_cast < SweepTree * >(node->elem[LEFT]);
+			      if (myLeft)
+				{
+				  pData[lastPointNo].askForWindingS =
+				    myLeft->src;
+				  pData[lastPointNo].askForWindingB =
+				    myLeft->bord;
+				}
+			      else
+				{
+				  pData[lastPointNo].askForWindingB = -1;
+				}
+			      doWinding = false;
+			    }
+
+			  TesteIntersection (node, RIGHT, true);
+			  TesteIntersection (node, LEFT, true);
+
+			  ptSh->swsData[cb].curPoint = lastPointNo;
+
+			  AddChgt (lastPointNo, lastChgtPt, shapeHead,
+				   edgeHead, EDGE_INSERTED, node->src, node->bord, nullptr,
+				   -1);
+			}
+		    }
+		  cb = ptSh->NextAt (nPt, cb);
+		}
+	    }
+	}
+    }
+  {
+    int lastI = AssemblePoints (lastChgtPt, numberOfPoints());
+
+
+    Shape *curSh = shapeHead;
+    int curBo = edgeHead;
+    while (curSh)
+      {
+	curSh->swsData[curBo].leftRnd =
+	  pData[curSh->swsData[curBo].leftRnd].newInd;
+	curSh->swsData[curBo].rightRnd =
+	  pData[curSh->swsData[curBo].rightRnd].newInd;
+
+	Shape *neSh = curSh->swsData[curBo].nextSh;
+	curBo = curSh->swsData[curBo].nextBo;
+	curSh = neSh;
+      }
+
+    /* FIXME: this kind of code seems to appear frequently */
+    for (auto & chgt : chgts)
+      {
+	chgt.ptNo = pData[chgt.ptNo].newInd;
+	if (chgt.type == 0)
+	  {
+	    if (chgt.src->getEdge(chgt.bord).st <
+		chgt.src->getEdge(chgt.bord).en)
+	      {
+		chgt.src->swsData[chgt.bord].stPt = chgt.ptNo;
+	      }
+	    else
+	      {
+		chgt.src->swsData[chgt.bord].enPt = chgt.ptNo;
+	      }
+	  }
+	else if (chgt.type == 1)
+	  {
+	    if (chgt.src->getEdge(chgt.bord).st >
+		chgt.src->getEdge(chgt.bord).en)
+	      {
+		chgt.src->swsData[chgt.bord].stPt = chgt.ptNo;
+	      }
+	    else
+	      {
+		chgt.src->swsData[chgt.bord].enPt = chgt.ptNo;
+	      }
+	  }
+      }
+
+    CheckAdjacencies (lastI, lastChgtPt, shapeHead, edgeHead);
+
+    CheckEdges (lastI, lastChgtPt, a, b, mod);
+
+    for (int i = lastChgtPt; i < lastI; i++)
+      {
+	if (pData[i].askForWindingS)
+	  {
+	    Shape *windS = pData[i].askForWindingS;
+	    int windB = pData[i].askForWindingB;
+	    pData[i].nextLinkedPoint = windS->swsData[windB].firstLinkedPoint;
+	    windS->swsData[windB].firstLinkedPoint = i;
+	  }
+      }
+
+    _pts.resize(lastI);
+
+    edgeHead = -1;
+    shapeHead = nullptr;
+  }
+
+  chgts.clear();
+  clearIncidenceData();
+
+//      Plot(190,70,6,400,400,true,false,true,true);
+
+  if ( mod == bool_op_cut ) {
+    AssembleAretes (fill_justDont);
+    // dupliquer les aretes de la coupure
+    int i=numberOfEdges()-1;
+    for (;i>=0;i--) {
+      if ( ebData[i].pathID == cutPathID ) {
+        // on duplique
+        int nEd=AddEdge(getEdge(i).en,getEdge(i).st);
+        ebData[nEd].pathID=cutPathID;
+        ebData[nEd].pieceID=ebData[i].pieceID;
+        ebData[nEd].tSt=ebData[i].tEn;
+        ebData[nEd].tEn=ebData[i].tSt;
+        eData[nEd].weight=eData[i].weight;
+        // lui donner les firstlinkedpoitn si besoin
+        if ( getEdge(i).en >= getEdge(i).st ) {
+          int cp = swsData[i].firstLinkedPoint;
+          while (cp >= 0) {
+            pData[cp].askForWindingB = nEd;
+            cp = pData[cp].nextLinkedPoint;
+          }
+          swsData[nEd].firstLinkedPoint = swsData[i].firstLinkedPoint;
+          swsData[i].firstLinkedPoint=-1;
+        }
+      }
+    }
+  } else if ( mod == bool_op_slice ) {
+  } else {
+    AssembleAretes ();
+  }
+  
+  for (int i = 0; i < numberOfPoints(); i++)
+    {
+      _pts[i].oldDegree = getPoint(i).totalDegree();
+    }
+
+  _need_edges_sorting = true;
+  if ( mod == bool_op_slice ) {
+  } else {
+    GetWindings (a, b, mod, false);
+  }
+//      Plot(190,70,6,400,400,true,true,true,true);
+
+  if (mod == bool_op_symdiff)
+  {
+    for (int i = 0; i < numberOfEdges(); i++)
+    {
+      if (swdData[i].leW < 0)
+        swdData[i].leW = -swdData[i].leW;
+      if (swdData[i].riW < 0)
+        swdData[i].riW = -swdData[i].riW;
+      
+      if (swdData[i].leW > 0 && swdData[i].riW <= 0)
+	    {
+	      eData[i].weight = 1;
+	    }
+      else if (swdData[i].leW <= 0 && swdData[i].riW > 0)
+	    {
+	      Inverse (i);
+	      eData[i].weight = 1;
+	    }
+      else
+	    {
+	      eData[i].weight = 0;
+	      SubEdge (i);
+	      i--;
+	    }
+    }
+  }
+  else if (mod == bool_op_union || mod == bool_op_diff)
+  {
+    for (int i = 0; i < numberOfEdges(); i++)
+    {
+      if (swdData[i].leW > 0 && swdData[i].riW <= 0)
+	    {
+	      eData[i].weight = 1;
+	    }
+      else if (swdData[i].leW <= 0 && swdData[i].riW > 0)
+	    {
+	      Inverse (i);
+	      eData[i].weight = 1;
+	    }
+      else
+	    {
+	      eData[i].weight = 0;
+	      SubEdge (i);
+	      i--;
+	    }
+    }
+  }
+  else if (mod == bool_op_inters)
+  {
+    for (int i = 0; i < numberOfEdges(); i++)
+    {
+      if (swdData[i].leW > 1 && swdData[i].riW <= 1)
+	    {
+	      eData[i].weight = 1;
+	    }
+      else if (swdData[i].leW <= 1 && swdData[i].riW > 1)
+	    {
+	      Inverse (i);
+	      eData[i].weight = 1;
+	    }
+      else
+	    {
+	      eData[i].weight = 0;
+	      SubEdge (i);
+	      i--;
+	    }
+    }
+  } else if ( mod == bool_op_cut ) {
+    // inverser les aretes de la coupe au besoin
+    for (int i=0;i<numberOfEdges();i++) {
+      if ( getEdge(i).st < 0 || getEdge(i).en < 0 ) {
+        if ( i < numberOfEdges()-1 ) {
+          // decaler les askForWinding
+          int cp = swsData[numberOfEdges()-1].firstLinkedPoint;
+          while (cp >= 0) {
+            pData[cp].askForWindingB = i;
+            cp = pData[cp].nextLinkedPoint;
+          }
+        }
+        SwapEdges(i,numberOfEdges()-1);
+        SubEdge(numberOfEdges()-1);
+//        SubEdge(i);
+        i--;
+      } else if ( ebData[i].pathID == cutPathID ) {
+        swdData[i].leW=swdData[i].leW%2;
+        swdData[i].riW=swdData[i].riW%2;
+        if ( swdData[i].leW < swdData[i].riW ) {
+          Inverse(i);
+        }
+      }
+    }
+  } else if ( mod == bool_op_slice ) {
+    // supprimer les aretes de la coupe
+    int i=numberOfEdges()-1;
+    for (;i>=0;i--) {
+      if ( ebData[i].pathID == cutPathID || getEdge(i).st < 0 || getEdge(i).en < 0 ) {
+        SubEdge(i);
+      }
+    }
+  }
+  else
+  {
+    for (int i = 0; i < numberOfEdges(); i++)
+    {
+      if (swdData[i].leW > 0 && swdData[i].riW <= 0)
+	    {
+	      eData[i].weight = 1;
+	    }
+      else if (swdData[i].leW <= 0 && swdData[i].riW > 0)
+	    {
+	      Inverse (i);
+	      eData[i].weight = 1;
+	    }
+      else
+	    {
+	      eData[i].weight = 0;
+	      SubEdge (i);
+	      i--;
+	    }
+    }
+  }
+  
+  delete sTree;
+  sTree = nullptr;
+  delete sEvts;
+  sEvts = nullptr;
+  
+  if ( mod == bool_op_cut ) {
+    // on garde le askForWinding
+  } else {
+    MakePointData (false);
+  }
+  MakeEdgeData (false);
+  MakeSweepSrcData (false);
+  MakeSweepDestData (false);
+  a->CleanupSweep ();
+  b->CleanupSweep ();
+
+  if (directedEulerian(this) == false)
+    {
+//              printf( "pas euclidian2");
+      _pts.clear();
+      _aretes.clear();
+      return shape_euler_err;
+    }
+  type = shape_polygon;
+  return 0;
+}
+
+// frontend to the TesteIntersection() below
+void Shape::TesteIntersection(SweepTree *t, Side s, bool onlyDiff)
+{
+    SweepTree *tt = static_cast<SweepTree*>(t->elem[s]);
+    if (tt == nullptr) {
+	return;
+    }
+
+    SweepTree *a = (s == LEFT) ? tt : t;
+    SweepTree *b = (s == LEFT) ? t : tt;
+
+    Geom::Point atx;
+    double atl;
+    double atr;
+    if (TesteIntersection(a, b, atx, atl, atr, onlyDiff)) {
+	sEvts->add(a, b, atx, atl, atr);
+    }
+}
+
+// a crucial piece of code: computing intersections between segments
+bool
+Shape::TesteIntersection (SweepTree * iL, SweepTree * iR, Geom::Point &atx, double &atL, double &atR, bool onlyDiff)
+{
+  int lSt = iL->src->getEdge(iL->bord).st, lEn = iL->src->getEdge(iL->bord).en;
+  int rSt = iR->src->getEdge(iR->bord).st, rEn = iR->src->getEdge(iR->bord).en;
+  Geom::Point ldir, rdir;
+  ldir = iL->src->eData[iL->bord].rdx;
+  rdir = iR->src->eData[iR->bord].rdx;
+  // first, a round of checks to quickly dismiss edge which obviously dont intersect,
+  // such as having disjoint bounding boxes
+  if (lSt < lEn)
+    {
+    }
+  else
+    {
+      int swap = lSt;
+      lSt = lEn;
+      lEn = swap;
+      ldir = -ldir;
+    }
+  if (rSt < rEn)
+    {
+    }
+  else
+    {
+      int swap = rSt;
+      rSt = rEn;
+      rEn = swap;
+      rdir = -rdir;
+    }
+
+  if (iL->src->pData[lSt].rx[0] < iL->src->pData[lEn].rx[0])
+    {
+      if (iR->src->pData[rSt].rx[0] < iR->src->pData[rEn].rx[0])
+	{
+	  if (iL->src->pData[lSt].rx[0] > iR->src->pData[rEn].rx[0])
+	    return false;
+	  if (iL->src->pData[lEn].rx[0] < iR->src->pData[rSt].rx[0])
+	    return false;
+	}
+      else
+	{
+	  if (iL->src->pData[lSt].rx[0] > iR->src->pData[rSt].rx[0])
+	    return false;
+	  if (iL->src->pData[lEn].rx[0] < iR->src->pData[rEn].rx[0])
+	    return false;
+	}
+    }
+  else
+    {
+      if (iR->src->pData[rSt].rx[0] < iR->src->pData[rEn].rx[0])
+	{
+	  if (iL->src->pData[lEn].rx[0] > iR->src->pData[rEn].rx[0])
+	    return false;
+	  if (iL->src->pData[lSt].rx[0] < iR->src->pData[rSt].rx[0])
+	    return false;
+	}
+      else
+	{
+	  if (iL->src->pData[lEn].rx[0] > iR->src->pData[rSt].rx[0])
+	    return false;
+	  if (iL->src->pData[lSt].rx[0] < iR->src->pData[rEn].rx[0])
+	    return false;
+	}
+    }
+
+  double ang = cross (ldir, rdir);
+//      ang*=iL->src->eData[iL->bord].isqlength;
+//      ang*=iR->src->eData[iR->bord].isqlength;
+  if (ang <= 0) return false;		// edges in opposite directions:  <-left  ... right ->
+                                // they can't intersect
+
+  // d'abord tester les bords qui partent d'un meme point
+  if (iL->src == iR->src && lSt == rSt)
+    {
+      if (iL->src == iR->src && lEn == rEn)
+	return false;		// c'est juste un doublon
+      atx = iL->src->pData[lSt].rx;
+      atR = atL = -1;
+      return true;		// l'ordre est mauvais
+    }
+  if (iL->src == iR->src && lEn == rEn)
+    return false;		// rien a faire=ils vont terminer au meme endroit
+
+  // tester si on est dans une intersection multiple
+
+  if (onlyDiff && iL->src == iR->src)
+    return false;
+
+  // on reprend les vrais points
+  lSt = iL->src->getEdge(iL->bord).st;
+  lEn = iL->src->getEdge(iL->bord).en;
+  rSt = iR->src->getEdge(iR->bord).st;
+  rEn = iR->src->getEdge(iR->bord).en;
+
+  // compute intersection (if there is one)
+  // Boissonat anr Preparata said in one paper that double precision floats were sufficient for get single precision
+  // coordinates for the intersection, if the endpoints are single precision. i hope they're right...
+  {
+    Geom::Point sDiff, eDiff;
+    double slDot, elDot;
+    double srDot, erDot;
+    sDiff = iL->src->pData[lSt].rx - iR->src->pData[rSt].rx;
+    eDiff = iL->src->pData[lEn].rx - iR->src->pData[rSt].rx;
+    srDot = cross(rdir, sDiff);
+    erDot = cross(rdir, eDiff);
+    sDiff = iR->src->pData[rSt].rx - iL->src->pData[lSt].rx;
+    eDiff = iR->src->pData[rEn].rx - iL->src->pData[lSt].rx;
+    slDot = cross(ldir, sDiff);
+    elDot = cross(ldir, eDiff);
+
+    if ((srDot >= 0 && erDot >= 0) || (srDot <= 0 && erDot <= 0))
+      {
+	if (srDot == 0)
+	  {
+	    if (lSt < lEn)
+	      {
+		atx = iL->src->pData[lSt].rx;
+		atL = 0;
+		atR = slDot / (slDot - elDot);
+		return true;
+	      }
+	    else
+	      {
+		return false;
+	      }
+	  }
+	else if (erDot == 0)
+	  {
+	    if (lSt > lEn)
+	      {
+		atx = iL->src->pData[lEn].rx;
+		atL = 1;
+		atR = slDot / (slDot - elDot);
+		return true;
+	      }
+	    else
+	      {
+		return false;
+	      }
+	  }
+	if (srDot > 0 && erDot > 0)
+	  {
+	    if (rEn < rSt)
+	      {
+		if (srDot < erDot)
+		  {
+		    if (lSt < lEn)
+		      {
+			atx = iL->src->pData[lSt].rx;
+			atL = 0;
+			atR = slDot / (slDot - elDot);
+			return true;
+		      }
+		  }
+		else
+		  {
+		    if (lEn < lSt)
+		      {
+			atx = iL->src->pData[lEn].rx;
+			atL = 1;
+			atR = slDot / (slDot - elDot);
+			return true;
+		      }
+		  }
+	      }
+	  }
+	if (srDot < 0 && erDot < 0)
+	  {
+	    if (rEn > rSt)
+	      {
+		if (srDot > erDot)
+		  {
+		    if (lSt < lEn)
+		      {
+			atx = iL->src->pData[lSt].rx;
+			atL = 0;
+			atR = slDot / (slDot - elDot);
+			return true;
+		      }
+		  }
+		else
+		  {
+		    if (lEn < lSt)
+		      {
+			atx = iL->src->pData[lEn].rx;
+			atL = 1;
+			atR = slDot / (slDot - elDot);
+			return true;
+		      }
+		  }
+	      }
+	  }
+	return false;
+      }
+    if ((slDot >= 0 && elDot >= 0) || (slDot <= 0 && elDot <= 0))
+      {
+	if (slDot == 0)
+	  {
+	    if (rSt < rEn)
+	      {
+		atx = iR->src->pData[rSt].rx;
+		atR = 0;
+		atL = srDot / (srDot - erDot);
+		return true;
+	      }
+	    else
+	      {
+		return false;
+	      }
+	  }
+	else if (elDot == 0)
+	  {
+	    if (rSt > rEn)
+	      {
+		atx = iR->src->pData[rEn].rx;
+		atR = 1;
+		atL = srDot / (srDot - erDot);
+		return true;
+	      }
+	    else
+	      {
+		return false;
+	      }
+	  }
+	if (slDot > 0 && elDot > 0)
+	  {
+	    if (lEn > lSt)
+	      {
+		if (slDot < elDot)
+		  {
+		    if (rSt < rEn)
+		      {
+			atx = iR->src->pData[rSt].rx;
+			atR = 0;
+			atL = srDot / (srDot - erDot);
+			return true;
+		      }
+		  }
+		else
+		  {
+		    if (rEn < rSt)
+		      {
+			atx = iR->src->pData[rEn].rx;
+			atR = 1;
+			atL = srDot / (srDot - erDot);
+			return true;
+		      }
+		  }
+	      }
+	  }
+	if (slDot < 0 && elDot < 0)
+	  {
+	    if (lEn < lSt)
+	      {
+		if (slDot > elDot)
+		  {
+		    if (rSt < rEn)
+		      {
+			atx = iR->src->pData[rSt].rx;
+			atR = 0;
+			atL = srDot / (srDot - erDot);
+			return true;
+		      }
+		  }
+		else
+		  {
+		    if (rEn < rSt)
+		      {
+			atx = iR->src->pData[rEn].rx;
+			atR = 1;
+			atL = srDot / (srDot - erDot);
+			return true;
+		      }
+		  }
+	      }
+	  }
+	return false;
+      }
+
+/*		double  slb=slDot-elDot,srb=srDot-erDot;
+		if ( slb < 0 ) slb=-slb;
+		if ( srb < 0 ) srb=-srb;*/
+    if (iL->src->eData[iL->bord].siEd > iR->src->eData[iR->bord].siEd)
+      {
+	atx =
+	  (slDot * iR->src->pData[rEn].rx -
+	   elDot * iR->src->pData[rSt].rx) / (slDot - elDot);
+      }
+    else
+      {
+	atx =
+	  (srDot * iL->src->pData[lEn].rx -
+	   erDot * iL->src->pData[lSt].rx) / (srDot - erDot);
+      }
+    atL = srDot / (srDot - erDot);
+    atR = slDot / (slDot - elDot);
+    return true;
+  }
+
+  return true;
+}
+
+int
+Shape::PushIncidence (Shape * a, int cb, int pt, double theta)
+{
+  if (theta < 0 || theta > 1)
+    return -1;
+
+  if (nbInc >= maxInc)
+    {
+      maxInc = 2 * nbInc + 1;
+      iData =
+	(incidenceData *) g_realloc(iData, maxInc * sizeof (incidenceData));
+    }
+  int n = nbInc++;
+  iData[n].nextInc = a->swsData[cb].firstLinkedPoint;
+  iData[n].pt = pt;
+  iData[n].theta = theta;
+  a->swsData[cb].firstLinkedPoint = n;
+  return n;
+}
+
+int
+Shape::CreateIncidence (Shape * a, int no, int nPt)
+{
+  Geom::Point adir, diff;
+  adir = a->eData[no].rdx;
+  diff = getPoint(nPt).x - a->pData[a->getEdge(no).st].rx;
+  double t = dot (diff, adir);
+  t *= a->eData[no].ilength;
+  return PushIncidence (a, no, nPt, t);
+}
+
+int
+Shape::Winding (int nPt) const 
+{
+  int askTo = pData[nPt].askForWindingB;
+  if (askTo < 0 || askTo >= numberOfEdges())
+    return 0;
+  if (getEdge(askTo).st < getEdge(askTo).en)
+    {
+      return swdData[askTo].leW;
+    }
+  else
+    {
+      return swdData[askTo].riW;
+    }
+  return 0;
+}
+
+int
+Shape::Winding (const Geom::Point px) const 
+{
+  int lr = 0, ll = 0, rr = 0;
+
+  for (int i = 0; i < numberOfEdges(); i++)
+    {
+      Geom::Point adir, diff, ast, aen;
+      adir = eData[i].rdx;
+
+      ast = pData[getEdge(i).st].rx;
+      aen = pData[getEdge(i).en].rx;
+
+      int nWeight = eData[i].weight;
+
+      if (ast[0] < aen[0])
+	{
+	  if (ast[0] > px[0])
+	    continue;
+	  if (aen[0] < px[0])
+	    continue;
+	}
+      else
+	{
+	  if (ast[0] < px[0])
+	    continue;
+	  if (aen[0] > px[0])
+	    continue;
+	}
+      if (ast[0] == px[0])
+	{
+	  if (ast[1] >= px[1])
+	    continue;
+	  if (aen[0] == px[0])
+	    continue;
+	  if (aen[0] < px[0])
+	    ll += nWeight;
+	  else
+	    rr -= nWeight;
+	  continue;
+	}
+      if (aen[0] == px[0])
+	{
+	  if (aen[1] >= px[1])
+	    continue;
+	  if (ast[0] == px[0])
+	    continue;
+	  if (ast[0] < px[0])
+	    ll -= nWeight;
+	  else
+	    rr += nWeight;
+	  continue;
+	}
+
+      if (ast[1] < aen[1])
+	{
+	  if (ast[1] >= px[1])
+	    continue;
+	}
+      else
+	{
+	  if (aen[1] >= px[1])
+	    continue;
+	}
+
+      diff = px - ast;
+      double cote = cross(adir, diff);
+      if (cote == 0)
+	continue;
+      if (cote < 0)
+	{
+	  if (ast[0] > px[0])
+	    lr += nWeight;
+	}
+      else
+	{
+	  if (ast[0] < px[0])
+	    lr -= nWeight;
+	}
+    }
+  return lr + (ll + rr) / 2;
+}
+
+// merging duplicate points and edges
+int
+Shape::AssemblePoints (int st, int en)
+{
+  if (en > st) {
+   for (int i = st; i < en; i++) pData[i].oldInd = i;
+//              SortPoints(st,en-1);
+    SortPointsByOldInd (st, en - 1); // SortPointsByOldInd() is required here, because of the edges we have
+                                       // associated with the point for later computation of winding numbers.
+                                       // specifically, we need the first point we treated, it's the only one with a valid
+                                       // associated edge (man, that was a nice bug).
+     for (int i = st; i < en; i++) pData[pData[i].oldInd].newInd = i;
+
+     int lastI = st;
+     for (int i = st; i < en; i++) {
+	      pData[i].pending = lastI++;
+	      if (i > st && getPoint(i - 1).x[0] == getPoint(i).x[0] && getPoint(i - 1).x[1] == getPoint(i).x[1]) {
+	        pData[i].pending = pData[i - 1].pending;
+	        if (pData[pData[i].pending].askForWindingS == nullptr) {
+		        pData[pData[i].pending].askForWindingS = pData[i].askForWindingS;
+		        pData[pData[i].pending].askForWindingB = pData[i].askForWindingB;
+		      } else {
+		        if (pData[pData[i].pending].askForWindingS == pData[i].askForWindingS
+		      && pData[pData[i].pending].askForWindingB == pData[i].askForWindingB) {
+		      // meme bord, c bon
+		        } else {
+		      // meme point, mais pas le meme bord: ouille!
+		      // il faut prendre le bord le plus a gauche
+		      // en pratique, n'arrive que si 2 maxima sont dans la meme case -> le mauvais choix prend une arete incidente 
+		      // au bon choix
+//                                              printf("doh");
+		        }
+		      }
+	        lastI--;
+	      } else {
+	        if (i > pData[i].pending) {
+		        _pts[pData[i].pending].x = getPoint(i).x;
+		        pData[pData[i].pending].rx = getPoint(i).x;
+		        pData[pData[i].pending].askForWindingS = pData[i].askForWindingS;
+		        pData[pData[i].pending].askForWindingB = pData[i].askForWindingB;
+		      }
+	      }
+	    }
+      for (int i = st; i < en; i++) pData[i].newInd = pData[pData[i].newInd].pending;
+      return lastI;
+  }
+  return en;
+}
+
+void
+Shape::AssemblePoints (Shape * a)
+{
+  if (hasPoints())
+    {
+      int lastI = AssemblePoints (0, numberOfPoints());
+
+      for (int i = 0; i < a->numberOfEdges(); i++)
+	{
+	  a->swsData[i].stPt = pData[a->swsData[i].stPt].newInd;
+	  a->swsData[i].enPt = pData[a->swsData[i].enPt].newInd;
+	}
+      for (int i = 0; i < nbInc; i++)
+	iData[i].pt = pData[iData[i].pt].newInd;
+
+      _pts.resize(lastI);
+    }
+}
+void
+Shape::AssembleAretes (FillRule directed)
+{
+  if ( directed == fill_justDont && _has_back_data == false ) {
+    directed=fill_nonZero;
+  }
+  
+  for (int i = 0; i < numberOfPoints(); i++) {
+    if (getPoint(i).totalDegree() == 2) {
+      int cb, cc;
+      cb = getPoint(i).incidentEdge[FIRST];
+      cc = getPoint(i).incidentEdge[LAST];
+      bool  doublon=false;
+      if ((getEdge(cb).st == getEdge(cc).st && getEdge(cb).en == getEdge(cc).en)
+          || (getEdge(cb).st == getEdge(cc).en && getEdge(cb).en == getEdge(cc).en)) doublon=true;
+      if ( directed == fill_justDont ) {
+        if ( doublon ) {
+          if ( ebData[cb].pathID > ebData[cc].pathID ) {
+            cc = getPoint(i).incidentEdge[FIRST]; // on swappe pour enlever cc
+            cb = getPoint(i).incidentEdge[LAST];
+          } else if ( ebData[cb].pathID == ebData[cc].pathID ) {
+            if ( ebData[cb].pieceID > ebData[cc].pieceID ) {
+              cc = getPoint(i).incidentEdge[FIRST]; // on swappe pour enlever cc
+              cb = getPoint(i).incidentEdge[LAST];
+            } else if ( ebData[cb].pieceID == ebData[cc].pieceID ) { 
+              if ( ebData[cb].tSt > ebData[cc].tSt ) {
+                cc = getPoint(i).incidentEdge[FIRST]; // on swappe pour enlever cc
+                cb = getPoint(i).incidentEdge[LAST];
+              }
+            }
+          }
+        }
+        if ( doublon ) eData[cc].weight = 0;
+      } else {
+      }
+      if ( doublon ) {
+        if (getEdge(cb).st == getEdge(cc).st) {
+          eData[cb].weight += eData[cc].weight;
+        } else {
+          eData[cb].weight -= eData[cc].weight;
+        }
+ 	      eData[cc].weight = 0;
+        
+	      if (swsData[cc].firstLinkedPoint >= 0) {
+          int cp = swsData[cc].firstLinkedPoint;
+          while (cp >= 0) {
+            pData[cp].askForWindingB = cb;
+            cp = pData[cp].nextLinkedPoint;
+          }
+          if (swsData[cb].firstLinkedPoint < 0) {
+            swsData[cb].firstLinkedPoint = swsData[cc].firstLinkedPoint;
+          } else {
+            int ncp = swsData[cb].firstLinkedPoint;
+            while (pData[ncp].nextLinkedPoint >= 0) {
+              ncp = pData[ncp].nextLinkedPoint;
+            }
+            pData[ncp].nextLinkedPoint = swsData[cc].firstLinkedPoint;
+          }
+        }
+        
+	      DisconnectStart (cc);
+	      DisconnectEnd (cc);
+	      if (numberOfEdges() > 1) {
+          int cp = swsData[numberOfEdges() - 1].firstLinkedPoint;
+          while (cp >= 0) {
+            pData[cp].askForWindingB = cc;
+            cp = pData[cp].nextLinkedPoint;
+          }
+        }
+	      SwapEdges (cc, numberOfEdges() - 1);
+	      if (cb == numberOfEdges() - 1) {
+          cb = cc;
+        }
+	      _aretes.pop_back();
+	    }
+    } else {
+      int cb;
+      cb = getPoint(i).incidentEdge[FIRST];
+      while (cb >= 0 && cb < numberOfEdges()) {
+	      int other = Other (i, cb);
+	      int cc;
+	      cc = getPoint(i).incidentEdge[FIRST];
+	      while (cc >= 0 && cc < numberOfEdges()) {
+          int ncc = NextAt (i, cc);
+          bool  doublon=false;
+          if (cc != cb && Other (i, cc) == other ) doublon=true;
+          if ( directed == fill_justDont ) {
+            if ( doublon ) {
+              if ( ebData[cb].pathID > ebData[cc].pathID ) {
+                doublon=false;
+              } else if ( ebData[cb].pathID == ebData[cc].pathID ) {
+                if ( ebData[cb].pieceID > ebData[cc].pieceID ) {
+                  doublon=false;
+                } else if ( ebData[cb].pieceID == ebData[cc].pieceID ) { 
+                  if ( ebData[cb].tSt > ebData[cc].tSt ) {
+                    doublon=false;
+                  }
+                }
+              }
+            }
+            if ( doublon ) eData[cc].weight = 0;
+          } else {
+          }
+          if ( doublon ) {
+//            if (cc != cb && Other (i, cc) == other) {
+            // doublon
+            if (getEdge(cb).st == getEdge(cc).st) {
+              eData[cb].weight += eData[cc].weight;
+            } else {
+              eData[cb].weight -= eData[cc].weight;
+            }
+            eData[cc].weight = 0;
+            
+            if (swsData[cc].firstLinkedPoint >= 0) {
+              int cp = swsData[cc].firstLinkedPoint;
+              while (cp >= 0) {
+                pData[cp].askForWindingB = cb;
+                cp = pData[cp].nextLinkedPoint;
+              }
+              if (swsData[cb].firstLinkedPoint < 0) {
+                swsData[cb].firstLinkedPoint = swsData[cc].firstLinkedPoint;
+              } else {
+                int ncp = swsData[cb].firstLinkedPoint;
+                while (pData[ncp].nextLinkedPoint >= 0) {
+                  ncp = pData[ncp].nextLinkedPoint;
+                }
+                pData[ncp].nextLinkedPoint = swsData[cc].firstLinkedPoint;
+              }
+            }
+            
+            DisconnectStart (cc);
+            DisconnectEnd (cc);
+            if (numberOfEdges() > 1) {
+              int cp = swsData[numberOfEdges() - 1].firstLinkedPoint;
+              while (cp >= 0) {
+                pData[cp].askForWindingB = cc;
+                cp = pData[cp].nextLinkedPoint;
+              }
+            }
+            SwapEdges (cc, numberOfEdges() - 1);
+            if (cb == numberOfEdges() - 1) {
+              cb = cc;
+            }
+            if (ncc == numberOfEdges() - 1) {
+              ncc = cc;
+            }
+	    _aretes.pop_back();
+          }
+          cc = ncc;
+        }
+	      cb = NextAt (i, cb);
+	    }
+    }
+  }
+  
+  if ( directed == fill_justDont ) {
+    for (int i = 0; i < numberOfEdges(); i++)  {
+      if (eData[i].weight == 0) {
+//        SubEdge(i);
+ //       i--;
+      } else {
+        if (eData[i].weight < 0) Inverse (i);
+      }
+    }
+  } else {
+    for (int i = 0; i < numberOfEdges(); i++)  {
+      if (eData[i].weight == 0) {
+        //                      SubEdge(i);
+        //                      i--;
+      } else {
+        if (eData[i].weight < 0) Inverse (i);
+      }
+    }
+  }
+}
+void
+Shape::GetWindings (Shape * /*a*/, Shape * /*b*/, BooleanOp /*mod*/, bool brutal)
+{
+  // preparation du parcours
+  for (int i = 0; i < numberOfEdges(); i++)
+    {
+      swdData[i].misc = nullptr;
+      swdData[i].precParc = swdData[i].suivParc = -1;
+    }
+
+  // chainage
+  SortEdges ();
+
+  int searchInd = 0;
+
+  int lastPtUsed = 0;
+  do
+    {
+      int startBord = -1;
+      int outsideW = 0;
+      {
+	int fi = 0;
+	for (fi = lastPtUsed; fi < numberOfPoints(); fi++)
+	  {
+	    if (getPoint(fi).incidentEdge[FIRST] >= 0 && swdData[getPoint(fi).incidentEdge[FIRST]].misc == nullptr)
+	      break;
+	  }
+	lastPtUsed = fi + 1;
+	if (fi < numberOfPoints())
+	  {
+	    int bestB = getPoint(fi).incidentEdge[FIRST];
+	    if (bestB >= 0)
+	      {
+		startBord = bestB;
+		if (fi == 0)
+		  {
+		    outsideW = 0;
+		  }
+		else
+		  {
+		    if (brutal)
+		      {
+			outsideW = Winding (getPoint(fi).x);
+		      }
+		    else
+		      {
+			outsideW = Winding (fi);
+		      }
+		  }
+    if ( getPoint(fi).totalDegree() == 1 ) {
+      if ( fi == getEdge(startBord).en ) {
+        if ( eData[startBord].weight == 0 ) {
+          // on se contente d'inverser
+          Inverse(startBord);
+        } else {
+          // on passe le askForWinding (sinon ca va rester startBord)
+          pData[getEdge(startBord).st].askForWindingB=pData[getEdge(startBord).en].askForWindingB;
+        }
+      }
+    }
+		if (getEdge(startBord).en == fi)
+		  outsideW += eData[startBord].weight;
+	      }
+	  }
+      }
+      if (startBord >= 0)
+	{
+	  // parcours en profondeur pour mettre les leF et riF a leurs valeurs
+	  swdData[startBord].misc = (void *) 1;
+	  swdData[startBord].leW = outsideW;
+	  swdData[startBord].riW = outsideW - eData[startBord].weight;
+//    if ( doDebug ) printf("part de %d\n",startBord);
+	  int curBord = startBord;
+	  bool curDir = true;
+	  swdData[curBord].precParc = -1;
+	  swdData[curBord].suivParc = -1;
+	  do
+	    {
+	      int cPt;
+	      if (curDir)
+		cPt = getEdge(curBord).en;
+	      else
+		cPt = getEdge(curBord).st;
+	      int nb = curBord;
+//        if ( doDebug ) printf("de curBord= %d avec leF= %d et riF= %d  -> ",curBord,swdData[curBord].leW,swdData[curBord].riW);
+	      do
+		{
+		  int nnb = -1;
+		  if (getEdge(nb).en == cPt)
+		    {
+		      outsideW = swdData[nb].riW;
+		      nnb = CyclePrevAt (cPt, nb);
+		    }
+		  else
+		    {
+		      outsideW = swdData[nb].leW;
+		      nnb = CyclePrevAt (cPt, nb);
+		    }
+		  if (nnb == nb)
+		    {
+		      // cul-de-sac
+		      nb = -1;
+		      break;
+		    }
+		  nb = nnb;
+		}
+	      while (nb >= 0 && nb != curBord && swdData[nb].misc != nullptr);
+	      if (nb < 0 || nb == curBord)
+		{
+		  // retour en arriere
+		  int oPt;
+		  if (curDir)
+		    oPt = getEdge(curBord).st;
+		  else
+		    oPt = getEdge(curBord).en;
+		  curBord = swdData[curBord].precParc;
+//    if ( doDebug ) printf("retour vers %d\n",curBord);
+		  if (curBord < 0)
+		    break;
+		  if (oPt == getEdge(curBord).en)
+		    curDir = true;
+		  else
+		    curDir = false;
+		}
+	      else
+		{
+		  swdData[nb].misc = (void *) 1;
+		  swdData[nb].ind = searchInd++;
+		  if (cPt == getEdge(nb).st)
+		    {
+		      swdData[nb].riW = outsideW;
+		      swdData[nb].leW = outsideW + eData[nb].weight;
+		    }
+		  else
+		    {
+		      swdData[nb].leW = outsideW;
+		      swdData[nb].riW = outsideW - eData[nb].weight;
+		    }
+		  swdData[nb].precParc = curBord;
+		  swdData[curBord].suivParc = nb;
+		  curBord = nb;
+//		  if ( doDebug ) printf("suite %d\n",curBord);
+		  if (cPt == getEdge(nb).en)
+		    curDir = false;
+		  else
+		    curDir = true;
+		}
+	    }
+	  while (true /*swdData[curBord].precParc >= 0 */ );
+	  // fin du cas non-oriente
+	}
+    }
+  while (lastPtUsed < numberOfPoints());
+//      fflush(stdout);
+}
+
+bool
+Shape::TesteIntersection (Shape * ils, Shape * irs, int ilb, int irb,
+                          Geom::Point &atx, double &atL, double &atR,
+			  bool /*onlyDiff*/)
+{
+  int lSt = ils->getEdge(ilb).st, lEn = ils->getEdge(ilb).en;
+  int rSt = irs->getEdge(irb).st, rEn = irs->getEdge(irb).en;
+  if (lSt == rSt || lSt == rEn)
+    {
+      return false;
+    }
+  if (lEn == rSt || lEn == rEn)
+    {
+      return false;
+    }
+
+  Geom::Point ldir, rdir;
+  ldir = ils->eData[ilb].rdx;
+  rdir = irs->eData[irb].rdx;
+
+  double il = ils->pData[lSt].rx[0], it = ils->pData[lSt].rx[1], ir =
+    ils->pData[lEn].rx[0], ib = ils->pData[lEn].rx[1];
+  if (il > ir)
+    {
+      double swf = il;
+      il = ir;
+      ir = swf;
+    }
+  if (it > ib)
+    {
+      double swf = it;
+      it = ib;
+      ib = swf;
+    }
+  double jl = irs->pData[rSt].rx[0], jt = irs->pData[rSt].rx[1], jr =
+    irs->pData[rEn].rx[0], jb = irs->pData[rEn].rx[1];
+  if (jl > jr)
+    {
+      double swf = jl;
+      jl = jr;
+      jr = swf;
+    }
+  if (jt > jb)
+    {
+      double swf = jt;
+      jt = jb;
+      jb = swf;
+    }
+
+  if (il > jr || it > jb || ir < jl || ib < jt)
+    return false;
+
+  // pre-test
+  {
+    Geom::Point sDiff, eDiff;
+    double slDot, elDot;
+    double srDot, erDot;
+    sDiff = ils->pData[lSt].rx - irs->pData[rSt].rx;
+    eDiff = ils->pData[lEn].rx - irs->pData[rSt].rx;
+    srDot = cross(rdir, sDiff);
+    erDot = cross(rdir, eDiff);
+    if ((srDot >= 0 && erDot >= 0) || (srDot <= 0 && erDot <= 0))
+      return false;
+
+    sDiff = irs->pData[rSt].rx - ils->pData[lSt].rx;
+    eDiff = irs->pData[rEn].rx - ils->pData[lSt].rx;
+    slDot = cross(ldir, sDiff);
+    elDot = cross(ldir, eDiff);
+    if ((slDot >= 0 && elDot >= 0) || (slDot <= 0 && elDot <= 0))
+      return false;
+
+    double slb = slDot - elDot, srb = srDot - erDot;
+    if (slb < 0)
+      slb = -slb;
+    if (srb < 0)
+      srb = -srb;
+    if (slb > srb)
+      {
+	atx =
+	  (slDot * irs->pData[rEn].rx - elDot * irs->pData[rSt].rx) / (slDot -
+								       elDot);
+      }
+    else
+      {
+	atx =
+	  (srDot * ils->pData[lEn].rx - erDot * ils->pData[lSt].rx) / (srDot -
+								       erDot);
+      }
+    atL = srDot / (srDot - erDot);
+    atR = slDot / (slDot - elDot);
+    return true;
+  }
+
+  // a mettre en double precision pour des resultats exacts
+  Geom::Point usvs;
+  usvs = irs->pData[rSt].rx - ils->pData[lSt].rx;
+
+  // pas sur de l'ordre des coefs de m
+  Geom::Affine m(ldir[0], ldir[1],
+	       rdir[0], rdir[1],
+	       0, 0);
+  double det = m.det();
+
+  double tdet = det * ils->eData[ilb].isqlength * irs->eData[irb].isqlength;
+
+  if (tdet > -0.0001 && tdet < 0.0001)
+    {				// ces couillons de vecteurs sont colineaires
+      Geom::Point sDiff, eDiff;
+      double sDot, eDot;
+      sDiff = ils->pData[lSt].rx - irs->pData[rSt].rx;
+      eDiff = ils->pData[lEn].rx - irs->pData[rSt].rx;
+      sDot = cross(rdir, sDiff);
+      eDot = cross(rdir, eDiff);
+
+      atx =
+	(sDot * irs->pData[lEn].rx - eDot * irs->pData[lSt].rx) / (sDot -
+								   eDot);
+      atL = sDot / (sDot - eDot);
+
+      sDiff = irs->pData[rSt].rx - ils->pData[lSt].rx;
+       eDiff = irs->pData[rEn].rx - ils->pData[lSt].rx;
+      sDot = cross(ldir, sDiff);
+      eDot = cross(ldir, eDiff);
+
+      atR = sDot / (sDot - eDot);
+
+      return true;
+    }
+
+  // plus de colinearite ni d'extremites en commun
+  m[1] = -m[1];
+  m[2] = -m[2];
+  {
+    double swap = m[0];
+    m[0] = m[3];
+    m[3] = swap;
+  }
+
+  atL = (m[0]* usvs[0] + m[1] * usvs[1]) / det;
+  atR = -(m[2] * usvs[0] + m[3] * usvs[1]) / det;
+  atx = ils->pData[lSt].rx + atL * ldir;
+
+
+  return true;
+}
+
+bool
+Shape::TesteAdjacency (Shape * a, int no, const Geom::Point atx, int nPt,
+		       bool push)
+{
+  if (nPt == a->swsData[no].stPt || nPt == a->swsData[no].enPt)
+    return false;
+
+  Geom::Point adir, diff, ast, aen, diff1, diff2, diff3, diff4;
+
+  ast = a->pData[a->getEdge(no).st].rx;
+  aen = a->pData[a->getEdge(no).en].rx;
+
+  adir = a->eData[no].rdx;
+
+  double sle = a->eData[no].length;
+  double ile = a->eData[no].ilength;
+
+  diff = atx - ast;
+ 
+  double e = IHalfRound(cross(adir, diff) * a->eData[no].isqlength);
+  if (-3 < e && e < 3)
+    {
+      double rad = HalfRound (0.501); // when using single precision, 0.505 is better (0.5 would be the correct value, 
+                                      // but it produces lots of bugs)
+      diff1[0] = diff[0] - rad;
+      diff1[1] = diff[1] - rad;
+      diff2[0] = diff[0] + rad;
+      diff2[1] = diff[1] - rad;
+      diff3[0] = diff[0] + rad;
+      diff3[1] = diff[1] + rad;
+      diff4[0] = diff[0] - rad;
+      diff4[1] = diff[1] + rad;
+      double di1, di2;
+      bool adjacent = false;
+      di1 = cross(adir, diff1);
+      di2 = cross(adir, diff3);
+      if ((di1 < 0 && di2 > 0) || (di1 > 0 && di2 < 0))
+	{
+	  adjacent = true;
+	}
+      else
+	{
+	  di1 = cross(adir, diff2);
+	  di2 = cross(adir, diff4);
+	  if ((di1 < 0 && di2 > 0) || (di1 > 0 && di2 < 0))
+	    {
+	      adjacent = true;
+	    }
+	}
+      if (adjacent)
+	{
+	  double t = dot (diff, adir);
+	  if (t > 0 && t < sle)
+	    {
+	      if (push)
+		{
+		  t *= ile;
+		  PushIncidence (a, no, nPt, t);
+		}
+	      return true;
+	    }
+	}
+    }
+  return false;
+}
+
+void
+Shape::CheckAdjacencies (int lastPointNo, int lastChgtPt, Shape * /*shapeHead*/,
+			 int /*edgeHead*/)
+{
+  for (auto & chgt : chgts)
+    {
+      int chLeN = chgt.ptNo;
+      int chRiN = chgt.ptNo;
+      if (chgt.src)
+	{
+	  Shape *lS = chgt.src;
+	  int lB = chgt.bord;
+	  int lftN = lS->swsData[lB].leftRnd;
+	  int rgtN = lS->swsData[lB].rightRnd;
+	  if (lftN < chLeN)
+	    chLeN = lftN;
+	  if (rgtN > chRiN)
+	    chRiN = rgtN;
+//                      for (int n=lftN;n<=rgtN;n++) CreateIncidence(lS,lB,n);
+	  for (int n = lftN - 1; n >= lastChgtPt; n--)
+	    {
+	      if (TesteAdjacency (lS, lB, getPoint(n).x, n, false) ==
+		  false)
+                break;
+              lS->swsData[lB].leftRnd = n;
+	    }
+	  for (int n = rgtN + 1; n < lastPointNo; n++)
+	    {
+	      if (TesteAdjacency (lS, lB, getPoint(n).x, n, false) ==
+		  false)
+		break;
+	      lS->swsData[lB].rightRnd = n;
+	    }
+	}
+      if (chgt.osrc)
+	{
+	  Shape *rS = chgt.osrc;
+	  int rB = chgt.obord;
+	  int lftN = rS->swsData[rB].leftRnd;
+	  int rgtN = rS->swsData[rB].rightRnd;
+	  if (lftN < chLeN)
+	    chLeN = lftN;
+	  if (rgtN > chRiN)
+	    chRiN = rgtN;
+//                      for (int n=lftN;n<=rgtN;n++) CreateIncidence(rS,rB,n);
+	  for (int n = lftN - 1; n >= lastChgtPt; n--)
+	    {
+	      if (TesteAdjacency (rS, rB, getPoint(n).x, n, false) ==
+		  false)
+		break;
+              rS->swsData[rB].leftRnd = n;
+	    }
+	  for (int n = rgtN + 1; n < lastPointNo; n++)
+	    {
+	      if (TesteAdjacency (rS, rB, getPoint(n).x, n, false) ==
+		  false)
+		break;
+	      rS->swsData[rB].rightRnd = n;
+	    }
+	}
+      if (chgt.lSrc)
+	{
+	  if (chgt.lSrc->swsData[chgt.lBrd].leftRnd < lastChgtPt)
+	    {
+	      Shape *nSrc = chgt.lSrc;
+	      int nBrd = chgt.lBrd /*,nNo=chgts[cCh].ptNo */ ;
+	      bool hit;
+
+	      do
+		{
+		  hit = false;
+		  for (int n = chRiN; n >= chLeN; n--)
+		    {
+		      if (TesteAdjacency
+			  (nSrc, nBrd, getPoint(n).x, n, false))
+			{
+			  if (nSrc->swsData[nBrd].leftRnd < lastChgtPt)
+			    {
+			      nSrc->swsData[nBrd].leftRnd = n;
+			      nSrc->swsData[nBrd].rightRnd = n;
+			    }
+			  else
+			    {
+			      if (n < nSrc->swsData[nBrd].leftRnd)
+				nSrc->swsData[nBrd].leftRnd = n;
+			      if (n > nSrc->swsData[nBrd].rightRnd)
+				nSrc->swsData[nBrd].rightRnd = n;
+			    }
+			  hit = true;
+			}
+		    }
+		  for (int n = chLeN - 1; n >= lastChgtPt; n--)
+		    {
+		      if (TesteAdjacency
+			  (nSrc, nBrd, getPoint(n).x, n, false) == false)
+			break;
+		      if (nSrc->swsData[nBrd].leftRnd < lastChgtPt)
+			{
+			  nSrc->swsData[nBrd].leftRnd = n;
+			  nSrc->swsData[nBrd].rightRnd = n;
+			}
+		      else
+			{
+			  if (n < nSrc->swsData[nBrd].leftRnd)
+			    nSrc->swsData[nBrd].leftRnd = n;
+			  if (n > nSrc->swsData[nBrd].rightRnd)
+			    nSrc->swsData[nBrd].rightRnd = n;
+			}
+		      hit = true;
+		    }
+		  if (hit)
+		    {
+		      SweepTree *node =
+			static_cast < SweepTree * >(nSrc->swsData[nBrd].misc);
+		      if (node == nullptr)
+			break;
+		      node = static_cast < SweepTree * >(node->elem[LEFT]);
+		      if (node == nullptr)
+			break;
+		      nSrc = node->src;
+		      nBrd = node->bord;
+		      if (nSrc->swsData[nBrd].leftRnd >= lastChgtPt)
+			break;
+		    }
+		}
+	      while (hit);
+
+	    }
+	}
+      if (chgt.rSrc)
+	{
+	  if (chgt.rSrc->swsData[chgt.rBrd].leftRnd < lastChgtPt)
+	    {
+	      Shape *nSrc = chgt.rSrc;
+	      int nBrd = chgt.rBrd /*,nNo=chgts[cCh].ptNo */ ;
+	      bool hit;
+	      do
+		{
+		  hit = false;
+		  for (int n = chLeN; n <= chRiN; n++)
+		    {
+		      if (TesteAdjacency
+			  (nSrc, nBrd, getPoint(n).x, n, false))
+			{
+			  if (nSrc->swsData[nBrd].leftRnd < lastChgtPt)
+			    {
+			      nSrc->swsData[nBrd].leftRnd = n;
+			      nSrc->swsData[nBrd].rightRnd = n;
+			    }
+			  else
+			    {
+			      if (n < nSrc->swsData[nBrd].leftRnd)
+				nSrc->swsData[nBrd].leftRnd = n;
+			      if (n > nSrc->swsData[nBrd].rightRnd)
+				nSrc->swsData[nBrd].rightRnd = n;
+			    }
+			  hit = true;
+			}
+		    }
+		  for (int n = chRiN + 1; n < lastPointNo; n++)
+		    {
+		      if (TesteAdjacency
+			  (nSrc, nBrd, getPoint(n).x, n, false) == false)
+			break;
+		      if (nSrc->swsData[nBrd].leftRnd < lastChgtPt)
+			{
+			  nSrc->swsData[nBrd].leftRnd = n;
+			  nSrc->swsData[nBrd].rightRnd = n;
+			}
+		      else
+			{
+			  if (n < nSrc->swsData[nBrd].leftRnd)
+			    nSrc->swsData[nBrd].leftRnd = n;
+			  if (n > nSrc->swsData[nBrd].rightRnd)
+			    nSrc->swsData[nBrd].rightRnd = n;
+			}
+		      hit = true;
+		    }
+		  if (hit)
+		    {
+		      SweepTree *node =
+			static_cast < SweepTree * >(nSrc->swsData[nBrd].misc);
+		      if (node == nullptr)
+			break;
+		      node = static_cast < SweepTree * >(node->elem[RIGHT]);
+		      if (node == nullptr)
+			break;
+		      nSrc = node->src;
+		      nBrd = node->bord;
+		      if (nSrc->swsData[nBrd].leftRnd >= lastChgtPt)
+			break;
+		    }
+		}
+	      while (hit);
+	    }
+	}
+    }
+}
+
+
+void Shape::AddChgt(int lastPointNo, int lastChgtPt, Shape * &shapeHead,
+		    int &edgeHead, sTreeChangeType type, Shape * lS, int lB, Shape * rS,
+		    int rB)
+{
+    sTreeChange c;
+    c.ptNo = lastPointNo;
+    c.type = type;
+    c.src = lS;
+    c.bord = lB;
+    c.osrc = rS;
+    c.obord = rB;
+    chgts.push_back(c);
+    const int nCh = chgts.size() - 1;
+
+    /* FIXME: this looks like a cut and paste job */
+
+    if (lS) {
+	SweepTree *lE = static_cast < SweepTree * >(lS->swsData[lB].misc);
+	if (lE && lE->elem[LEFT]) {
+	    SweepTree *llE = static_cast < SweepTree * >(lE->elem[LEFT]);
+	    chgts[nCh].lSrc = llE->src;
+	    chgts[nCh].lBrd = llE->bord;
+	} else {
+	    chgts[nCh].lSrc = nullptr;
+	    chgts[nCh].lBrd = -1;
+	}
+
+	if (lS->swsData[lB].leftRnd < lastChgtPt) {
+	    lS->swsData[lB].leftRnd = lastPointNo;
+	    lS->swsData[lB].nextSh = shapeHead;
+	    lS->swsData[lB].nextBo = edgeHead;
+	    edgeHead = lB;
+	    shapeHead = lS;
+	} else {
+	    int old = lS->swsData[lB].leftRnd;
+	    if (getPoint(old).x[0] > getPoint(lastPointNo).x[0]) {
+		lS->swsData[lB].leftRnd = lastPointNo;
+	    }
+	}
+	if (lS->swsData[lB].rightRnd < lastChgtPt) {
+	    lS->swsData[lB].rightRnd = lastPointNo;
+	} else {
+	    int old = lS->swsData[lB].rightRnd;
+	    if (getPoint(old).x[0] < getPoint(lastPointNo).x[0])
+		lS->swsData[lB].rightRnd = lastPointNo;
+	}
+    }
+
+    if (rS) {
+	SweepTree *rE = static_cast < SweepTree * >(rS->swsData[rB].misc);
+	if (rE->elem[RIGHT]) {
+	    SweepTree *rrE = static_cast < SweepTree * >(rE->elem[RIGHT]);
+	    chgts[nCh].rSrc = rrE->src;
+	    chgts[nCh].rBrd = rrE->bord;
+	} else {
+	    chgts[nCh].rSrc = nullptr;
+	    chgts[nCh].rBrd = -1;
+	}
+	
+	if (rS->swsData[rB].leftRnd < lastChgtPt) {
+	    rS->swsData[rB].leftRnd = lastPointNo;
+	    rS->swsData[rB].nextSh = shapeHead;
+	    rS->swsData[rB].nextBo = edgeHead;
+	    edgeHead = rB;
+	    shapeHead = rS;
+	} else {
+	    int old = rS->swsData[rB].leftRnd;
+	    if (getPoint(old).x[0] > getPoint(lastPointNo).x[0]) {
+		rS->swsData[rB].leftRnd = lastPointNo;
+	    }
+	}
+	if (rS->swsData[rB].rightRnd < lastChgtPt) {
+	    rS->swsData[rB].rightRnd = lastPointNo;
+	} else {
+	    int old = rS->swsData[rB].rightRnd;
+	    if (getPoint(old).x[0] < getPoint(lastPointNo).x[0])
+		rS->swsData[rB].rightRnd = lastPointNo;
+	}
+    } else {
+	SweepTree *lE = static_cast < SweepTree * >(lS->swsData[lB].misc);
+	if (lE && lE->elem[RIGHT]) {
+	    SweepTree *rlE = static_cast < SweepTree * >(lE->elem[RIGHT]);
+	    chgts[nCh].rSrc = rlE->src;
+	    chgts[nCh].rBrd = rlE->bord;
+	} else {
+	    chgts[nCh].rSrc = nullptr;
+	    chgts[nCh].rBrd = -1;
+	}
+    }
+}
+
+// is this a debug function?  It's calling localized "printf" ...
+void
+Shape::Validate ()
+{
+  for (int i = 0; i < numberOfPoints(); i++)
+    {
+      pData[i].rx = getPoint(i).x;
+    }
+  for (int i = 0; i < numberOfEdges(); i++)
+    {
+      eData[i].rdx = getEdge(i).dx;
+    }
+  for (int i = 0; i < numberOfEdges(); i++)
+    {
+      for (int j = i + 1; j < numberOfEdges(); j++)
+	{
+        Geom::Point atx;
+        double   atL, atR;
+	  if (TesteIntersection (this, this, i, j, atx, atL, atR, false))
+	    {
+	      printf ("%i %i  %f %f di=%f %f  dj=%f %f\n", i, j, atx[0],atx[1],getEdge(i).dx[0],getEdge(i).dx[1],getEdge(j).dx[0],getEdge(j).dx[1]);
+	    }
+	}
+    }
+  fflush (stdout);
+}
+
+void
+Shape::CheckEdges (int lastPointNo, int lastChgtPt, Shape * a, Shape * b,
+		   BooleanOp mod)
+{
+
+  for (auto & chgt : chgts)
+    {
+      if (chgt.type == 0)
+	{
+	  Shape *lS = chgt.src;
+	  int lB = chgt.bord;
+	  lS->swsData[lB].curPoint = chgt.ptNo;
+	}
+    }
+  for (auto & chgt : chgts)
+    {
+//              int   chLeN=chgts[cCh].ptNo;
+//              int   chRiN=chgts[cCh].ptNo;
+      if (chgt.src)
+	{
+	  Shape *lS = chgt.src;
+	  int lB = chgt.bord;
+	  Avance (lastPointNo, lastChgtPt, lS, lB, a, b, mod);
+	}
+      if (chgt.osrc)
+	{
+	  Shape *rS = chgt.osrc;
+	  int rB = chgt.obord;
+	  Avance (lastPointNo, lastChgtPt, rS, rB, a, b, mod);
+	}
+      if (chgt.lSrc)
+	{
+	  Shape *nSrc = chgt.lSrc;
+	  int nBrd = chgt.lBrd;
+	  while (nSrc->swsData[nBrd].leftRnd >=
+		 lastChgtPt /*&& nSrc->swsData[nBrd].doneTo < lastChgtPt */ )
+	    {
+	      Avance (lastPointNo, lastChgtPt, nSrc, nBrd, a, b, mod);
+
+	      SweepTree *node =
+		static_cast < SweepTree * >(nSrc->swsData[nBrd].misc);
+	      if (node == nullptr)
+		break;
+	      node = static_cast < SweepTree * >(node->elem[LEFT]);
+	      if (node == nullptr)
+		break;
+	      nSrc = node->src;
+	      nBrd = node->bord;
+	    }
+	}
+      if (chgt.rSrc)
+	{
+	  Shape *nSrc = chgt.rSrc;
+	  int nBrd = chgt.rBrd;
+	  while (nSrc->swsData[nBrd].rightRnd >=
+		 lastChgtPt /*&& nSrc->swsData[nBrd].doneTo < lastChgtPt */ )
+	    {
+	      Avance (lastPointNo, lastChgtPt, nSrc, nBrd, a, b, mod);
+
+	      SweepTree *node =
+		static_cast < SweepTree * >(nSrc->swsData[nBrd].misc);
+	      if (node == nullptr)
+		break;
+	      node = static_cast < SweepTree * >(node->elem[RIGHT]);
+	      if (node == nullptr)
+		break;
+	      nSrc = node->src;
+	      nBrd = node->bord;
+	    }
+	}
+    }
+}
+
+void
+Shape::Avance (int lastPointNo, int lastChgtPt, Shape * lS, int lB, Shape * /*a*/,
+	       Shape * b, BooleanOp mod)
+{
+  double dd = HalfRound (1);
+  bool avoidDiag = false;
+//      if ( lastChgtPt > 0 && pts[lastChgtPt-1].y+dd == pts[lastChgtPt].y ) avoidDiag=true;
+
+  bool direct = true;
+  if (lS == b && (mod == bool_op_diff || mod == bool_op_symdiff))
+    direct = false;
+  int lftN = lS->swsData[lB].leftRnd;
+  int rgtN = lS->swsData[lB].rightRnd;
+  if (lS->swsData[lB].doneTo < lastChgtPt)
+    {
+      int lp = lS->swsData[lB].curPoint;
+      if (lp >= 0 && getPoint(lp).x[1] + dd == getPoint(lastChgtPt).x[1])
+	avoidDiag = true;
+      if (lS->eData[lB].rdx[1] == 0)
+	{
+	  // tjs de gauche a droite et pas de diagonale
+	  if (lS->eData[lB].rdx[0] >= 0)
+	    {
+	      for (int p = lftN; p <= rgtN; p++)
+		{
+		  DoEdgeTo (lS, lB, p, direct, true);
+		  lp = p;
+		}
+	    }
+	  else
+	    {
+	      for (int p = lftN; p <= rgtN; p++)
+		{
+		  DoEdgeTo (lS, lB, p, direct, false);
+		  lp = p;
+		}
+	    }
+	}
+      else if (lS->eData[lB].rdx[1] > 0)
+	{
+	  if (lS->eData[lB].rdx[0] >= 0)
+	    {
+
+	      for (int p = lftN; p <= rgtN; p++)
+		{
+		  if (avoidDiag && p == lftN && getPoint(lftN).x[0] == getPoint(lp).x[0] + dd)
+		    {
+		      if (lftN > 0 && lftN - 1 >= lastChgtPt
+			  && getPoint(lftN - 1).x[0] == getPoint(lp).x[0])
+			{
+			  DoEdgeTo (lS, lB, lftN - 1, direct, true);
+			  DoEdgeTo (lS, lB, lftN, direct, true);
+			}
+		      else
+			{
+			  DoEdgeTo (lS, lB, lftN, direct, true);
+			}
+		    }
+		  else
+		    {
+		      DoEdgeTo (lS, lB, p, direct, true);
+		    }
+		  lp = p;
+		}
+	    }
+	  else
+	    {
+
+	      for (int p = rgtN; p >= lftN; p--)
+		{
+		  if (avoidDiag && p == rgtN && getPoint(rgtN).x[0] == getPoint(lp).x[0] - dd)
+		    {
+		      if (rgtN < numberOfPoints() && rgtN + 1 < lastPointNo
+			  && getPoint(rgtN + 1).x[0] == getPoint(lp).x[0])
+			{
+			  DoEdgeTo (lS, lB, rgtN + 1, direct, true);
+			  DoEdgeTo (lS, lB, rgtN, direct, true);
+			}
+		      else
+			{
+			  DoEdgeTo (lS, lB, rgtN, direct, true);
+			}
+		    }
+		  else
+		    {
+		      DoEdgeTo (lS, lB, p, direct, true);
+		    }
+		  lp = p;
+		}
+	    }
+	}
+      else
+	{
+	  if (lS->eData[lB].rdx[0] >= 0)
+	    {
+
+	      for (int p = rgtN; p >= lftN; p--)
+		{
+		  if (avoidDiag && p == rgtN && getPoint(rgtN).x[0] == getPoint(lp).x[0] - dd)
+		    {
+		      if (rgtN < numberOfPoints() && rgtN + 1 < lastPointNo
+			  && getPoint(rgtN + 1).x[0] == getPoint(lp).x[0])
+			{
+			  DoEdgeTo (lS, lB, rgtN + 1, direct, false);
+			  DoEdgeTo (lS, lB, rgtN, direct, false);
+			}
+		      else
+			{
+			  DoEdgeTo (lS, lB, rgtN, direct, false);
+			}
+		    }
+		  else
+		    {
+		      DoEdgeTo (lS, lB, p, direct, false);
+		    }
+		  lp = p;
+		}
+	    }
+	  else
+	    {
+
+	      for (int p = lftN; p <= rgtN; p++)
+		{
+		  if (avoidDiag && p == lftN && getPoint(lftN).x[0] == getPoint(lp).x[0] + dd)
+		    {
+		      if (lftN > 0 && lftN - 1 >= lastChgtPt
+			  && getPoint(lftN - 1).x[0] == getPoint(lp).x[0])
+			{
+			  DoEdgeTo (lS, lB, lftN - 1, direct, false);
+			  DoEdgeTo (lS, lB, lftN, direct, false);
+			}
+		      else
+			{
+			  DoEdgeTo (lS, lB, lftN, direct, false);
+			}
+		    }
+		  else
+		    {
+		      DoEdgeTo (lS, lB, p, direct, false);
+		    }
+		  lp = p;
+		}
+	    }
+	}
+      lS->swsData[lB].curPoint = lp;
+    }
+  lS->swsData[lB].doneTo = lastPointNo - 1;
+}
+
+void
+Shape::DoEdgeTo (Shape * iS, int iB, int iTo, bool direct, bool sens)
+{
+  int lp = iS->swsData[iB].curPoint;
+  int ne = -1;
+  if (sens)
+    {
+      if (direct)
+	ne = AddEdge (lp, iTo);
+      else
+	ne = AddEdge (iTo, lp);
+    }
+  else
+    {
+      if (direct)
+	ne = AddEdge (iTo, lp);
+      else
+	ne = AddEdge (lp, iTo);
+    }
+  if (ne >= 0 && _has_back_data)
+    {
+      ebData[ne].pathID = iS->ebData[iB].pathID;
+      ebData[ne].pieceID = iS->ebData[iB].pieceID;
+      if (iS->eData[iB].length < 0.00001)
+	{
+	  ebData[ne].tSt = ebData[ne].tEn = iS->ebData[iB].tSt;
+	}
+      else
+	{
+	  double bdl = iS->eData[iB].ilength;
+    Geom::Point bpx = iS->pData[iS->getEdge(iB).st].rx;
+	  Geom::Point bdx = iS->eData[iB].rdx;
+	  Geom::Point psx = getPoint(getEdge(ne).st).x;
+	  Geom::Point pex = getPoint(getEdge(ne).en).x;
+        Geom::Point psbx=psx-bpx;
+        Geom::Point pebx=pex-bpx;
+	  double pst = dot(psbx,bdx) * bdl;
+	  double pet = dot(pebx,bdx) * bdl;
+	  pst = iS->ebData[iB].tSt * (1 - pst) + iS->ebData[iB].tEn * pst;
+	  pet = iS->ebData[iB].tSt * (1 - pet) + iS->ebData[iB].tEn * pet;
+	  ebData[ne].tEn = pet;
+	  ebData[ne].tSt = pst;
+	}
+    }
+  iS->swsData[iB].curPoint = iTo;
+  if (ne >= 0)
+    {
+      int cp = iS->swsData[iB].firstLinkedPoint;
+      swsData[ne].firstLinkedPoint = iS->swsData[iB].firstLinkedPoint;
+      while (cp >= 0)
+	{
+	  pData[cp].askForWindingB = ne;
+	  cp = pData[cp].nextLinkedPoint;
+	}
+      iS->swsData[iB].firstLinkedPoint = -1;
+    }
+}