src/livarot/sweep-tree.cpp

   1 #include "libnr/nr-point-fns.h"
   2 #include "livarot/sweep-event-queue.h"
   3 #include "livarot/sweep-tree-list.h"
   4 #include "livarot/sweep-tree.h"
   5 #include "livarot/sweep-event.h"
   6 #include "livarot/Shape.h"
   7
   8
   9 /*
  10  * the AVL tree holding the edges intersecting the sweepline
  11  * that structure is very sensitive to anything
  12  * you have edges stored in nodes, the nodes are sorted in increasing x-order of intersection
  13  * with the sweepline, you have the 2 potential intersections of the edge in the node with its
  14  * neighbours, plus the fact that it's stored in an array that's realloc'd
  15  */
  16
  17 SweepTree::SweepTree()
  18 {
  19     src = NULL;
  20     bord = -1;
  21     startPoint = -1;
  22     evt[LEFT] = evt[RIGHT] = NULL;
  23     sens = true;
  24     //invDirLength=1;
  25 }
  26
  27 SweepTree::~SweepTree()
  28 {
  29     MakeDelete();
  30 }
  31
  32 void
  33 SweepTree::MakeNew(Shape *iSrc, int iBord, int iWeight, int iStartPoint)
  34 {
  35     AVLTree::MakeNew();
  36     ConvertTo(iSrc, iBord, iWeight, iStartPoint);
  37 }
  38
  39 void
  40 SweepTree::ConvertTo(Shape *iSrc, int iBord, int iWeight, int iStartPoint)
  41 {
  42     src = iSrc;
  43     bord = iBord;
  44     evt[LEFT] = evt[RIGHT] = NULL;
  45     startPoint = iStartPoint;
  46     if (src->getEdge(bord).st < src->getEdge(bord).en) {
  47         if (iWeight >= 0)
  48             sens = true;
  49         else
  50             sens = false;
  51     } else {
  52         if (iWeight >= 0)
  53             sens = false;
  54         else
  55             sens = true;
  56     }
  57     //invDirLength=src->eData[bord].isqlength;
  58     //invDirLength=1/sqrt(src->getEdge(bord).dx*src->getEdge(bord).dx+src->getEdge(bord).dy*src->getEdge(bord).dy);
  59 }
  60
  61
  62 void SweepTree::MakeDelete()
  63 {
  64     for (int i = 0; i < 2; i++) {
  65         if (evt[i]) {
  66             evt[i]->sweep[1 - i] = NULL;
  67         }
  68         evt[i] = NULL;
  69     }
  70
  71     AVLTree::MakeDelete();
  72 }
  73
  74
  75 // find the position at which node "newOne" should be inserted in the subtree rooted here
  76 // we want to order with respect to the order of intersections with the sweepline, currently
  77 // lying at y=px[1].
  78 // px is the upper endpoint of newOne
  79 int
  80 SweepTree::Find(Geom::Point const &px, SweepTree *newOne, SweepTree *&insertL,
  81                 SweepTree *&insertR, bool sweepSens)
  82 {
  83     // get the edge associated with this node: one point+one direction
  84     // since we're dealing with line, the direction (bNorm) is taken downwards
  85     Geom::Point bOrig, bNorm;
  86     bOrig = src->pData[src->getEdge(bord).st].rx;
  87     bNorm = src->eData[bord].rdx;
  88     if (src->getEdge(bord).st > src->getEdge(bord).en) {
  89         bNorm = -bNorm;
  90     }
  91     // rotate to get the normal to the edge
  92     bNorm=bNorm.ccw();
  93
  94     Geom::Point diff;
  95     diff = px - bOrig;
  96
  97     // compute (px-orig)^dir to know on which side of this edge the point px lies
  98     double y = 0;
  99     //if ( startPoint == newOne->startPoint ) {
 100     //   y=0;
 101     //} else {
 102     y = dot(bNorm, diff);
 103     //}
 104     //y*=invDirLength;
 105     if (fabs(y) < 0.000001) {
 106         // that damn point px lies on me, so i need to consider to direction of the edge in
 107         // newOne to know if it goes toward my left side or my right side
 108         // sweepSens is needed (actually only used by the Scan() functions) because if the sweepline goes upward,
 109         // signs change
 110         // prendre en compte les directions
 111         Geom::Point nNorm;
 112         nNorm = newOne->src->eData[newOne->bord].rdx;
 113         if (newOne->src->getEdge(newOne->bord).st >
 114             newOne->src->getEdge(newOne->bord).en)
 115         {
 116             nNorm = -nNorm;
 117         }
 118         nNorm=nNorm.ccw();
 119
 120         if (sweepSens) {
 121             y = cross(nNorm, bNorm);
 122         } else {
 123             y = cross(bNorm, nNorm);
 124         }
 125         if (y == 0) {
 126             y = dot(bNorm, nNorm);
 127             if (y == 0) {
 128                 insertL = this;
 129                 insertR = static_cast<SweepTree *>(elem[RIGHT]);
 130                 return found_exact;
 131             }
 132         }
 133     }
 134     if (y < 0) {
 135         if (son[LEFT]) {
 136             return (static_cast<SweepTree *>(son[LEFT]))->Find(px, newOne,
 137                                                                insertL, insertR,
 138                                                                sweepSens);
 139         } else {
 140             insertR = this;
 141             insertL = static_cast<SweepTree *>(elem[LEFT]);
 142             if (insertL) {
 143                 return found_between;
 144             } else {
 145                 return found_on_left;
 146             }
 147         }
 148     } else {
 149         if (son[RIGHT]) {
 150             return (static_cast<SweepTree *>(son[RIGHT]))->Find(px, newOne,
 151                                                                 insertL, insertR,
 152                                                                 sweepSens);
 153         } else {
 154             insertL = this;
 155             insertR = static_cast<SweepTree *>(elem[RIGHT]);
 156             if (insertR) {
 157                 return found_between;
 158             } else {
 159                 return found_on_right;
 160             }
 161         }
 162     }
 163     return not_found;
 164 }
 165
 166 // only find a point's position
 167 int
 168 SweepTree::Find(Geom::Point const &px, SweepTree * &insertL,
 169                  SweepTree * &insertR)
 170 {
 171   Geom::Point bOrig, bNorm;
 172   bOrig = src->pData[src->getEdge(bord).st].rx;
 173   bNorm = src->eData[bord].rdx;
 174   if (src->getEdge(bord).st > src->getEdge(bord).en)
 175     {
 176       bNorm = -bNorm;
 177     }
 178  bNorm=bNorm.ccw();
 179
 180   Geom::Point diff;
 181   diff = px - bOrig;
 182
 183   double y = 0;
 184   y = dot(bNorm, diff);
 185   if (y == 0)
 186     {
 187       insertL = this;
 188       insertR = static_cast<SweepTree *>(elem[RIGHT]);
 189       return found_exact;
 190     }
 191   if (y < 0)
 192     {
 193       if (son[LEFT])
 194         {
 195           return (static_cast<SweepTree *>(son[LEFT]))->Find(px, insertL,
 196                                                             insertR);
 197         }
 198       else
 199         {
 200           insertR = this;
 201           insertL = static_cast<SweepTree *>(elem[LEFT]);
 202           if (insertL)
 203             {
 204               return found_between;
 205             }
 206           else
 207             {
 208               return found_on_left;
 209             }
 210         }
 211     }
 212   else
 213     {
 214       if (son[RIGHT])
 215         {
 216           return (static_cast<SweepTree *>(son[RIGHT]))->Find(px, insertL,
 217                                                             insertR);
 218         }
 219       else
 220         {
 221           insertL = this;
 222           insertR = static_cast<SweepTree *>(elem[RIGHT]);
 223           if (insertR)
 224             {
 225               return found_between;
 226             }
 227           else
 228             {
 229               return found_on_right;
 230             }
 231         }
 232     }
 233   return not_found;
 234 }
 235
 236 void
 237 SweepTree::RemoveEvents(SweepEventQueue & queue)
 238 {
 239     RemoveEvent(queue, LEFT);
 240     RemoveEvent(queue, RIGHT);
 241 }
 242
 243 void SweepTree::RemoveEvent(SweepEventQueue &queue, Side s)
 244 {
 245     if (evt[s]) {
 246         queue.remove(evt[s]);
 247         evt[s] = NULL;
 248     }
 249 }
 250
 251 int
 252 SweepTree::Remove(SweepTreeList &list, SweepEventQueue &queue,
 253                   bool rebalance)
 254 {
 255   RemoveEvents(queue);
 256   AVLTree *tempR = static_cast<AVLTree *>(list.racine);
 257   int err = AVLTree::Remove(tempR, rebalance);
 258   list.racine = static_cast<SweepTree *>(tempR);
 259   MakeDelete();
 260   if (list.nbTree <= 1)
 261     {
 262       list.nbTree = 0;
 263       list.racine = NULL;
 264     }
 265   else
 266     {
 267       if (list.racine == list.trees + (list.nbTree - 1))
 268         list.racine = this;
 269       list.trees[--list.nbTree].Relocate(this);
 270     }
 271   return err;
 272 }
 273
 274 int
 275 SweepTree::Insert(SweepTreeList &list, SweepEventQueue &queue,
 276                   Shape *iDst, int iAtPoint, bool rebalance, bool sweepSens)
 277 {
 278   if (list.racine == NULL)
 279     {
 280       list.racine = this;
 281       return avl_no_err;
 282     }
 283   SweepTree *insertL = NULL;
 284   SweepTree *insertR = NULL;
 285   int insertion =
 286     list.racine->Find(iDst->getPoint(iAtPoint).x, this,
 287                        insertL, insertR, sweepSens);
 288
 289     if (insertion == found_exact) {
 290         if (insertR) {
 291             insertR->RemoveEvent(queue, LEFT);
 292         }
 293         if (insertL) {
 294             insertL->RemoveEvent(queue, RIGHT);
 295         }
 296
 297     } else if (insertion == found_between) {
 298       insertR->RemoveEvent(queue, LEFT);
 299       insertL->RemoveEvent(queue, RIGHT);
 300     }
 301
 302   AVLTree *tempR = static_cast<AVLTree *>(list.racine);
 303   int err =
 304     AVLTree::Insert(tempR, insertion, static_cast<AVLTree *>(insertL),
 305                      static_cast<AVLTree *>(insertR), rebalance);
 306   list.racine = static_cast<SweepTree *>(tempR);
 307   return err;
 308 }
 309
 310 // insertAt() is a speedup on the regular sweepline: if the polygon contains a point of high degree, you
 311 // get a set of edge that are to be added in the same position. thus you insert one edge with a regular insert(),
 312 // and then insert all the other in a doubly-linked list fashion. this avoids the Find() call, but is O(d^2) worst-case
 313 // where d is the number of edge to add in this fashion. hopefully d remains small
 314
 315 int
 316 SweepTree::InsertAt(SweepTreeList &list, SweepEventQueue &queue,
 317                     Shape */*iDst*/, SweepTree *insNode, int fromPt,
 318                     bool rebalance, bool sweepSens)
 319 {
 320   if (list.racine == NULL)
 321     {
 322       list.racine = this;
 323       return avl_no_err;
 324     }
 325
 326   Geom::Point fromP;
 327   fromP = src->pData[fromPt].rx;
 328   Geom::Point nNorm;
 329   nNorm = src->getEdge(bord).dx;
 330   if (src->getEdge(bord).st > src->getEdge(bord).en)
 331     {
 332       nNorm = -nNorm;
 333     }
 334   if (sweepSens == false)
 335     {
 336       nNorm = -nNorm;
 337     }
 338
 339   Geom::Point bNorm;
 340   bNorm = insNode->src->getEdge(insNode->bord).dx;
 341   if (insNode->src->getEdge(insNode->bord).st >
 342       insNode->src->getEdge(insNode->bord).en)
 343     {
 344       bNorm = -bNorm;
 345     }
 346
 347   SweepTree *insertL = NULL;
 348   SweepTree *insertR = NULL;
 349   double ang = cross(nNorm, bNorm);
 350   if (ang == 0)
 351     {
 352       insertL = insNode;
 353       insertR = static_cast<SweepTree *>(insNode->elem[RIGHT]);
 354     }
 355   else if (ang > 0)
 356     {
 357       insertL = insNode;
 358       insertR = static_cast<SweepTree *>(insNode->elem[RIGHT]);
 359
 360       while (insertL)
 361         {
 362           if (insertL->src == src)
 363             {
 364               if (insertL->src->getEdge(insertL->bord).st != fromPt
 365                   && insertL->src->getEdge(insertL->bord).en != fromPt)
 366                 {
 367                   break;
 368                 }
 369             }
 370           else
 371             {
 372               int ils = insertL->src->getEdge(insertL->bord).st;
 373               int ile = insertL->src->getEdge(insertL->bord).en;
 374               if ((insertL->src->pData[ils].rx[0] != fromP[0]
 375                    || insertL->src->pData[ils].rx[1] != fromP[1])
 376                   && (insertL->src->pData[ile].rx[0] != fromP[0]
 377                       || insertL->src->pData[ile].rx[1] != fromP[1]))
 378                 {
 379                   break;
 380                 }
 381             }
 382           bNorm = insertL->src->getEdge(insertL->bord).dx;
 383           if (insertL->src->getEdge(insertL->bord).st >
 384               insertL->src->getEdge(insertL->bord).en)
 385             {
 386               bNorm = -bNorm;
 387             }
 388           ang = cross(nNorm, bNorm);
 389           if (ang <= 0)
 390             {
 391               break;
 392             }
 393           insertR = insertL;
 394           insertL = static_cast<SweepTree *>(insertR->elem[LEFT]);
 395         }
 396     }
 397   else if (ang < 0)
 398     {
 399       insertL = insNode;
 400       insertR = static_cast<SweepTree *>(insNode->elem[RIGHT]);
 401
 402       while (insertR)
 403         {
 404           if (insertR->src == src)
 405             {
 406               if (insertR->src->getEdge(insertR->bord).st != fromPt
 407                   && insertR->src->getEdge(insertR->bord).en != fromPt)
 408                 {
 409                   break;
 410                 }
 411             }
 412           else
 413             {
 414               int ils = insertR->src->getEdge(insertR->bord).st;
 415               int ile = insertR->src->getEdge(insertR->bord).en;
 416               if ((insertR->src->pData[ils].rx[0] != fromP[0]
 417                    || insertR->src->pData[ils].rx[1] != fromP[1])
 418                   && (insertR->src->pData[ile].rx[0] != fromP[0]
 419                       || insertR->src->pData[ile].rx[1] != fromP[1]))
 420                 {
 421                   break;
 422                 }
 423             }
 424           bNorm = insertR->src->getEdge(insertR->bord).dx;
 425           if (insertR->src->getEdge(insertR->bord).st >
 426               insertR->src->getEdge(insertR->bord).en)
 427             {
 428               bNorm = -bNorm;
 429             }
 430           ang = cross(nNorm, bNorm);
 431           if (ang > 0)
 432             {
 433               break;
 434             }
 435           insertL = insertR;
 436           insertR = static_cast<SweepTree *>(insertL->elem[RIGHT]);
 437         }
 438     }
 439
 440   int insertion = found_between;
 441
 442   if (insertL == NULL) {
 443     insertion = found_on_left;
 444   }
 445   if (insertR == NULL) {
 446     insertion = found_on_right;
 447   }
 448
 449   if (insertion == found_exact) {
 450       /* FIXME: surely this can never be called? */
 451       if (insertR) {
 452           insertR->RemoveEvent(queue, LEFT);
 453       }
 454       if (insertL) {
 455           insertL->RemoveEvent(queue, RIGHT);
 456       }
 457   } else if (insertion == found_between) {
 458       insertR->RemoveEvent(queue, LEFT);
 459       insertL->RemoveEvent(queue, RIGHT);
 460   }
 461
 462   AVLTree *tempR = static_cast<AVLTree *>(list.racine);
 463   int err =
 464     AVLTree::Insert(tempR, insertion, static_cast<AVLTree *>(insertL),
 465                      static_cast<AVLTree *>(insertR), rebalance);
 466   list.racine = static_cast<SweepTree *>(tempR);
 467   return err;
 468 }
 469
 470 void
 471 SweepTree::Relocate(SweepTree * to)
 472 {
 473   if (this == to)
 474     return;
 475   AVLTree::Relocate(to);
 476   to->src = src;
 477   to->bord = bord;
 478   to->sens = sens;
 479   to->evt[LEFT] = evt[LEFT];
 480   to->evt[RIGHT] = evt[RIGHT];
 481   to->startPoint = startPoint;
 482   if (unsigned(bord) < src->swsData.size())
 483     src->swsData[bord].misc = to;
 484   if (unsigned(bord) < src->swrData.size())
 485     src->swrData[bord].misc = to;
 486   if (evt[LEFT])
 487     evt[LEFT]->sweep[RIGHT] = to;
 488   if (evt[RIGHT])
 489     evt[RIGHT]->sweep[LEFT] = to;
 490 }
 491
 492 // TODO check if ignoring these parameters is bad
 493 void
 494 SweepTree::SwapWithRight(SweepTreeList &/*list*/, SweepEventQueue &/*queue*/)
 495 {
 496     SweepTree *tL = this;
 497     SweepTree *tR = static_cast<SweepTree *>(elem[RIGHT]);
 498
 499     tL->src->swsData[tL->bord].misc = tR;
 500     tR->src->swsData[tR->bord].misc = tL;
 501
 502     {
 503         Shape *swap = tL->src;
 504         tL->src = tR->src;
 505         tR->src = swap;
 506     }
 507     {
 508         int swap = tL->bord;
 509         tL->bord = tR->bord;
 510         tR->bord = swap;
 511     }
 512     {
 513         int swap = tL->startPoint;
 514         tL->startPoint = tR->startPoint;
 515         tR->startPoint = swap;
 516     }
 517     //{double swap=tL->invDirLength;tL->invDirLength=tR->invDirLength;tR->invDirLength=swap;}
 518     {
 519         bool swap = tL->sens;
 520         tL->sens = tR->sens;
 521         tR->sens = swap;
 522     }
 523 }
 524
 525 void
 526 SweepTree::Avance(Shape */*dstPts*/, int /*curPoint*/, Shape */*a*/, Shape */*b*/)
 527 {
 528     return;
 529 /*      if ( curPoint != startPoint ) {
 530                 int nb=-1;
 531                 if ( sens ) {
 532 //                      nb=dstPts->AddEdge(startPoint,curPoint);
 533                 } else {
 534 //                      nb=dstPts->AddEdge(curPoint,startPoint);
 535                 }
 536                 if ( nb >= 0 ) {
 537                         dstPts->swsData[nb].misc=(void*)((src==b)?1:0);
 538                         int   wp=waitingPoint;
 539                         dstPts->eData[nb].firstLinkedPoint=waitingPoint;
 540                         waitingPoint=-1;
 541                         while ( wp >= 0 ) {
 542                                 dstPts->pData[wp].edgeOnLeft=nb;
 543                                 wp=dstPts->pData[wp].nextLinkedPoint;
 544                         }
 545                 }
 546                 startPoint=curPoint;
 547         }*/
 548 }
 549
 550 /*
 551   Local Variables:
 552   mode:c++
 553   c-file-style:"stroustrup"
 554   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 555   indent-tabs-mode:nil
 556   fill-column:99
 557   End:
 558 */
 559 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :