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"
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 }
16 SweepEventQueue::~SweepEventQueue()
17 {
18 g_free(events);
19 delete []inds;
20 }
22 SweepEvent *SweepEventQueue::add(SweepTree *iLeft, SweepTree *iRight, NR::Point &px, double itl, double itr)
23 {
24 if (nbEvt > maxEvt) {
25 return NULL;
26 }
28 int const n = nbEvt++;
29 events[n].MakeNew (iLeft, iRight, px, itl, itr);
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 }
39 events[n].ind = n;
40 inds[n] = n;
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 }
57 curInd = half;
58 }
60 return events + n;
61 }
65 bool SweepEventQueue::peek(SweepTree * &iLeft, SweepTree * &iRight, NR::Point &px, double &itl, double &itr)
66 {
67 if (nbEvt <= 0) {
68 return false;
69 }
71 SweepEvent const &e = events[inds[0]];
73 iLeft = e.sweep[LEFT];
74 iRight = e.sweep[RIGHT];
75 px = e.posx;
76 itl = e.tl;
77 itr = e.tr;
79 return true;
80 }
82 bool SweepEventQueue::extract(SweepTree * &iLeft, SweepTree * &iRight, NR::Point &px, double &itl, double &itr)
83 {
84 if (nbEvt <= 0) {
85 return false;
86 }
88 SweepEvent &e = events[inds[0]];
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);
97 return true;
98 }
101 void SweepEventQueue::remove(SweepEvent *e)
102 {
103 if (nbEvt <= 1) {
104 e->MakeDelete ();
105 nbEvt = 0;
106 return;
107 }
109 int const n = e->ind;
110 int to = inds[n];
111 e->MakeDelete();
112 relocate(&events[--nbEvt], to);
114 int const moveInd = nbEvt;
115 if (moveInd == n) {
116 return;
117 }
119 to = inds[moveInd];
121 events[to].ind = n;
122 inds[n] = to;
124 int curInd = n;
125 NR::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 }
144 if (didClimb) {
145 return;
146 }
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 }
199 break;
200 }
201 }
202 }
207 void SweepEventQueue::relocate(SweepEvent *e, int to)
208 {
209 if (inds[e->ind] == to) {
210 return; // j'y suis deja
211 }
213 events[to] = *e;
215 e->sweep[LEFT]->evt[RIGHT] = events + to;
216 e->sweep[RIGHT]->evt[LEFT] = events + to;
217 inds[e->ind] = to;
218 }
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, NR::Point(0, 0), 0, 0);
231 }
233 SweepEvent::~SweepEvent()
234 {
235 MakeDelete();
236 }
238 void SweepEvent::MakeNew(SweepTree *iLeft, SweepTree *iRight, NR::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 }
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 }
260 sweep[i]->evt[1 - i] = NULL;
261 sweep[i] = NULL;
262 }
263 }
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 :