src/livarot/sweep-event.cpp

   1 #include <glib/gmem.h>
   2 #include "livarot/sweep-event-queue.h"
   3 #include "livarot/sweep-tree.h"
   4 #include "livarot/sweep-event.h"
   5 #include "livarot/Shape.h"
   6
   7 SweepEventQueue::SweepEventQueue(int s) : nbEvt(0), maxEvt(s)
   8 {
   9     /* FIXME: use new[] for this, but this causes problems when delete[]
  10     ** calls the SweepEvent destructors.
  11     */
  12     events = (SweepEvent *) g_malloc(maxEvt * sizeof(SweepEvent));
  13     inds = new int[maxEvt];
  14 }
  15
  16 SweepEventQueue::~SweepEventQueue()
  17 {
  18     g_free(events);
  19     delete []inds;
  20 }
  21
  22 SweepEvent *SweepEventQueue::add(SweepTree *iLeft, SweepTree *iRight, Geom::Point &px, double itl, double itr)
  23 {
  24     if (nbEvt > maxEvt) {
  25         return NULL;
  26     }
  27
  28     int const n = nbEvt++;
  29     events[n].MakeNew (iLeft, iRight, px, itl, itr);
  30
  31     SweepTree *t[2] = { iLeft, iRight };
  32     for (int i = 0; i < 2; i++) {
  33         Shape *s = t[i]->src;
  34         Shape::dg_arete const &e = s->getEdge(t[i]->bord);
  35         int const n = std::max(e.st, e.en);
  36         s->pData[n].pending++;;
  37     }
  38
  39     events[n].ind = n;
  40     inds[n] = n;
  41
  42     int curInd = n;
  43     while (curInd > 0) {
  44         int const half = (curInd - 1) / 2;
  45         int const no = inds[half];
  46         if (px[1] < events[no].posx[1]
  47             || (px[1] == events[no].posx[1] && px[0] < events[no].posx[0]))
  48         {
  49             events[n].ind = half;
  50             events[no].ind = curInd;
  51             inds[half] = n;
  52             inds[curInd] = no;
  53         } else {
  54             break;
  55         }
  56
  57         curInd = half;
  58     }
  59
  60     return events + n;
  61 }
  62
  63
  64
  65 bool SweepEventQueue::peek(SweepTree * &iLeft, SweepTree * &iRight, Geom::Point &px, double &itl, double &itr)
  66 {
  67     if (nbEvt <= 0) {
  68         return false;
  69     }
  70
  71     SweepEvent const &e = events[inds[0]];
  72
  73     iLeft = e.sweep[LEFT];
  74     iRight = e.sweep[RIGHT];
  75     px = e.posx;
  76     itl = e.tl;
  77     itr = e.tr;
  78
  79     return true;
  80 }
  81
  82 bool SweepEventQueue::extract(SweepTree * &iLeft, SweepTree * &iRight, Geom::Point &px, double &itl, double &itr)
  83 {
  84     if (nbEvt <= 0) {
  85         return false;
  86     }
  87
  88     SweepEvent &e = events[inds[0]];
  89
  90     iLeft = e.sweep[LEFT];
  91     iRight = e.sweep[RIGHT];
  92     px = e.posx;
  93     itl = e.tl;
  94     itr = e.tr;
  95     remove(&e);
  96
  97     return true;
  98 }
  99
 100
 101 void SweepEventQueue::remove(SweepEvent *e)
 102 {
 103     if (nbEvt <= 1) {
 104         e->MakeDelete ();
 105         nbEvt = 0;
 106         return;
 107     }
 108
 109     int const n = e->ind;
 110     int to = inds[n];
 111     e->MakeDelete();
 112     relocate(&events[--nbEvt], to);
 113
 114     int const moveInd = nbEvt;
 115     if (moveInd == n) {
 116         return;
 117     }
 118
 119     to = inds[moveInd];
 120
 121     events[to].ind = n;
 122     inds[n] = to;
 123
 124     int curInd = n;
 125     Geom::Point const px = events[to].posx;
 126     bool didClimb = false;
 127     while (curInd > 0) {
 128         int const half = (curInd - 1) / 2;
 129         int const no = inds[half];
 130         if (px[1] < events[no].posx[1]
 131             || (px[1] == events[no].posx[1] && px[0] < events[no].posx[0]))
 132         {
 133           events[to].ind = half;
 134           events[no].ind = curInd;
 135           inds[half] = to;
 136           inds[curInd] = no;
 137           didClimb = true;
 138         } else {
 139             break;
 140         }
 141         curInd = half;
 142     }
 143
 144     if (didClimb) {
 145         return;
 146     }
 147
 148     while (2 * curInd + 1 < nbEvt) {
 149         int const son1 = 2 * curInd + 1;
 150         int const son2 = son1 + 1;
 151         int const no1 = inds[son1];
 152         int const no2 = inds[son2];
 153         if (son2 < nbEvt) {
 154             if (px[1] > events[no1].posx[1]
 155                 || (px[1] == events[no1].posx[1]
 156                     && px[0] > events[no1].posx[0]))
 157             {
 158                 if (events[no2].posx[1] > events[no1].posx[1]
 159                     || (events[no2].posx[1] == events[no1].posx[1]
 160                         && events[no2].posx[0] > events[no1].posx[0]))
 161                 {
 162                     events[to].ind = son1;
 163                     events[no1].ind = curInd;
 164                     inds[son1] = to;
 165                     inds[curInd] = no1;
 166                     curInd = son1;
 167                 } else {
 168                     events[to].ind = son2;
 169                     events[no2].ind = curInd;
 170                     inds[son2] = to;
 171                     inds[curInd] = no2;
 172                     curInd = son2;
 173                 }
 174             } else {
 175                 if (px[1] > events[no2].posx[1]
 176                     || (px[1] == events[no2].posx[1]
 177                         && px[0] > events[no2].posx[0]))
 178                 {
 179                     events[to].ind = son2;
 180                     events[no2].ind = curInd;
 181                     inds[son2] = to;
 182                     inds[curInd] = no2;
 183                     curInd = son2;
 184                 } else {
 185                     break;
 186                 }
 187             }
 188         } else {
 189             if (px[1] > events[no1].posx[1]
 190                 || (px[1] == events[no1].posx[1]
 191                     && px[0] > events[no1].posx[0]))
 192             {
 193                 events[to].ind = son1;
 194                 events[no1].ind = curInd;
 195                 inds[son1] = to;
 196                 inds[curInd] = no1;
 197             }
 198
 199             break;
 200         }
 201     }
 202 }
 203
 204
 205
 206
 207 void SweepEventQueue::relocate(SweepEvent *e, int to)
 208 {
 209     if (inds[e->ind] == to) {
 210         return;                 // j'y suis deja
 211     }
 212
 213     events[to] = *e;
 214
 215     e->sweep[LEFT]->evt[RIGHT] = events + to;
 216     e->sweep[RIGHT]->evt[LEFT] = events + to;
 217     inds[e->ind] = to;
 218 }
 219
 220
 221 /*
 222  * a simple binary heap
 223  * it only contains intersection events
 224  * the regular benley-ottman stuffs the segment ends in it too, but that not needed here since theses points
 225  * are already sorted. and the binary heap is much faster with only intersections...
 226  * the code sample on which this code is based comes from purists.org
 227  */
 228 SweepEvent::SweepEvent()
 229 {
 230     MakeNew (NULL, NULL, Geom::Point(0, 0), 0, 0);
 231 }
 232
 233 SweepEvent::~SweepEvent()
 234 {
 235     MakeDelete();
 236 }
 237
 238 void SweepEvent::MakeNew(SweepTree *iLeft, SweepTree *iRight, Geom::Point const &px, double itl, double itr)
 239 {
 240     ind = -1;
 241     posx = px;
 242     tl = itl;
 243     tr = itr;
 244     sweep[LEFT] = iLeft;
 245     sweep[RIGHT] = iRight;
 246     sweep[LEFT]->evt[RIGHT] = this;
 247     sweep[RIGHT]->evt[LEFT] = this;
 248 }
 249
 250 void SweepEvent::MakeDelete()
 251 {
 252     for (int i = 0; i < 2; i++) {
 253         if (sweep[i]) {
 254             Shape *s = sweep[i]->src;
 255             Shape::dg_arete const &e = s->getEdge(sweep[i]->bord);
 256             int const n = std::max(e.st, e.en);
 257             s->pData[n].pending--;
 258         }
 259
 260         sweep[i]->evt[1 - i] = NULL;
 261         sweep[i] = NULL;
 262     }
 263 }
 264
 265
 266 /*
 267   Local Variables:
 268   mode:c++
 269   c-file-style:"stroustrup"
 270   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 271   indent-tabs-mode:nil
 272   fill-column:99
 273   End:
 274 */
 275 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :