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"
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 */
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 }
27 SweepTree::~SweepTree()
28 {
29 MakeDelete();
30 }
32 void
33 SweepTree::MakeNew(Shape *iSrc, int iBord, int iWeight, int iStartPoint)
34 {
35 AVLTree::MakeNew();
36 ConvertTo(iSrc, iBord, iWeight, iStartPoint);
37 }
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 }
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 }
71 AVLTree::MakeDelete();
72 }
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(NR::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 NR::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();
94 NR::Point diff;
95 diff = px - bOrig;
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 NR::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();
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 }
166 // only find a point's position
167 int
168 SweepTree::Find(NR::Point const &px, SweepTree * &insertL,
169 SweepTree * &insertR)
170 {
171 NR::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();
180 NR::Point diff;
181 diff = px - bOrig;
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 }
236 void
237 SweepTree::RemoveEvents(SweepEventQueue & queue)
238 {
239 RemoveEvent(queue, LEFT);
240 RemoveEvent(queue, RIGHT);
241 }
243 void SweepTree::RemoveEvent(SweepEventQueue &queue, Side s)
244 {
245 if (evt[s]) {
246 queue.remove(evt[s]);
247 evt[s] = NULL;
248 }
249 }
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 }
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);
289 if (insertion == found_exact) {
290 if (insertR) {
291 insertR->RemoveEvent(queue, LEFT);
292 }
293 if (insertL) {
294 insertL->RemoveEvent(queue, RIGHT);
295 }
297 } else if (insertion == found_between) {
298 insertR->RemoveEvent(queue, LEFT);
299 insertL->RemoveEvent(queue, RIGHT);
300 }
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 }
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
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 }
326 NR::Point fromP;
327 fromP = src->pData[fromPt].rx;
328 NR::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 }
339 NR::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 }
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]);
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]);
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 }
440 int insertion = found_between;
442 if (insertL == NULL) {
443 insertion = found_on_left;
444 }
445 if (insertR == NULL) {
446 insertion = found_on_right;
447 }
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 }
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 }
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 }
492 void
493 SweepTree::SwapWithRight(SweepTreeList &list, SweepEventQueue &queue)
494 {
495 SweepTree *tL = this;
496 SweepTree *tR = static_cast<SweepTree *>(elem[RIGHT]);
498 tL->src->swsData[tL->bord].misc = tR;
499 tR->src->swsData[tR->bord].misc = tL;
501 {
502 Shape *swap = tL->src;
503 tL->src = tR->src;
504 tR->src = swap;
505 }
506 {
507 int swap = tL->bord;
508 tL->bord = tR->bord;
509 tR->bord = swap;
510 }
511 {
512 int swap = tL->startPoint;
513 tL->startPoint = tR->startPoint;
514 tR->startPoint = swap;
515 }
516 //{double swap=tL->invDirLength;tL->invDirLength=tR->invDirLength;tR->invDirLength=swap;}
517 {
518 bool swap = tL->sens;
519 tL->sens = tR->sens;
520 tR->sens = swap;
521 }
522 }
524 void
525 SweepTree::Avance(Shape *dstPts, int curPoint, Shape *a, Shape *b)
526 {
527 return;
528 /* if ( curPoint != startPoint ) {
529 int nb=-1;
530 if ( sens ) {
531 // nb=dstPts->AddEdge(startPoint,curPoint);
532 } else {
533 // nb=dstPts->AddEdge(curPoint,startPoint);
534 }
535 if ( nb >= 0 ) {
536 dstPts->swsData[nb].misc=(void*)((src==b)?1:0);
537 int wp=waitingPoint;
538 dstPts->eData[nb].firstLinkedPoint=waitingPoint;
539 waitingPoint=-1;
540 while ( wp >= 0 ) {
541 dstPts->pData[wp].edgeOnLeft=nb;
542 wp=dstPts->pData[wp].nextLinkedPoint;
543 }
544 }
545 startPoint=curPoint;
546 }*/
547 }
549 /*
550 Local Variables:
551 mode:c++
552 c-file-style:"stroustrup"
553 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
554 indent-tabs-mode:nil
555 fill-column:99
556 End:
557 */
558 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :