Inkscape

ShapeSweep.cpp

Go to the documentation of this file.

/*
 *  ShapeSweep.cpp
 *  nlivarot
 *
 *  Created by fred on Thu Jun 19 2003.
 *
 */

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <glib/gmem.h>
#include "Shape.h"
#include "livarot/sweep-event-queue.h"
#include "livarot/sweep-tree-list.h"
#include "livarot/sweep-tree.h"

#include "libnr/nr-matrix.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 (void)
{
  MakePointData (true);
  MakeEdgeData (true);
  MakeSweepSrcData (true);
}

void
Shape::CleanupSweep (void)
{
  MakePointData (false);
  MakeEdgeData (false);
  MakeSweepSrcData (false);
}

void
Shape::ForceToPolygon (void)
{
  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, NULL, 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 == NULL) {
    sTree = new SweepTreeList(a->numberOfEdges());
    }
    if (sEvts == NULL) {
    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 = NULL;

    clearIncidenceData();
    
    int curAPt = 0;

    while (curAPt < a->numberOfPoints() || sEvts->size() > 0) {
    NR::Point ptX;
      double ptL, ptR;
      SweepTree *intersL = NULL;
      SweepTree *intersR = NULL;
      int nPt = -1;
      Shape *ptSh = NULL;
      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;
    }

      NR::Point rPtX;
      rPtX[0]= Round (ptX[0]);
      rPtX[1]= Round (ptX[1]);
      int lastPointNo = -1;
      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 (unsigned int i = 0; i < chgts.size(); i++)
        {
          chgts[i].ptNo = pData[chgts[i].ptNo].newInd;
          if (chgts[i].type == 0)
        {
          if (chgts[i].src->getEdge(chgts[i].bord).st <
              chgts[i].src->getEdge(chgts[i].bord).en)
            {
              chgts[i].src->swsData[chgts[i].bord].stPt =
            chgts[i].ptNo;
            }
          else
            {
              chgts[i].src->swsData[chgts[i].bord].enPt =
            chgts[i].ptNo;
            }
        }
          else if (chgts[i].type == 1)
        {
          if (chgts[i].src->getEdge(chgts[i].bord).st >
              chgts[i].src->getEdge(chgts[i].bord).en)
            {
              chgts[i].src->swsData[chgts[i].bord].stPt =
            chgts[i].ptNo;
            }
          else
            {
              chgts[i].src->swsData[chgts[i].bord].enPt =
            chgts[i].ptNo;
            }
        }
        }

      CheckAdjacencies (lastI, lastChgtPt, shapeHead, edgeHead);

      CheckEdges (lastI, lastChgtPt, a, NULL, 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 = NULL;
    }


      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 == NULL)
        {
          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 == NULL)
                {
                }
              else
                {
                  AddChgt (lastPointNo, lastChgtPt, shapeHead,
                       edgeHead, EDGE_REMOVED, node->src, node->bord,
                       NULL, -1);
                  ptSh->swsData[cb].misc = NULL;

                  int onLeftB = -1, onRightB = -1;
                  Shape *onLeftS = NULL;
                  Shape *onRightS = NULL;
                  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 = NULL;
      if (dnNo >= 0)
        {
          if (upNo >= 0)
        {
          SweepTree *node = (SweepTree *) ptSh->swsData[upNo].misc;

          AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, EDGE_REMOVED,
               node->src, node->bord, NULL, -1);

          ptSh->swsData[upNo].misc = NULL;

          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, NULL, -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, NULL, -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, NULL,
                   -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 (unsigned int i = 0; i < chgts.size(); i++)
      {
    chgts[i].ptNo = pData[chgts[i].ptNo].newInd;
    if (chgts[i].type == 0)
      {
        if (chgts[i].src->getEdge(chgts[i].bord).st <
        chgts[i].src->getEdge(chgts[i].bord).en)
          {
        chgts[i].src->swsData[chgts[i].bord].stPt = chgts[i].ptNo;
          }
        else
          {
        chgts[i].src->swsData[chgts[i].bord].enPt = chgts[i].ptNo;
          }
      }
    else if (chgts[i].type == 1)
      {
        if (chgts[i].src->getEdge(chgts[i].bord).st >
        chgts[i].src->getEdge(chgts[i].bord).en)
          {
        chgts[i].src->swsData[chgts[i].bord].stPt = chgts[i].ptNo;
          }
        else
          {
        chgts[i].src->swsData[chgts[i].bord].enPt = chgts[i].ptNo;
          }
      }
      }

    CheckAdjacencies (lastI, lastChgtPt, shapeHead, edgeHead);

    CheckEdges (lastI, lastChgtPt, a, NULL, 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 = NULL;
  }

    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 = NULL;
  delete sEvts;
  sEvts = NULL;

  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 == NULL || b == NULL)
    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 == NULL) {
      sTree = new SweepTreeList(a->numberOfEdges() + b->numberOfEdges());
  }
  if (sEvts == NULL) {
      sEvts = new SweepEventQueue(a->numberOfEdges() + b->numberOfEdges());
  }
  
  MakePointData (true);
  MakeEdgeData (true);
  MakeSweepSrcData (true);
  MakeSweepDestData (true);
  if (a->hasBackData () && b->hasBackData ())
    {
      MakeBackData (true);
    }
  else
    {