scanbeam.cpp

EDA PCB 电路设计工具源码 c/c++ for Linux, Windows, Mac, 2008.8 最新

/*! \file ../src/scanbeam.cpp
    \author Probably Klaas Holwerda or Julian Smart

    Copyright: 2001-2004 (C) Probably Klaas Holwerda 

    Licence: wxWidgets Licence

    RCS-ID: $Id: scanbeam.cpp,v 1.10 2005/06/17 23:05:18 kbluck Exp $
*/

#ifdef __GNUG__
#pragma implementation
#endif

// class scanbeam
// this class represents de space between two scanlines
#include "../include/scanbeam.h"
#include <math.h>
#include <assert.h>

#include "../include/booleng.h"

#include "../include/graph.h"
#include "../include/node.h"

//this here is to initialize the static iterator of scanbeam
//with NOLIST constructor

int recordsorter(Record* , Record* );

int recordsorter_ysp_angle(Record* , Record* );
int recordsorter_ysp_angle_back(Record* rec1, Record* rec2);

ScanBeam::ScanBeam(Bool_Engine* GC):DL_List<Record*>()
{
   _GC = GC;
	_type=NORMAL;
   _BI.Attach(this);
}

ScanBeam::~ScanBeam()
{
   //first delete all record still in the beam
   _BI.Detach();
   remove_all( true );

   //DeleteRecordPool(); 
}

void ScanBeam::SetType(Node* low,Node* high)
{
   if (low->GetX() < high->GetX())
   	_type=NORMAL;
   else
   	_type=FLAT;
}

/*
//catch node to link crossings
// must be sorted on ysp
int ScanBeam::FindCloseLinksAndCross(TDLI<KBoolLink>* _I,Node* _lowf)
{
	int merges = 0;
	Record* record;

   TDLI<Record> _BBI=TDLI<Record>(this);

	if (_BI.count() > 1)
	{
		//first search a link towards this node
		for(_BI.tohead(); !_BI.hitroot(); _BI++)
		{
			record=_BI.item();
			if( (record->GetLink()->GetBeginNode()==_lowf) ||
				 (record->GetLink()->GetEndNode()  ==_lowf)
			  )
			  break;
		}

		//NOTICE if the node "a_node" is not inside a record
		//for instance to connected flat links (flatlinks not in beam)
		//then IL will be at end    (those will be catched at 90 degrees rotation)
		if (_BI.hitroot())
      {
			return(merges);
      }

      //from IL search back for close links
      _BBI.toiter(&_BI);
      _BBI--;
      while(!_BBI.hitroot())
      {
         record=_BBI.item();

         if (record->Ysp() != _lowf->GetY())
            break;

         // the distance to the low node is smaller then the MARGE
         if( (record->GetLink()->GetBeginNode()!=_lowf) &&
             (record->GetLink()->GetEndNode()  !=_lowf)
           )
         {  // the link is not towards the low node
            record->GetLink()->AddCrossing(_lowf);
            record->SetNewLink(record->GetLink()->ProcessCrossingsSmart(_I));
            merges++;
         }
         _BBI--;
      }

      //from IL search forward for close links
      _BBI.toiter(&_BI);
      _BBI++;
      while(!_BBI.hitroot())
      {
         record=_BBI.item();

         if (record->Ysp() != _lowf->GetY())
//         if (record->Ysp() < _lowf->GetY()-MARGE)
            break;

         // the distance to the low node is smaller then the MARGE
         if( (record->GetLink()->GetBeginNode()!=_lowf) &&
             (record->GetLink()->GetEndNode()  !=_lowf)
           )
         {  // the link is not towards the low node
            record->GetLink()->AddCrossing(_lowf);
            record->SetNewLink(record->GetLink()->ProcessCrossingsSmart(_I));
            merges++;
         }
         _BBI++;
      }
   }
	return merges;
}
*/

/*
bool  ScanBeam::Update(TDLI<KBoolLink>* _I,Node* _lowf)
{
	bool found=false;
	KBoolLink* link;

	_BI.tohead();
	while (!_BI.hitroot())
	{

		Record* record=_BI.item();
		record->Calc_Ysp(_type,_low);
		_BI++;
	}

   FindCloseLinksAndCross(_I,_lowf);

   _BI.tohead();
   while (!_BI.hitroot())
   {
      Record* record=_BI.item();
      //records containing links towards the new low node
      //are links to be marked for removal

      if ((record->GetLink()->GetEndNode() == _lowf) ||
          (record->GetLink()->GetBeginNode() == _lowf)
         )
      {
         //cross here the links that meat eachother now
         delete _BI.item();
         _BI.remove();

         //cross here the links that meat eachother now
         _BI--;
         if (!_BI.hitroot() && (_BI.count() > 1))
         {
            Record* prev=_BI.item();
            _BI++;
            if (!_BI.hitroot())
            {
               if (!_BI.item()->Equal(prev)) // records NOT parallel
                  if (_BI.item()->GetLine()->Intersect(prev->GetLine(),MARGE))
                  {
                     //they did cross, integrate the crossings in the graph
                     //this  may modify the links already part of the record
                     //this is why they are returned in set for the record
                     _BI.item()->SetNewLink(_BI.item()->GetLink()->ProcessCrossingsSmart(_I));
                     prev->SetNewLink(prev->GetLink()->ProcessCrossingsSmart(_I));
                  }
            }
         }
         else
          	_BI++;
      }
      else
         _BI++;
   }

	//writebeam();

   //ONLY links towards the low node are possible to be added
	//the bin flag will be set if it fits in the beam
	//so for following beams it will not be checked again
	while ( bool(link=_lowf->GetBinHighest(false)) )
	{
      Record* record=new Record(link);
      // yp_new will always be the y of low node since all new links are
      // from this node
      record->SetYsp(_lowf->GetY());
      record->Set_Flags(_type);
      //need to calculate ysn to be able to sort this record in the right order
      //this is only used when the insert node is equal for both records
      // ins_smart and cross neighbour  directly
      // if empty then just insert

      if (empty())
         insend(record);
      else
      {
         // put new item left of the one that is bigger
         _BI.tohead();
         while(!_BI.hitroot())
         {
            if (recordsorter_ysp_angle(record,_BI.item())==1)
               break;
            _BI++;
         }

         _BI.insbefore(record);
         _BI--;_BI--; //just before the new record inserted
         if (!_BI.hitroot())
         {
            Record* prev=_BI.item();
            _BI++; //goto the new record inserted
            if (!_BI.item()->Equal(prev)) // records NOT parallel
            {
               if (_BI.item()->GetLine()->Intersect(prev->GetLine(),MARGE))
               {
                  //this  may modify the links already part of the record
                  //this is why they are returned in set for the record
                  _BI.item()->SetNewLink(_BI.item()->GetLink()->ProcessCrossingsSmart(_I));
                  prev->SetNewLink(prev->GetLink()->ProcessCrossingsSmart(_I));
               }
            }
         }
         else
           _BI++;

         Record* prev=_BI.item(); //the new record
         _BI++;
         if (!_BI.hitroot() && !_BI.item()->Equal(prev)) // records NOT parallel
         {
	         Record* cur=_BI.item();
            if (cur->GetLine()->Intersect(prev->GetLine(),MARGE))
            {
               //this  may modify the links already part of the record
               //this is why they are returned in set for the record
               cur->SetNewLink(cur->GetLink()->ProcessCrossingsSmart(_I));
               prev->SetNewLink(prev->GetLink()->ProcessCrossingsSmart(_I));
            }
         }
      }
      //remember this to calculate in/out values for each new link its polygon again.
      GNI->insend(record->GetLink()->GetGraphNum());
      found=true;
	   record->GetLink()->SetBeenHere();
   }

   FindCloseLinksAndCross(_I,_lowf);
	//writebeam();
	return(found);
}
*/

bool ScanBeam::FindNew(SCANTYPE scantype,TDLI<KBoolLink>* _I, bool& holes )
{
   bool foundnew = false;

   _low = _I->item()->GetBeginNode();

	KBoolLink* link;

	//if (!checksort())
	//	SortTheBeam();

   lastinserted=0;
   //ONLY links towards the low node are possible to be added
	//the bin flag will be set if it fits in the beam
	//so for following beams it will not be checked again
	while ( (link = _low->GetBinHighest(false)) != NULL )
   {
     	if ( (link->GetEndNode()->GetX() == link->GetBeginNode()->GetX()) //flatlink in flatbeam
           && ((scantype == NODELINK) || (scantype == LINKLINK) || (scantype == LINKHOLES))
         )
      {
            switch(scantype)
            {
               case NODELINK:
               {
                  //all vertical links in flatbeam are ignored
                  //normal link in beam
                  Record* record=new Record(link,_GC);
                  // yp_new will always be the y of low node since all new links are
                  // from this node
                  record->SetYsp(_low->GetY());
                  record->Set_Flags();
                  // put new item left of the one that is lower in the beam 
                  // The last one inserted in this loop, is already left of the current
                  // iterator position. So the new links are inerted in proper order.                  
                  link->SetRecordNode( _BI.insbefore(record) );
                  _BI--;
	               foundnew = Process_PointToLink_Crossings() !=0 || foundnew;
                  delete record;
                  _BI.remove();
                  break;
               }
               case LINKLINK:
               //is the new record a flat link
               {
                  KBoolLine flatline = KBoolLine(link, _GC);
                  foundnew = Process_LinkToLink_Flat(&flatline) || foundnew;
                  //flatlinks are not part of the beams, still they are used to find new beams
                  //they can be processed now if the beginnode does not change, since this is used to
                  //to find new beams. and its position does not change
                  //ProcessCrossings does take care of this
	   				flatline.ProcessCrossings(_I);
		            break;
               }
               case LINKHOLES : //holes are never to flatlinks
                   assert( true );
      	      default: 
      		       break;             
            }
      }
      else
      {
         //normal link in beam
         Record* record = new Record(link,_GC);
         // yp_new will always be the y of low node since all new links are
         // from this node
         record->SetYsp(_low->GetY());
         record->Set_Flags();
         // put new item left of the one that is lower in the beam 
         // The last one inserted in this loop, is already left of the current
         // iterator position. So the new links are inserted in proper order.
         link->SetRecordNode( _BI.insbefore(record) );         
         lastinserted++;

         //_GC->Write_Log( "after insert" );
         writebeam();

         switch(scantype)
         {
          case NODELINK:
               _BI--;
               foundnew = Process_PointToLink_Crossings() !=0  || foundnew;
               _BI++;
               break;
          case INOUT:
            {
               _BI--;
               //now we can set the _inc flag
					Generate_INOUT(record->GetLink()->GetGraphNum());
               _BI++;
            }
            break;
          case GENLR:
            {
               //now we can set the a/b group flags based on the above link
               _BI--;
               _BI--;
               Record* above=0;
               if (!_BI.hitroot())
                  above=_BI.item();
               _BI++;

               //something to do for winding rule

               if (record->Calc_Left_Right(above))
               {
                  delete record;
                  _BI.remove();
                  lastinserted--;
               }
               else
                  _BI++;
            }
            break;
          case LINKHOLES:
            _BI--;
            holes = ProcessHoles(true,_I) || holes;
            _BI++;
            break;

	       default:
	         break;
         }
      }
      link->SetBeenHere();
	}

   writebeam();

	return foundnew;
}

bool ScanBeam::RemoveOld(SCANTYPE scantype,TDLI<KBoolLink>* _I, bool& holes )
{
	bool found = false;
	bool foundnew = false;
   DL_Iter<Record*>  _BBI=DL_Iter<Record*>();
	bool attached=false;

   _low = _I->item()->GetBeginNode();

   switch(scantype)
   {
      case INOUT:
      case GENLR:
      case LINKHOLES:
      if (_type==NORMAL )
      {
         if (_low->GetBinHighest(true)) //is there something to remove
         {
            if ( scantype == LINKHOLES )
            {
               _BI.tohead();
               while (!_BI.hitroot())
               {
                  Record* record=_BI.item();
                  //records containing links towards the new low node
                  //are links to be removed
                  if ((record->GetLink()->GetEndNode() == _low) ||
                      (record->GetLink()->GetBeginNode() == _low)
                     )
                  {
                     holes = ProcessHoles(false,_I) || holes;
                  }
                  _BI++;
               }
            }

            _BI.tohead();
            while (!_BI.hitroot())
            {
               Record* record=_BI.item();
               //records containing links towards the new low node
               //are links to be removed
               if ((record->GetLink()->GetEndNode() == _low) ||
                   (record->GetLink()->GetBeginNode() == _low)
                  )
               {
                  if (attached)   //there is a bug
                  {
                     _BBI.Detach();
                     if (!checksort())
                        SortTheBeam( true );
                     _BI.tohead();
                     attached=false;

                  }
                  delete _BI.item();
                  _BI.remove();