Logo Search packages:      
Sourcecode: inkscape version File versions

sweep-event.cpp

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

SweepEventQueue::SweepEventQueue(int s) : nbEvt(0), maxEvt(s)
{
    /* FIXME: use new[] for this, but this causes problems when delete[]
    ** calls the SweepEvent destructors.
    */
    events = (SweepEvent *) g_malloc(maxEvt * sizeof(SweepEvent));
    inds = new int[maxEvt];
}

SweepEventQueue::~SweepEventQueue()
{
    g_free(events);
    delete []inds;
}

00022 SweepEvent *SweepEventQueue::add(SweepTree *iLeft, SweepTree *iRight, NR::Point &px, double itl, double itr)
{
    if (nbEvt > maxEvt) {
      return NULL;
    }
    
    int const n = nbEvt++;
    events[n].MakeNew (iLeft, iRight, px, itl, itr);

    SweepTree *t[2] = { iLeft, iRight };
    for (int i = 0; i < 2; i++) {
        Shape *s = t[i]->src;
      Shape::dg_arete const &e = s->getEdge(t[i]->bord);
      int const n = std::max(e.st, e.en);
      s->pData[n].pending++;;
    }

    events[n].ind = n;
    inds[n] = n;

    int curInd = n;
    while (curInd > 0) {
      int const half = (curInd - 1) / 2;
      int const no = inds[half];
      if (px[1] < events[no].posx[1]
          || (px[1] == events[no].posx[1] && px[0] < events[no].posx[0]))
      {
          events[n].ind = half;
          events[no].ind = curInd;
          inds[half] = n;
          inds[curInd] = no;
      } else {
          break;
      }
      
      curInd = half;
    }
  
    return events + n;
}



00065 bool SweepEventQueue::peek(SweepTree * &iLeft, SweepTree * &iRight, NR::Point &px, double &itl, double &itr)
{
    if (nbEvt <= 0) {
      return false;
    }
    
    SweepEvent const &e = events[inds[0]];

    iLeft = e.sweep[LEFT];
    iRight = e.sweep[RIGHT];
    px = e.posx;
    itl = e.tl;
    itr = e.tr;
    
    return true;
}

00082 bool SweepEventQueue::extract(SweepTree * &iLeft, SweepTree * &iRight, NR::Point &px, double &itl, double &itr)
{
    if (nbEvt <= 0) {
      return false;
    }

    SweepEvent &e = events[inds[0]];
    
    iLeft = e.sweep[LEFT];
    iRight = e.sweep[RIGHT];
    px = e.posx;
    itl = e.tl;
    itr = e.tr;
    remove(&e);
    
    return true;
}


void SweepEventQueue::remove(SweepEvent *e)
{
    if (nbEvt <= 1) {
      e->MakeDelete ();
      nbEvt = 0;
      return;
    }
    
    int const n = e->ind;
    int to = inds[n];
    e->MakeDelete();
    relocate(&events[--nbEvt], to);

    int const moveInd = nbEvt;
    if (moveInd == n) {
      return;
    }
    
    to = inds[moveInd];

    events[to].ind = n;
    inds[n] = to;

    int curInd = n;
    NR::Point const px = events[to].posx;
    bool didClimb = false;
    while (curInd > 0) {
      int const half = (curInd - 1) / 2;
      int const no = inds[half];
      if (px[1] < events[no].posx[1]
          || (px[1] == events[no].posx[1] && px[0] < events[no].posx[0]))
      {
        events[to].ind = half;
        events[no].ind = curInd;
        inds[half] = to;
        inds[curInd] = no;
        didClimb = true;
      } else {
          break;
      }
      curInd = half;
    }
    
    if (didClimb) {
      return;
    }
    
    while (2 * curInd + 1 < nbEvt) {
      int const son1 = 2 * curInd + 1;
      int const son2 = son1 + 1;
      int const no1 = inds[son1];
      int const no2 = inds[son2];
      if (son2 < nbEvt) {
          if (px[1] > events[no1].posx[1]
            || (px[1] == events[no1].posx[1]
                && px[0] > events[no1].posx[0]))
          {
            if (events[no2].posx[1] > events[no1].posx[1]
                || (events[no2].posx[1] == events[no1].posx[1]
                  && events[no2].posx[0] > events[no1].posx[0]))
            {
                events[to].ind = son1;
                events[no1].ind = curInd;
                inds[son1] = to;
                inds[curInd] = no1;
                curInd = son1;
            } else {
                events[to].ind = son2;
                events[no2].ind = curInd;
                inds[son2] = to;
                inds[curInd] = no2;
                curInd = son2;
            }
          } else {
            if (px[1] > events[no2].posx[1]
                || (px[1] == events[no2].posx[1]
                  && px[0] > events[no2].posx[0]))
            {
                events[to].ind = son2;
                events[no2].ind = curInd;
                inds[son2] = to;
                inds[curInd] = no2;
                curInd = son2;
            } else {
                break;
            }
          }
      } else {
          if (px[1] > events[no1].posx[1]
            || (px[1] == events[no1].posx[1]
                && px[0] > events[no1].posx[0]))
          {
            events[to].ind = son1;
            events[no1].ind = curInd;
            inds[son1] = to;
            inds[curInd] = no1;
          }
          
          break;
      }
    }
}




void SweepEventQueue::relocate(SweepEvent *e, int to)
{
    if (inds[e->ind] == to) {
      return;                 // j'y suis deja
    }

    events[to] = *e;

    e->sweep[LEFT]->evt[RIGHT] = events + to;
    e->sweep[RIGHT]->evt[LEFT] = events + to;
    inds[e->ind] = to;
}


/*
 * a simple binary heap
 * it only contains intersection events
 * the regular benley-ottman stuffs the segment ends in it too, but that not needed here since theses points
 * are already sorted. and the binary heap is much faster with only intersections...
 * the code sample on which this code is based comes from purists.org
 */
SweepEvent::SweepEvent()
{
    MakeNew (NULL, NULL, NR::Point(0, 0), 0, 0);
}

SweepEvent::~SweepEvent()
{
    MakeDelete();
}

00238 void SweepEvent::MakeNew(SweepTree *iLeft, SweepTree *iRight, NR::Point const &px, double itl, double itr)
{
    ind = -1;
    posx = px;
    tl = itl;
    tr = itr;
    sweep[LEFT] = iLeft;
    sweep[RIGHT] = iRight;
    sweep[LEFT]->evt[RIGHT] = this;
    sweep[RIGHT]->evt[LEFT] = this;
}

00250 void SweepEvent::MakeDelete()
{
    for (int i = 0; i < 2; i++) {
      if (sweep[i]) {
          Shape *s = sweep[i]->src;
          Shape::dg_arete const &e = s->getEdge(sweep[i]->bord);
          int const n = std::max(e.st, e.en);
          s->pData[n].pending--;
      }

      sweep[i]->evt[1 - i] = NULL;
      sweep[i] = NULL;
    }
}


/*
  Local Variables:
  mode:c++
  c-file-style:"stroustrup"
  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
  indent-tabs-mode:nil
  fill-column:99
  End:
*/
// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :

Generated by  Doxygen 1.6.0   Back to index