graph.cpp

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

//	         writegraph(true);
//	         scanbeam->writebeam();
         }
*/


//=============================== Global Functions =============================

// Sorts the links on the X values
int linkXYsorter(KBoolLink *a, KBoolLink* b)
{
	if ( a->GetBeginNode()->GetX() < b->GetBeginNode()->GetX())
		return(1);
	if ( a->GetBeginNode()->GetX() > b->GetBeginNode()->GetX())
		return(-1);
   //they are eqaul in x
	if ( a->GetBeginNode()->GetY() < b->GetBeginNode()->GetY())
		return(-1);
	if ( a->GetBeginNode()->GetY() > b->GetBeginNode()->GetY())
		return(1);
   //they are eqaul in y
	return(0);
}

// Sorts the links on the Y value of the beginnode
int linkYXsorter(KBoolLink *a, KBoolLink* b)
{
	if ( a->GetBeginNode()->GetY() > b->GetBeginNode()->GetY())
		return(1);
	if ( a->GetBeginNode()->GetY() < b->GetBeginNode()->GetY())
		return(-1);
	if ( a->GetBeginNode()->GetX() > b->GetBeginNode()->GetX())
		return(-1);
	if ( a->GetBeginNode()->GetX() < b->GetBeginNode()->GetX())
		return(1);
	return(0);
}


// The sort function for sorting graph from shortest to longest (_l1 < _l2)
int linkLsorter(KBoolLink *_l1, KBoolLink* _l2)
{
	B_INT dx1,dx2,dy1,dy2;
	dx1 = (_l1->GetEndNode()->GetX() - _l1->GetBeginNode()->GetX());
	dx1*=dx1;
	dy1 = (_l1->GetEndNode()->GetY() - _l1->GetBeginNode()->GetY());
	dy1*=dy1;
	dx2 = (_l2->GetEndNode()->GetX() - _l2->GetBeginNode()->GetX());
	dx2*=dx2;
	dy2 = (_l2->GetEndNode()->GetY() - _l2->GetBeginNode()->GetY());
	dy2*=dy2;

	dx1+=dy1;	dx2+=dy2;

	if ( dx1 > dx2 )
		return(-1);
	if ( dx1 < dx2 )
		return(1);
	return(0);
}

// The sort function for the links in a graph (a.topnode < b.topnode)
// if the two links lay with the top nodes on eachother the most left will be selected

int linkYXtopsorter(KBoolLink *a, KBoolLink *b)
{

	if (bmax(a->GetBeginNode()->GetY(),a->GetEndNode()->GetY()) < bmax(b->GetBeginNode()->GetY(),b->GetEndNode()->GetY()))
		return -1;

	if (bmax(a->GetBeginNode()->GetY(),a->GetEndNode()->GetY()) > bmax(b->GetBeginNode()->GetY(),b->GetEndNode()->GetY()))
		return 1;

	//equal
   if (bmin(a->GetBeginNode()->GetX(),a->GetEndNode()->GetX()) < bmin(b->GetBeginNode()->GetX(),b->GetEndNode()->GetX()))
	   return -1;

   if (bmin(a->GetBeginNode()->GetX(),a->GetEndNode()->GetX()) > bmin(b->GetBeginNode()->GetX(),b->GetEndNode()->GetX()))
		return 1;

	return 0;
}

// The sort function for sorting graph from shortest to longest (_l1 < _l2)
int linkGraphNumsorter(KBoolLink *_l1, KBoolLink* _l2)
{
	if ( _l1->GetGraphNum() > _l2->GetGraphNum())
		return(-1);
	if ( _l1->GetGraphNum() < _l2->GetGraphNum())
		return(1);
	return(0);
}

// Perform an operation on the graph
void Graph::Boolean(BOOL_OP operation,GraphList* Result)
{
	_GC->SetState("Performing Operation");

	// At this moment we have one graph
	// step one, split it up in single graphs, and mark the holes
	// step two, make one graph again and link the holes
	// step three, split up again and dump the result in Result

	_GC->SetState("Extract simples first ");

   ResetBinMark();
   DeleteNonCond(operation);
   HandleNonCond(operation);

   bool foundholes = false;
   try
	{
      WriteGraphKEY(_GC);
      writegraph(true);

		Extract_Simples(operation,true, foundholes);
	}
	catch (Bool_Engine_Error& error)
	{
      throw error;
	}

	// now we will link all the holes in de graphlist
	// By the scanbeam method we will search all the links that are marked
	//	as topleft link of a the hole polygon, when we find them we will get the
	//	closest link, being the one higher in the beam.
	//	Next we will create a link and nodes toceoonect the hole into it outside contour 
   // or other hole.
	_GC->SetState("Linking Holes");

   if (_linklist->count() == 0)
      //extract simples did leaf an empty graph
      //so we are ready
      return;

   if ( foundholes && _GC->GetLinkHoles() )
   {
      //the first extract simples introduced nodes at the same location that are not merged.
      //e.g. Butterfly polygons as two seperate polygons.
      //The scanlines can not cope with this, so merge them, and later extract one more time.
      Merge_NodeToNode(0);

      _GC->Write_Log("LINKHOLES\n");
      writegraph( false );

      //link the holes into the non holes if there are any.
      bool holes = false; 
      ScanGraph2(LINKHOLES, holes );

      WriteGraphKEY(_GC);
      writegraph(true);
      if ( holes )
      {
		   //to delete extra points
		   //those extra points are caused by link holes
         //and are eqaul
		   DeleteZeroLines(1);

		   _GC->SetState("extract simples last");
         ResetBinMark();
         HandleNonCond(operation);
         DeleteNonCond(operation);
		   Extract_Simples(operation,false, foundholes);
      }
   }

   writegraph( true );
   Split(Result);
}

// Perform an correction on the graph
void Graph::Correction( GraphList* Result, double factor )
{
	// At this moment we have one graph
	// step one, split it up in single graphs, and mark the holes
	// step two, make one graph again and link the holes
	// step three, split up again and dump the result in Result
	_GC->SetState("Extract simple graphs");

	//extract the (MERGE or OR) result from the graph
	if (Simplify(_GC->GetGrid()))
		if (GetNumberOfLinks() < 3)
				return;

	Graph* original=new Graph(_GC);

   {
      if (_linklist->empty()) return;

      KBoolLink* _current = GetFirstLink();
		Node *_first = new Node(_current->GetBeginNode(), _GC);
      Node *_last	 = _current->GetBeginNode();
      Node *_begin = _first;
      Node *_end   = _first;

		int _nr_of_points = GetNumberOfLinks();
		for (int i = 1; i < _nr_of_points; i++)
      {
 			// get the other node on the link
			_last = _current->GetOther(_last);
        // make a node from this point
         _end = new Node(_last, _GC);

         // make a link between begin and end
         original->AddLink(_begin, _end);

         _begin=_end;
 			_current = _current->Forth(_last);
      }

      // make a link between the _begin and the first to close the graph
      original->AddLink(_begin, _first);
   }

	SetNumber(1);
	SetGroup(GROUP_A);
	Prepare(1);
   ResetBinMark();
   //DeleteNonCond(BOOL_OR);
   HandleNonCond(BOOL_OR);

   bool foundholes = false;
	Extract_Simples( BOOL_OR, true, foundholes );
   Split(Result);

	//Result contains the separate boundaries and holes

   //ring creation should never be alternate rule, since it overlaps.
   //So temprarely modify it.
   bool rule = _GC->GetWindingRule();
   _GC->SetWindingRule( true );

	_GC->SetState("Create rings");
	//first create a ring around all simple graphs
   {
     	TDLI<Graph> IResult=TDLI<Graph>(Result);
      GraphList *_ring = new GraphList(_GC);
      {
         //put into one graphlist
         IResult.tohead();
         int i;
         int n=IResult.count();
         for (i=0;i<n;i++)
         {
           {
				  IResult.item()->MakeClockWise();
              IResult.item()->CreateRing_fast(_ring,fabs(factor));
      //			  IResult.item()->CreateRing(_ring,fabs(factor));
           }
           delete(IResult.item());
           IResult.remove();

            //move ring graphlist to result
            while (!_ring->empty())
            {
               //add to end
					((Graph*)_ring->headitem())->MakeClockWise();
               IResult.insend((Graph*)_ring->headitem());
               _ring->removehead();
            }
         }
      }
      delete _ring;

      //IResult contains all rings
      //prepare the graphs for extracting the links of a certain operation
      //set original graphlist to groupA and ring to groupB
      int i=2;
      IResult.tohead();
      while (!IResult.hitroot())
      {
        IResult.item()->Reset_flags();
        IResult.item()->SetGroup(GROUP_B);
        IResult.item()->SetNumber(i);
        i++;
        IResult++;
      }
   }

   //a ring shape can overlap itself, for alternate filling this is problem. 
   //doing a merge in winding rule makes this oke, since overlap is removed by it.
   if ( !rule ) //alternate rule? 
   {
      Prepare(1);
      Boolean(BOOL_OR,Result);

     	TDLI<Graph> IResult=TDLI<Graph>(Result);
      //IResult contains all rings
      //prepare the graphs for extracting the links of a certain operation
      //set original graphlist to groupA and ring to groupB
      int i=2;
      IResult.tohead();
      while (!IResult.hitroot())
      {
        IResult.item()->Reset_flags();
        IResult.item()->SetGroup(GROUP_B);
        IResult.item()->SetNumber(i);
        i++;
        IResult++;
      }
   }

   //restore filling rule
   _GC->SetWindingRule( rule );

	TakeOver(original);
   Reset_flags();
   SetNumber(1);
   SetGroup(GROUP_A);
	Result->MakeOneGraph(this); // adds all graph its links to original
										  // Result will be empty afterwords


	//merge ring with original shapes for positive correction else subtract ring

	//calculate intersections etc.
	//SINCE correction will calculate intersections between
	//ring and original _GC->Get_Marge() must be set a lot smaller then factor
	//during the rest of this routine
	//else wierd effects will be the result.
	double Backup_Marge = _GC->GetMarge();

	if (_GC->GetInternalMarge() > fabs(factor/100))
	{
      _GC->SetInternalMarge( (B_INT) fabs(factor/100));
	   //less then 1 is usless since all coordinates are integers
	   if (_GC->GetInternalMarge() < 1)
		   _GC->SetInternalMarge(1);
	}


	Prepare(1);

	_GC->SetState("Add/Substract rings");

	if (factor > 0)
		Boolean(BOOL_OR,Result);
	else
		Boolean(BOOL_A_SUB_B,Result);

	_GC->SetMarge( Backup_Marge);

	//the result of the graph correction is in Result
   delete original;
}

// Perform an operation on the graph
void Graph::MakeRing( GraphList* Result, double factor )
{

   bool rule = _GC->GetWindingRule();
   _GC->SetWindingRule( true );

	// At this moment we have one graph
	// step one, split it up in single graphs, and mark the holes
	// step two, make one graph again and link the holes
	// step three, split up again and dump the result in Result
	_GC->SetState("Extract simple graphs");

	//extract the (MERGE or OR) result from the graph
	SetNumber(1);
	Prepare(1);

   ResetBinMark();
   //DeleteNonCond(BOOL_OR);
   HandleNonCond(BOOL_OR);

   bool foundholes = false;
	Extract_Simples( BOOL_OR, true, foundholes );
   Split(Result);
	//Iresult contains the separate boundaries and holes
	//make a correction on the boundaries factor
	//make a correction on the holes -factor

	_GC->SetState("Create rings");

   //first create a ring around all simple graphs
   TDLI<Graph> IResult=TDLI<Graph>(Result);
   GraphList *_ring = new GraphList(_GC);
   {
      IResult.tohead();
      int i;
      int n=IResult.count();
      for (i=0;i<n;i++)
      {
        {
  			   IResult.item()->MakeClockWise();
            IResult.item()->CreateRing_fast(_ring,fabs(factor));
        }
        delete(IResult.item());
        IResult.remove();

         //move ring graphlist to result
         while (!_ring->empty())
         {
            //add to end
				((Graph*)_ring->headitem())->MakeClockWise();
            IResult.insend((Graph*)_ring->headitem());
            _ring->removehead();
         }
      }
   }
	delete _ring;
   _GC->SetWindingRule( rule );
}

//create a ring shapes on every edge of the graph
void Graph::CreateRing( GraphList *ring, double factor )
{
  TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
  _LI.tohead();
  while( !_LI.hitroot())
  {
	 Graph *shape=new Graph(_GC);
	 //generate shape around link
	 shape->Make_Rounded_Shape(_LI.item(),factor);
	 ring->insbegin(shape);
	 _LI++;
  }
}

//create a ring shapes on every edge of the graph
void Graph::CreateRing_fast( GraphList *ring, double factor )
{
	Node* begin;
	KBoolLink* currentlink;
	KBoolLine  currentline(_GC);

	KBoolLine  firstline(_GC);

	KBoolLink* nextlink;
	KBoolLine nextline(_GC);

   {
   	TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
		_LI.foreach_mf(&KBoolLink::UnMark);//reset bin and mark flag of each link
		_LI.mergesort(linkYXsorter);
	   _LI.tohead();

		begin = GetMostTopLeft(&_LI); // from all the most Top nodes,
											   // take the most left one
   }
	if (!begin)
		return;

	currentlink=begin->GetIncomingLink();
	currentline.Set(currentlink);
	currentline.CalculateLineParameters();

	nextlink=begin->GetOutgoingLink();
	nextline.Set(nextlink);
	nextline.CalculateLineParameters();

	firstline.Set(nextlink);
	firstline.CalculateLineParameters();

	while (nextlink)
	{
		Graph *shape=new Graph(_GC);
		{

			Node* _last_ins_left  =0;
			Node* _last_ins_right =0;

			currentline.Create_Begin_Shape(&nextline,&_last_ins_left,&_last_ins_right,factor,shape);

			while(true)
			{
				currentline=nextline;
				currentlink=nextlink;
				currentlink->SetBeenHere();

				nextlink=currentlink->GetEndNode()->Follow(currentlink);
				if (nextlink)
				{
					nextline.Set(nextlink);
					nextline.CalculateLineParameters();
					if (!currentline.Create_Ring_Shape(&nextline,&_last_ins_left,&_last_ins_right,factor,shape))
						break;
				}
				else
					break;
			}

			//finish this part
			if (nextlink)
				currentline.Create_End_Shape(&nextline,_last_ins_left,_last_ins_right,factor,shape);
			else
				currentline.Create_End_Shape(&firstline,_last_ins_left,_last_ins_right,factor,shape);

			shape->MakeOneDirection();
  			shape->MakeClockWise();
		}

		//if the shape is very small first merge it with the previous shape
		if (!ring->empty() && shape->Small( (B_INT) fabs(factor*3)))
		{
		   TDLI<Graph> Iring = TDLI<Graph>(ring);

			Iring.totail();

			GraphList *_twoshapes=new GraphList(_GC);
			_twoshapes->insbegin(shape);
			_twoshapes->insbegin(Iring.item());
			Iring.remove();
			_twoshapes->Merge();

			//move merged graphlist to ring
			Iring.takeover(_twoshapes);
			delete _twoshapes;
		}
		else
			ring->insend(shape);

		currentlink->SetBeenHere();
   }