1 /*! \file kbool/src/scanbeam.cpp
2 \author Klaas Holwerda or Julian Smart
3
4 Copyright: 2001-2004 (C) Klaas Holwerda
5
6 Licence: see kboollicense.txt
7
8 RCS-ID: $Id: scanbeam.cpp,v 1.10 2005/06/17 23:05:18 kbluck Exp $
9 */
10
11 #ifdef __GNUG__
12 #pragma implementation
13 #endif
14
15 // class scanbeam
16 // this class represents de space between two scanlines
17 #include "kbool/include/scanbeam.h"
18 #include <math.h>
19 #include <assert.h>
20
21 #include "kbool/include/booleng.h"
22
23 #include "kbool/include/graph.h"
24 #include "kbool/include/node.h"
25
26 //this here is to initialize the static iterator of scanbeam
27 //with NOLIST constructor
28
29 int recordsorter(Record* , Record* );
30
31 int recordsorter_ysp_angle(Record* , Record* );
32 int recordsorter_ysp_angle_back(Record* rec1, Record* rec2);
33
ScanBeam(Bool_Engine * GC)34 ScanBeam::ScanBeam(Bool_Engine* GC):DL_List<Record*>()
35 {
36 _GC = GC;
37 _type=NORMAL;
38 _BI.Attach(this);
39 }
40
~ScanBeam()41 ScanBeam::~ScanBeam()
42 {
43 //first delete all record still in the beam
44 _BI.Detach();
45 remove_all( true );
46
47 //DeleteRecordPool();
48 }
49
SetType(Node * low,Node * high)50 void ScanBeam::SetType(Node* low,Node* high)
51 {
52 if (low->GetX() < high->GetX())
53 _type=NORMAL;
54 else
55 _type=FLAT;
56 }
57
58 /*
59 //catch node to link crossings
60 // must be sorted on ysp
61 int ScanBeam::FindCloseLinksAndCross(TDLI<KBoolLink>* _I,Node* _lowf)
62 {
63 int merges = 0;
64 Record* record;
65
66 TDLI<Record> _BBI=TDLI<Record>(this);
67
68 if (_BI.count() > 1)
69 {
70 //first search a link towards this node
71 for(_BI.tohead(); !_BI.hitroot(); _BI++)
72 {
73 record=_BI.item();
74 if( (record->GetLink()->GetBeginNode()==_lowf) ||
75 (record->GetLink()->GetEndNode() ==_lowf)
76 )
77 break;
78 }
79
80 //NOTICE if the node "a_node" is not inside a record
81 //for instance to connected flat links (flatlinks not in beam)
82 //then IL will be at end (those will be catched at 90 degrees rotation)
83 if (_BI.hitroot())
84 {
85 return(merges);
86 }
87
88 //from IL search back for close links
89 _BBI.toiter(&_BI);
90 _BBI--;
91 while(!_BBI.hitroot())
92 {
93 record=_BBI.item();
94
95 if (record->Ysp() != _lowf->GetY())
96 break;
97
98 // the distance to the low node is smaller then the MARGE
99 if( (record->GetLink()->GetBeginNode()!=_lowf) &&
100 (record->GetLink()->GetEndNode() !=_lowf)
101 )
102 { // the link is not towards the low node
103 record->GetLink()->AddCrossing(_lowf);
104 record->SetNewLink(record->GetLink()->ProcessCrossingsSmart(_I));
105 merges++;
106 }
107 _BBI--;
108 }
109
110 //from IL search forward for close links
111 _BBI.toiter(&_BI);
112 _BBI++;
113 while(!_BBI.hitroot())
114 {
115 record=_BBI.item();
116
117 if (record->Ysp() != _lowf->GetY())
118 // if (record->Ysp() < _lowf->GetY()-MARGE)
119 break;
120
121 // the distance to the low node is smaller then the MARGE
122 if( (record->GetLink()->GetBeginNode()!=_lowf) &&
123 (record->GetLink()->GetEndNode() !=_lowf)
124 )
125 { // the link is not towards the low node
126 record->GetLink()->AddCrossing(_lowf);
127 record->SetNewLink(record->GetLink()->ProcessCrossingsSmart(_I));
128 merges++;
129 }
130 _BBI++;
131 }
132 }
133 return merges;
134 }
135 */
136
137 /*
138 bool ScanBeam::Update(TDLI<KBoolLink>* _I,Node* _lowf)
139 {
140 bool found=false;
141 KBoolLink* link;
142
143 _BI.tohead();
144 while (!_BI.hitroot())
145 {
146
147 Record* record=_BI.item();
148 record->Calc_Ysp(_type,_low);
149 _BI++;
150 }
151
152 FindCloseLinksAndCross(_I,_lowf);
153
154 _BI.tohead();
155 while (!_BI.hitroot())
156 {
157 Record* record=_BI.item();
158 //records containing links towards the new low node
159 //are links to be marked for removal
160
161 if ((record->GetLink()->GetEndNode() == _lowf) ||
162 (record->GetLink()->GetBeginNode() == _lowf)
163 )
164 {
165 //cross here the links that meat eachother now
166 delete _BI.item();
167 _BI.remove();
168
169 //cross here the links that meat eachother now
170 _BI--;
171 if (!_BI.hitroot() && (_BI.count() > 1))
172 {
173 Record* prev=_BI.item();
174 _BI++;
175 if (!_BI.hitroot())
176 {
177 if (!_BI.item()->Equal(prev)) // records NOT parallel
178 if (_BI.item()->GetLine()->Intersect(prev->GetLine(),MARGE))
179 {
180 //they did cross, integrate the crossings in the graph
181 //this may modify the links already part of the record
182 //this is why they are returned in set for the record
183 _BI.item()->SetNewLink(_BI.item()->GetLink()->ProcessCrossingsSmart(_I));
184 prev->SetNewLink(prev->GetLink()->ProcessCrossingsSmart(_I));
185 }
186 }
187 }
188 else
189 _BI++;
190 }
191 else
192 _BI++;
193 }
194
195 //writebeam();
196
197 //ONLY links towards the low node are possible to be added
198 //the bin flag will be set if it fits in the beam
199 //so for following beams it will not be checked again
200 while ( bool(link=_lowf->GetBinHighest(false)) )
201 {
202 Record* record=new Record(link);
203 // yp_new will always be the y of low node since all new links are
204 // from this node
205 record->SetYsp(_lowf->GetY());
206 record->Set_Flags(_type);
207 //need to calculate ysn to be able to sort this record in the right order
208 //this is only used when the insert node is equal for both records
209 // ins_smart and cross neighbour directly
210 // if empty then just insert
211
212 if (empty())
213 insend(record);
214 else
215 {
216 // put new item left of the one that is bigger
217 _BI.tohead();
218 while(!_BI.hitroot())
219 {
220 if (recordsorter_ysp_angle(record,_BI.item())==1)
221 break;
222 _BI++;
223 }
224
225 _BI.insbefore(record);
226 _BI--;_BI--; //just before the new record inserted
227 if (!_BI.hitroot())
228 {
229 Record* prev=_BI.item();
230 _BI++; //goto the new record inserted
231 if (!_BI.item()->Equal(prev)) // records NOT parallel
232 {
233 if (_BI.item()->GetLine()->Intersect(prev->GetLine(),MARGE))
234 {
235 //this may modify the links already part of the record
236 //this is why they are returned in set for the record
237 _BI.item()->SetNewLink(_BI.item()->GetLink()->ProcessCrossingsSmart(_I));
238 prev->SetNewLink(prev->GetLink()->ProcessCrossingsSmart(_I));
239 }
240 }
241 }
242 else
243 _BI++;
244
245 Record* prev=_BI.item(); //the new record
246 _BI++;
247 if (!_BI.hitroot() && !_BI.item()->Equal(prev)) // records NOT parallel
248 {
249 Record* cur=_BI.item();
250 if (cur->GetLine()->Intersect(prev->GetLine(),MARGE))
251 {
252 //this may modify the links already part of the record
253 //this is why they are returned in set for the record
254 cur->SetNewLink(cur->GetLink()->ProcessCrossingsSmart(_I));
255 prev->SetNewLink(prev->GetLink()->ProcessCrossingsSmart(_I));
256 }
257 }
258 }
259 //remember this to calculate in/out values for each new link its polygon again.
260 GNI->insend(record->GetLink()->GetGraphNum());
261 found=true;
262 record->GetLink()->SetBeenHere();
263 }
264
265 FindCloseLinksAndCross(_I,_lowf);
266 //writebeam();
267 return(found);
268 }
269 */
270
FindNew(SCANTYPE scantype,TDLI<KBoolLink> * _I,bool & holes)271 bool ScanBeam::FindNew(SCANTYPE scantype,TDLI<KBoolLink>* _I, bool& holes )
272 {
273 bool foundnew = false;
274
275 _low = _I->item()->GetBeginNode();
276
277 KBoolLink* link;
278
279 //if (!checksort())
280 // SortTheBeam();
281
282 lastinserted=0;
283 //ONLY links towards the low node are possible to be added
284 //the bin flag will be set if it fits in the beam
285 //so for following beams it will not be checked again
286 while ( (link = _low->GetBinHighest(false)) != NULL )
287 {
288 if ( (link->GetEndNode()->GetX() == link->GetBeginNode()->GetX()) //flatlink in flatbeam
289 && ((scantype == NODELINK) || (scantype == LINKLINK) || (scantype == LINKHOLES))
290 )
291 {
292 switch(scantype)
293 {
294 case NODELINK:
295 {
296 //all vertical links in flatbeam are ignored
297 //normal link in beam
298 Record* record=new Record(link,_GC);
299 // yp_new will always be the y of low node since all new links are
300 // from this node
301 record->SetYsp(_low->GetY());
302 record->Set_Flags();
303 // put new item left of the one that is lower in the beam
304 // The last one inserted in this loop, is already left of the current
305 // iterator position. So the new links are inerted in proper order.
306 link->SetRecordNode( _BI.insbefore(record) );
307 _BI--;
308 foundnew = Process_PointToLink_Crossings() !=0 || foundnew;
309 delete record;
310 _BI.remove();
311 break;
312 }
313 case LINKLINK:
314 //is the new record a flat link
315 {
316 KBoolLine flatline = KBoolLine(link, _GC);
317 foundnew = Process_LinkToLink_Flat(&flatline) || foundnew;
318 //flatlinks are not part of the beams, still they are used to find new beams
319 //they can be processed now if the beginnode does not change, since this is used to
320 //to find new beams. and its position does not change
321 //ProcessCrossings does take care of this
322 flatline.ProcessCrossings(_I);
323 break;
324 }
325 case LINKHOLES : //holes are never to flatlinks
326 assert( true );
327 default:
328 break;
329 }
330 }
331 else
332 {
333 //normal link in beam
334 Record* record = new Record(link,_GC);
335 // yp_new will always be the y of low node since all new links are
336 // from this node
337 record->SetYsp(_low->GetY());
338 record->Set_Flags();
339 // put new item left of the one that is lower in the beam
340 // The last one inserted in this loop, is already left of the current
341 // iterator position. So the new links are inserted in proper order.
342 link->SetRecordNode( _BI.insbefore(record) );
343 lastinserted++;
344
345 //_GC->Write_Log( "after insert" );
346 writebeam();
347
348 switch(scantype)
349 {
350 case NODELINK:
351 _BI--;
352 foundnew = Process_PointToLink_Crossings() !=0 || foundnew;
353 _BI++;
354 break;
355 case INOUT:
356 {
357 _BI--;
358 //now we can set the _inc flag
359 Generate_INOUT(record->GetLink()->GetGraphNum());
360 _BI++;
361 }
362 break;
363 case GENLR:
364 {
365 //now we can set the a/b group flags based on the above link
366 _BI--;
367 _BI--;
368 Record* above=0;
369 if (!_BI.hitroot())
370 above=_BI.item();
371 _BI++;
372
373 //something to do for winding rule
374
375 if (record->Calc_Left_Right(above))
376 {
377 delete record;
378 _BI.remove();
379 lastinserted--;
380 }
381 else
382 _BI++;
383 }
384 break;
385 case LINKHOLES:
386 _BI--;
387 holes = ProcessHoles(true,_I) || holes;
388 _BI++;
389 break;
390
391 default:
392 break;
393 }
394 }
395 link->SetBeenHere();
396 }
397
398 writebeam();
399
400 return foundnew;
401 }
402
RemoveOld(SCANTYPE scantype,TDLI<KBoolLink> * _I,bool & holes)403 bool ScanBeam::RemoveOld(SCANTYPE scantype,TDLI<KBoolLink>* _I, bool& holes )
404 {
405 bool found = false;
406 bool foundnew = false;
407 DL_Iter<Record*> _BBI=DL_Iter<Record*>();
408 bool attached=false;
409
410 _low = _I->item()->GetBeginNode();
411
412 switch(scantype)
413 {
414 case INOUT:
415 case GENLR:
416 case LINKHOLES:
417 if (_type==NORMAL )
418 {
419 if (_low->GetBinHighest(true)) //is there something to remove
420 {
421 if ( scantype == LINKHOLES )
422 {
423 _BI.tohead();
424 while (!_BI.hitroot())
425 {
426 Record* record=_BI.item();
427 //records containing links towards the new low node
428 //are links to be removed
429 if ((record->GetLink()->GetEndNode() == _low) ||
430 (record->GetLink()->GetBeginNode() == _low)
431 )
432 {
433 holes = ProcessHoles(false,_I) || holes;
434 }
435 _BI++;
436 }
437 }
438
439 _BI.tohead();
440 while (!_BI.hitroot())
441 {
442 Record* record=_BI.item();
443 //records containing links towards the new low node
444 //are links to be removed
445 if ((record->GetLink()->GetEndNode() == _low) ||
446 (record->GetLink()->GetBeginNode() == _low)
447 )
448 {
449 if (attached) //there is a bug
450 {
451 _BBI.Detach();
452 if (!checksort())
453 SortTheBeam( true );
454 _BI.tohead();
455 attached=false;
456
457 }
458 delete _BI.item();
459 _BI.remove();
460 found=true;
461 }
462 else if (found) //only once in here
463 {
464 attached=true;
465 found=false;
466 _BBI.Attach(this);
467 _BBI.toiter(&_BI); //this is the position new records will be inserted
468
469 //recalculate ysp for the new scanline
470 record->Calc_Ysp(_low);
471 _BI++;
472 }
473 else
474 {
475 //recalculate ysp for the new scanline
476 record->Calc_Ysp(_low);
477 _BI++;
478 }
479 }
480
481 if (attached)
482 {
483 _BI.toiter(&_BBI);
484 _BBI.Detach();
485 }
486
487 }
488 else
489 {
490 _BBI.Attach(this);
491 _BBI.toroot();
492 _BI.tohead();
493 while (!_BI.hitroot())
494 {
495 Record* record=_BI.item();
496
497 record->Calc_Ysp(_low);
498 if (!found && (record->Ysp() < _low->GetY()))
499 {
500 found=true;
501 _BBI.toiter(&_BI);
502 }
503 _BI++;
504 }
505 _BI.toiter(&_BBI);
506 _BBI.Detach();
507 }
508 }
509 else
510 { //because the previous beam was flat the links to remove are
511 //below the last insert position
512 if (_low->GetBinHighest(true)) //is there something to remove
513 {
514
515 if ( scantype == LINKHOLES )
516 {
517 _BI.tohead();
518 while (!_BI.hitroot())
519 {
520 Record* record=_BI.item();
521 //records containing links towards the new low node
522 //are links to be removed
523 if ((record->GetLink()->GetEndNode() == _low) ||
524 (record->GetLink()->GetBeginNode() == _low)
525 )
526 {
527 holes = ProcessHoles(false,_I) || holes;
528 }
529 _BI++;
530 }
531 }
532
533 //on record back bring us to the last inserted record
534 //or if nothing was inserted the record before the last deleted record
535 //if there was no record before the last deleted record this means
536 //we where at the beginning of the beam, so at root
537
538 //_BI << (lastinserted+1);
539 //_BI--;
540 //if (_BI.hitroot()) //only possible when at the begin of the beam
541
542 _BI.tohead();
543 while (!_BI.hitroot())
544 {
545 Record* record=_BI.item();
546 //records containing links towards the new low node
547 //are links to be removed
548 if ((record->GetLink()->GetEndNode() == _low) ||
549 (record->GetLink()->GetBeginNode() == _low)
550 )
551 {
552 delete _BI.item();
553 _BI.remove();
554 found=true;
555 }
556 else if (found) //only once in here
557 break;
558 else if (record->Ysp() < _low->GetY())
559 //if flatlinks are not in the beam nothing will be found
560 //this will bring us to the right insertion point
561 break;
562 else
563 _BI++;
564 }
565 }
566 else
567 {
568 //on record back bring us to the last inserted record
569 //or if nothing was inserted the record before the last deleted record
570 //if there was no record before the last deleted record this means
571 //we where at the beginning of the beam, so at root
572
573 //_BI << (lastinserted+ 1);
574 //_BI--;
575 //if (_BI.hitroot()) //only possible when at the begin of the beam
576 _BI.tohead();
577 while (!_BI.hitroot())
578 {
579 Record* record=_BI.item();
580 if (record->Ysp() < _low->GetY())
581 break;
582 _BI++;
583 }
584 }
585 }
586 break;
587
588 case NODELINK:
589 case LINKLINK:
590 {
591 if (_type == NORMAL)
592 {
593 Calc_Ysp();
594 if (scantype==LINKLINK)
595 foundnew = Process_LinkToLink_Crossings() !=0 || foundnew;
596 else
597 SortTheBeam( false );
598 }
599 //else beam is already sorted because the added/removed flat links
600 //do not change the ysp of links already there, new non flat links
601 //are inserted in order, as result the beam stays sorted
602
603 if (_low->GetBinHighest(true)) //is there something to remove
604 {
605 _BI.tohead();
606 while (!_BI.hitroot())
607 {
608 Record* record=_BI.item();
609 //records containing links towards the new low node
610 //are links to be removed
611 if ((record->GetLink()->GetEndNode() == _low) ||
612 (record->GetLink()->GetBeginNode() == _low)
613 )
614 {
615 KBoolLine* line=record->GetLine();
616 if (scantype==NODELINK)
617 foundnew = Process_PointToLink_Crossings() !=0 || foundnew;
618 line->ProcessCrossings(_I);
619 delete _BI.item();
620 _BI.remove();
621 found=true;
622 }
623 //because the beam is sorted on ysp, stop when nothing can be there to remove
624 //and the right insertion point for new links has been found
625 else if ((record->Ysp() < _low->GetY()))
626 break;
627 else
628 _BI++;
629 }
630 }
631 else
632 {
633 _BI.tohead();
634 while (!_BI.hitroot())
635 {
636 Record* record=_BI.item();
637 //because the beam is sorted on ysp, stop when
638 //the right insertion point for new links has been found
639 if ((record->Ysp() < _low->GetY()))
640 break;
641 _BI++;
642 }
643 }
644 }
645 break;
646
647 default:
648 break;
649 }
650
651 return foundnew;
652 }
653 /*
654 bool ScanBeam::RemoveOld(SCANTYPE scantype,TDLI<KBoolLink>* _I, bool& holes )
655 {
656 bool found = false;
657 bool foundnew = false;
658 DL_Iter<Record*> _BBI=DL_Iter<Record*>();
659 bool attached=false;
660
661 _low = _I->item()->GetBeginNode();
662
663 switch(scantype)
664 {
665 case INOUT:
666 case GENLR:
667 case LINKHOLES:
668 if (_type==NORMAL )
669 {
670 KBoolLink* link = _low->GetBinHighest(true);
671 if ( link ) //is there something to remove
672 {
673 link->SetRecordNode( NULL );
674
675 if ( scantype == LINKHOLES )
676 {
677 _BI.tohead();
678 while (!_BI.hitroot())
679 {
680 Record* record = _BI.item();
681 //records containing links towards the new low node
682 //are links to be removed
683 if ((record->GetLink()->GetEndNode() == _low) ||
684 (record->GetLink()->GetBeginNode() == _low)
685 )
686 {
687 holes = ProcessHoles(false,_I) || holes;
688 }
689 _BI++;
690 }
691 }
692
693 _BI.tohead();
694 while (!_BI.hitroot())
695 {
696 Record* record=_BI.item();
697 //records containing links towards the new low node
698 //are links to be removed
699 if ((record->GetLink()->GetEndNode() == _low) ||
700 (record->GetLink()->GetBeginNode() == _low)
701 )
702 {
703 delete _BI.item();
704 _BI.remove();
705 found=true;
706 }
707 else if (found) //only once in here
708 {
709 attached=true;
710 found=false;
711 //recalculate ysp for the new scanline
712 record->Calc_Ysp(_low);
713 _BI++;
714 }
715 else
716 {
717 //recalculate ysp for the new scanline
718 record->Calc_Ysp(_low);
719 _BI++;
720 }
721 }
722 }
723 else
724 {
725 _BI.tohead();
726 while (!_BI.hitroot())
727 {
728 Record* record=_BI.item();
729 record->Calc_Ysp(_low);
730 _BI++;
731 }
732 }
733 }
734 else
735 { //because the previous beam was flat the links to remove are
736 //below the last insert position
737 KBoolLink* link;
738 link = _low->GetBinHighest(true);
739 if( link )//is there something to remove
740 {
741 link->SetRecordNode( NULL );
742
743 bool linkf = false;
744 _BI.tohead();
745 while (!_BI.hitroot())
746 {
747 Record* record = _BI.item();
748 if (record->GetLink() == link)
749 linkf = true;
750 _BI++;
751 }
752
753 if ( !linkf )
754 _BI.tohead();
755
756
757 if ( scantype == LINKHOLES )
758 {
759 _BI.tohead();
760 while (!_BI.hitroot())
761 {
762 Record* record=_BI.item();
763 //records containing links towards the new low node
764 //are links to be removed
765 if ((record->GetLink()->GetEndNode() == _low) ||
766 (record->GetLink()->GetBeginNode() == _low)
767 )
768 {
769 holes = ProcessHoles(false,_I) || holes;
770 }
771 _BI++;
772 }
773 }
774
775 //_BI.tonode( link->GetRecordNode() );
776 //delete _BI.item();
777 //_BI.remove();
778
779 //on record back bring us to the last inserted record
780 //or if nothing was inserted the record before the last deleted record
781 //if there was no record before the last deleted record this means
782 //we where at the beginning of the beam, so at root
783
784 //_BI << (lastinserted+1);
785 //_BI--;
786 //if (_BI.hitroot()) //only possible when at the begin of the beam
787
788 //found=false;
789
790 _BI.tohead();
791 while (!_BI.hitroot())
792 {
793 Record* record=_BI.item();
794 //records containing links towards the new low node
795 //are links to be removed
796 if ((record->GetLink()->GetEndNode() == _low) ||
797 (record->GetLink()->GetBeginNode() == _low)
798 )
799 {
800 if ( link != record->GetLink() )
801 {
802 break;
803 }
804 if ( link->GetRecordNode() != _BI.node() )
805 {
806 delete _BI.item();
807 _BI.remove();
808 }
809 else
810 {
811 delete _BI.item();
812 _BI.remove();
813 }
814 found=true;
815 }
816 else if (found) //only once in here
817 break;
818 else if (record->Ysp() < _low->GetY())
819 //if flatlinks are not in the beam nothing will be found
820 //this will bring us to the right insertion point
821 break;
822 else
823 _BI++;
824 }
825
826 }
827
828 else
829 {
830
831 //on record back bring us to the last inserted record
832 //or if nothing was inserted the record before the last deleted record
833 //if there was no record before the last deleted record this means
834 //we where at the beginning of the beam, so at root
835
836 //_BI << (lastinserted+ 1);
837 //_BI--;
838 //if (_BI.hitroot()) //only possible when at the begin of the beam
839 _BI.tohead();
840 while (!_BI.hitroot())
841 {
842 Record* record=_BI.item();
843 if (record->Ysp() < _low->GetY())
844 break;
845 _BI++;
846 }
847
848 }
849 }
850 break;
851
852 case NODELINK:
853 case LINKLINK:
854 {
855 if (_type == NORMAL)
856 {
857 Calc_Ysp();
858 if (scantype==LINKLINK)
859 foundnew = Process_LinkToLink_Crossings() !=0 || foundnew;
860 else
861 SortTheBeam( false );
862 }
863 //else beam is already sorted because the added/removed flat links
864 //do not change the ysp of links already there, new non flat links
865 //are inserted in order, as result the beam stays sorted
866
867 if (_low->GetBinHighest(true)) //is there something to remove
868 {
869 _BI.tohead();
870 while (!_BI.hitroot())
871 {
872 Record* record=_BI.item();
873 //records containing links towards the new low node
874 //are links to be removed
875 if ((record->GetLink()->GetEndNode() == _low) ||
876 (record->GetLink()->GetBeginNode() == _low)
877 )
878 {
879 KBoolLine* line=record->GetLine();
880 if (scantype==NODELINK)
881 foundnew = Process_PointToLink_Crossings() !=0 || foundnew;
882 line->ProcessCrossings(_I);
883 delete _BI.item();
884 _BI.remove();
885 found=true;
886 }
887 //because the beam is sorted on ysp, stop when nothing can be there to remove
888 //and the right insertion point for new links has been found
889 else if ((record->Ysp() < _low->GetY()))
890 break;
891 else
892 _BI++;
893 }
894 }
895 else
896 {
897 _BI.tohead();
898 while (!_BI.hitroot())
899 {
900 Record* record=_BI.item();
901 //because the beam is sorted on ysp, stop when
902 //the right insertion point for new links has been found
903 if ((record->Ysp() < _low->GetY()))
904 break;
905 _BI++;
906 }
907 }
908 }
909 break;
910
911 default:
912 break;
913 }
914
915 return foundnew;
916 }
917 */
918
SortTheBeam(bool backangle)919 void ScanBeam::SortTheBeam( bool backangle )
920 {
921 if ( backangle )
922 _BI.mergesort( recordsorter_ysp_angle_back );
923 else
924 _BI.mergesort( recordsorter_ysp_angle );
925 }
926
Calc_Ysp()927 void ScanBeam::Calc_Ysp()
928 {
929 _BI.tohead();
930 while (!_BI.hitroot())
931 {
932 Record* record=_BI.item();
933 // KBoolLink* link=_BI.item()->GetLink();
934 record->Calc_Ysp(_low);
935 _BI++;
936 }
937 }
938
939 // this function will set for all the records which contain a link with the
940 // corresponding graphnumber the inc flag.
941 // The inc flag's function is to see in a beam if we go deeper in the graph or not
Generate_INOUT(int graphnumber)942 void ScanBeam::Generate_INOUT(int graphnumber)
943 {
944 DIRECTION first_dir = GO_LEFT;
945 int diepte = 0;
946
947 DL_Iter<Record*> _BBI = DL_Iter<Record*>();
948 _BBI.Attach(this);
949 for( _BBI.tohead(); !_BBI.hitroot(); _BBI++ )
950 {
951 // recalculate _inc again
952 if ( _BBI.item()->GetLink()->GetGraphNum()==graphnumber)
953 { //found a link that belongs to the graph
954 if (diepte==0)
955 { // first link found or at depth zero again
956 // the direction is important since this is used to find out
957 // if we go further in or out for coming links
958 first_dir=_BBI.item()->Direction();
959 _BBI.item()->GetLink()->SetInc(true);
960 diepte=1;
961 }
962 else
963 { // according to depth=1 links set depth
964 // verhoog of verlaag diepte
965 if (_BBI.item()->Direction() == first_dir)
966 {
967 diepte++;
968 _BBI.item()->GetLink()->SetInc(true);
969 }
970 else
971 {
972 diepte--;
973 _BBI.item()->GetLink()->SetInc(false);
974 }
975 }
976 }
977 if ( _BBI.item() == _BI.item()) break; //not need to do the rest, will come in a later beam
978 }
979 _BBI.Detach();
980 }
981
982
983 // function ProcessHoles
984 //
985 // this function will search the closest link to a hole
986 // step one, search for a link that is marked (this is a hole)
987 // step two, this is tricky, the closest link is the previous link in
988 // the beam, but only in the beam that contains the highest node
989 // from the marked link.
990 // why ? : if the marked link has for the begin and end node different
991 // x,y values, see below as link C
992 // B
993 // A +---------+
994 // +----------+
995 // ___--+
996 // ___---
997 // +--- C
998 //
999 // when we at first detect link C we would link it to link A, should work he
1000 // but; we always link a hole at its topleft node, so the highest node
1001 // and then we can't link to A but we should link to B
1002 // so when we found the link, we will look if the node that will come
1003 // in a later beam will be higher than the current, if so we will wait
1004 // till that node comes around otherwise we will link this node to the
1005 // closest link (prev in beam)
ProcessHoles(bool atinsert,TDLI<KBoolLink> * _LI)1006 bool ScanBeam::ProcessHoles( bool atinsert, TDLI<KBoolLink>* _LI )
1007 {
1008 // The scanbeam must already be sorted at this moment
1009 Node *topnode;
1010 bool foundholes = false;
1011
1012 Record* record = _BI.item();
1013 KBoolLink* link = record->GetLink();
1014
1015 if (!record->GetLine()->CrossListEmpty())
1016 {
1017 SortTheBeam( atinsert );
1018
1019 // link the holes in the graph to a link above.
1020 // a the link where the linecrosslist is not empty, means that
1021 // there are links which refer to this link (must be linked to this link)
1022 // make new nodes and links and set them, re-use the old link, so the links
1023 // that still stand in the linecrosslist will not be lost.
1024 // There is a hole that must be linked to this link !
1025 TDLI<Node> I(record->GetLine()->GetCrossList());
1026 I.tohead();
1027 while(!I.hitroot())
1028 {
1029 topnode = I.item();
1030 I.remove();
1031
1032 KBoolLine line(_GC);
1033 line.Set(link);
1034
1035 B_INT Y = line.Calculate_Y(topnode->GetX());
1036
1037 // Now we'll create new nodes and new links to make the link between
1038 // the graphs.
1039
1040 //holes are always linked in a non hole or hole
1041 //for a non hole this link will be to the right
1042 //because non holes are right around
1043 //for holes this will be to the right also,
1044 //because they are left around but the link is always on the
1045 //bottom of the hole
1046
1047 // linkA linkD
1048 // o-------->--------NodeA------->------------o
1049 // | |
1050 // | |
1051 // linkB v ^ linkBB
1052 // | |
1053 // | |
1054 // outgoing* | | incoming*
1055 // o------<---------topnode--------<----------o
1056 //
1057 // all holes are oriented left around
1058
1059
1060 Node * leftnode; //left node of clossest link
1061 (link->GetBeginNode()->GetX() < link->GetEndNode()->GetX()) ?
1062 leftnode = link->GetBeginNode():
1063 leftnode = link->GetEndNode();
1064
1065 Node *node_A = new Node(topnode->GetX(),Y, _GC);
1066 KBoolLink *link_A = new KBoolLink(0, link->m_user_data, leftnode, node_A, _GC);
1067 KBoolLink *link_B = new KBoolLink(0, link->m_user_data, node_A, topnode, _GC);
1068 KBoolLink *link_BB = new KBoolLink(0, link->m_user_data, topnode, node_A, _GC);
1069 KBoolLink *link_D = _BI.item()->GetLink();
1070 link_D->Replace(leftnode,node_A);
1071 _LI->insbegin(link_A);
1072 _LI->insbegin(link_B);
1073 _LI->insbegin(link_BB);
1074
1075 //mark those two segments as hole linking segments
1076 link_B->SetHoleLink(true);
1077 link_BB->SetHoleLink(true);
1078
1079 //is where we come from/link to a hole
1080 bool closest_is_hole = link->GetHole();
1081
1082 // if the polygon linked to, is a hole, this hole here
1083 // just gets bigger, so we take over the links its hole marking.
1084 link_A->SetHole(closest_is_hole);
1085 link_B->SetHole(closest_is_hole);
1086 link_BB->SetHole(closest_is_hole);
1087
1088 // we have only one operation at the time, taking
1089 // over the operation flags is enough, since the linking segments will
1090 // be part of that output for any operation done.
1091 link_A->TakeOverOperationFlags( link );
1092 link_B->TakeOverOperationFlags( link );
1093 link_BB->TakeOverOperationFlags( link );
1094 }
1095 }
1096
1097 if (link->IsTopHole() )
1098 {
1099 SortTheBeam( atinsert );
1100 writebeam();
1101 }
1102
1103 if (link->IsTopHole() && !_BI.athead() )
1104 {
1105 // now we check if this hole should now be linked, or later
1106 // we always link on the node with the maximum y value, Why ? because i like it !
1107 // to link we put the node of the hole into the crosslist of the closest link !
1108
1109 assert( record->Direction() == GO_LEFT );
1110 // he goes to the left
1111 if (atinsert)
1112 {
1113 if ( link->GetBeginNode()->GetY() <= link->GetEndNode()->GetY() )
1114 {
1115 topnode = link->GetEndNode();
1116 //the previous link in the scanbeam == the closest link to the hole in vertical
1117 //direction PUT this node into this link
1118 _BI--;
1119 _BI.item()->GetLine()->AddCrossing(topnode);
1120 _BI++;
1121 //reset tophole flag, hole has been processed
1122 link->SetTopHole(false);
1123 foundholes = true;
1124 }
1125 }
1126 else //remove stage of links from te beam
1127 {
1128 //the tophole link was NOT linked at the insert stage, so it most be linked now
1129 topnode = _BI.item()->GetLink()->GetBeginNode();
1130 //the previous link in the scanbeam == the closest link to the hole in vertical
1131 //direction PUT this node into this link
1132 _BI--;
1133 _BI.item()->GetLine()->AddCrossing(topnode);
1134 _BI++;
1135 //reset mark to flag that this hole has been processed
1136 link->SetTopHole(false);
1137 foundholes = true;
1138 }
1139 }
1140 return foundholes;
1141 }
1142
1143 //sort the records on Ysp if eqaul, sort on tangent at ysp
recordsorter_ysp_angle(Record * rec1,Record * rec2)1144 int recordsorter_ysp_angle(Record* rec1, Record* rec2)
1145 {
1146 if (rec1->Ysp() > rec2->Ysp() )
1147 return(1);
1148 if (rec1->Ysp() < rec2->Ysp() )
1149 return(-1);
1150 //it seems they are equal
1151 B_INT rightY1;
1152 if (rec1->Direction()==GO_LEFT)
1153 rightY1 = rec1->GetLink()->GetBeginNode()->GetY();
1154 else
1155 rightY1 = rec1->GetLink()->GetEndNode()->GetY();
1156 B_INT rightY2;
1157 if (rec2->Direction()==GO_LEFT)
1158 rightY2 = rec2->GetLink()->GetBeginNode()->GetY();
1159 else
1160 rightY2 = rec2->GetLink()->GetEndNode()->GetY();
1161
1162 if ( rightY1 > rightY2 )
1163 return(1);
1164 if ( rightY1 < rightY2 )
1165 return(-1);
1166 return(0);
1167 }
1168
1169 //sort the records on Ysp if eqaul, sort on tangent at ysp
recordsorter_ysp_angle_back(Record * rec1,Record * rec2)1170 int recordsorter_ysp_angle_back(Record* rec1, Record* rec2)
1171 {
1172 if (rec1->Ysp() > rec2->Ysp() )
1173 return(1);
1174 if (rec1->Ysp() < rec2->Ysp() )
1175 return(-1);
1176 //it seems they are equal
1177 B_INT leftY1;
1178 if ( rec1->Direction() == GO_RIGHT )
1179 leftY1 = rec1->GetLink()->GetBeginNode()->GetY();
1180 else
1181 leftY1 = rec1->GetLink()->GetEndNode()->GetY();
1182 B_INT leftY2;
1183 if ( rec2->Direction() == GO_RIGHT )
1184 leftY2 = rec2->GetLink()->GetBeginNode()->GetY();
1185 else
1186 leftY2 = rec2->GetLink()->GetEndNode()->GetY();
1187
1188 if ( leftY1 > leftY2 )
1189 return(1);
1190 if ( leftY1 < leftY2 )
1191 return(-1);
1192 return(0);
1193 }
1194
1195 // swap functie for cocktailsort ==> each swap means an intersection of links
swap_crossing_normal(Record * a,Record * b)1196 bool swap_crossing_normal(Record *a, Record *b)
1197 {
1198 if (!a->Equal(b)) // records NOT parallel
1199 {
1200 a->GetLine()->Intersect_simple( b->GetLine() );
1201 return true;
1202 }
1203 return false;
1204 }
1205
Process_LinkToLink_Crossings()1206 int ScanBeam::Process_LinkToLink_Crossings()
1207 {
1208 // sort on y value of next intersection; and find the intersections
1209 return _BI.cocktailsort( recordsorter_ysp_angle_back, swap_crossing_normal );
1210 }
1211
1212 //catch node to link crossings
1213 // must be sorted on ysp
Process_PointToLink_Crossings()1214 int ScanBeam::Process_PointToLink_Crossings()
1215 {
1216 int merges = 0;
1217 Record* record;
1218
1219 if (_BI.count() > 1)
1220 {
1221 DL_Iter<Record*> IL = DL_Iter<Record*>(this);
1222 IL.toiter(&_BI);
1223
1224 //from IL search back for close links
1225 IL--;
1226 while(!IL.hitroot())
1227 {
1228 record=IL.item();
1229
1230 if (record->Ysp() > _low->GetY()+ _GC->GetInternalMarge())
1231 break;
1232
1233 // the distance to the lo/hi node is smaller then the _GC->GetInternalMarge()
1234 if( (record->GetLink()->GetBeginNode()!= _low) &&
1235 (record->GetLink()->GetEndNode() != _low)
1236 )
1237 { // the link is not towards the lohi node
1238 record->GetLine()->AddCrossing(_low);
1239 merges++;
1240 }
1241 IL--;
1242 }
1243
1244 //from IL search forward for close links
1245 IL.toiter(&_BI);
1246 IL++;
1247 while(!IL.hitroot())
1248 {
1249 record=IL.item();
1250
1251 if (record->Ysp() < _low->GetY()- _GC->GetInternalMarge())
1252 break;
1253
1254 // the distance to the lohi node is smaller then the booleng->Get_Marge()
1255 if( (record->GetLink()->GetBeginNode()!=_low) &&
1256 (record->GetLink()->GetEndNode() !=_low)
1257 )
1258 { // the link is not towards the low node
1259 record->GetLine()->AddCrossing(_low);
1260 merges++;
1261 }
1262 IL++;
1263 }
1264
1265 }
1266
1267 return merges;
1268 }
1269
Process_LinkToLink_Flat(KBoolLine * flatline)1270 int ScanBeam::Process_LinkToLink_Flat(KBoolLine* flatline)
1271 {
1272 int crossfound = 0;
1273 Record* record;
1274 DL_Iter<Record*> _BBI = DL_Iter<Record*>();
1275 _BBI.Attach(this);
1276 _BBI.toiter(&_BI);
1277
1278 for(_BI.tohead(); !_BI.hitroot(); _BI++)
1279 {
1280 record=_BI.item();
1281
1282 if (record->Ysp() < (flatline->GetLink()->GetLowNode()->GetY() - _GC->GetInternalMarge()))
1283 break;//they are sorted so no other can be there
1284
1285 if ((record->Ysp() > (flatline->GetLink()->GetLowNode()->GetY() - _GC->GetInternalMarge()))
1286 &&
1287 (record->Ysp() < (flatline->GetLink()->GetHighNode()->GetY() + _GC->GetInternalMarge()))
1288 )
1289 { //it is in between the flat link region
1290 //create a new node at ysp and insert it in both the flatlink and the crossing link
1291
1292 if (
1293 (record->GetLink()->GetEndNode() != flatline->GetLink()->GetHighNode()) &&
1294 (record->GetLink()->GetEndNode() != flatline->GetLink()->GetLowNode() ) &&
1295 (record->GetLink()->GetBeginNode()!= flatline->GetLink()->GetHighNode()) &&
1296 (record->GetLink()->GetBeginNode()!= flatline->GetLink()->GetLowNode() )
1297 )
1298 {
1299 Node *newnode = new Node(_low->GetX(),_BI.item()->Ysp(), _GC);
1300 flatline->AddCrossing(newnode);
1301 record->GetLine()->AddCrossing(newnode);
1302 crossfound++;
1303 }
1304 }
1305 }
1306
1307 _BI.toiter(&_BBI);
1308 _BBI.Detach();
1309 return crossfound;
1310 }
1311
checksort()1312 bool ScanBeam::checksort()
1313 {
1314 // if empty then just insert
1315 if (empty())
1316 return true;
1317
1318 // put new item left of the one that is bigger
1319 _BI.tohead();
1320 Record* prev=_BI.item();
1321 _BI++;
1322 while(!_BI.hitroot())
1323 {
1324 Record* curr=_BI.item();
1325 if (recordsorter_ysp_angle(prev,curr)==-1)
1326 {
1327 recordsorter_ysp_angle(prev,curr);
1328 return false;
1329 }
1330 prev=_BI.item();
1331 _BI++;
1332 }
1333 return true;
1334 }
1335
writebeam()1336 bool ScanBeam::writebeam()
1337 {
1338 #if KBOOL_DEBUG == 1
1339 FILE* file = _GC->GetLogFile();
1340
1341 if (file == NULL)
1342 return true;
1343
1344 fprintf( file, "# beam %d \n", count() );
1345 fprintf( file, " low %I64d %I64d \n", _low->GetX() , _low->GetY() );
1346 fprintf( file, " type %d \n", _type );
1347
1348 if (empty())
1349 {
1350 fprintf( file, " empty \n" );
1351 return true;
1352 }
1353
1354 DL_Iter<Record*> _BI( this );
1355
1356 // put new item left of the one that is bigger
1357 _BI.tohead();
1358 while(!_BI.hitroot())
1359 {
1360 Record* cur=_BI.item();
1361
1362 fprintf( file, " ysp %I64d \n", cur->Ysp() );
1363
1364 KBoolLink* curl=cur->GetLink();
1365
1366 fprintf( file, " linkbegin %I64d %I64d \n", curl->GetBeginNode()->GetX(), curl->GetBeginNode()->GetY() );
1367 fprintf( file, " linkend %I64d %I64d \n", curl->GetEndNode()->GetX(), curl->GetEndNode()->GetY() );
1368
1369 _BI++;
1370 }
1371 #endif
1372
1373 return true;
1374 }
1375