graph.cpp

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

}

//create an arc and add it to the graph
//center of circle
//begin point of arc
//end point of arc
//radius of arc
//aberation for generating the segments
void Graph::CreateArc(Node* center, Node* begin, Node* end,double radius,bool clock,double aber)
{
	double phi,dphi,dx,dy;
	int Segments;
	int i;
	double ang1,ang2,phit;

	Node* _last_ins;
	Node* _current;

	_last_ins=begin;

	dx = (double) _last_ins->GetX() - center->GetX();
	dy = (double) _last_ins->GetY() - center->GetY();
	ang1=atan2(dy,dx);
	if (ang1<0) ang1+=2.0*M_PI;
	dx = (double) end->GetX() - center->GetX();
	dy = (double) end->GetY() - center->GetY();
	ang2=atan2(dy,dx);
	if (ang2<0) ang2+=2.0*M_PI;

	if (clock)
	{ //clockwise
		if (ang2 > ang1)
			phit=2.0*M_PI-ang2+ ang1;
		else
			phit=ang1-ang2;
	}
	else
	{ //counter_clockwise
		if (ang1 > ang2)
			phit=-(2.0*M_PI-ang1+ ang2);
		else
			phit=-(ang2-ang1);
	}

	//what is the delta phi to get an accurancy of aber
	dphi=2*acos((radius-aber)/radius);

	//set the number of segments
	if (phit > 0)
		Segments=(int)ceil(phit/dphi);
	else
		Segments=(int)ceil(-phit/dphi);

	if (Segments <= 1)
	  Segments=1;
	if (Segments > 6)
	  Segments=6;

	dphi=phit/(Segments);

	for (i=1; i<Segments; i++)
	{
	  dx = (double) _last_ins->GetX() - center->GetX();
	  dy = (double) _last_ins->GetY() - center->GetY();
	  phi=atan2(dy,dx);

	  _current = new Node((B_INT) (center->GetX() + radius * cos(phi-dphi)),
								 (B_INT) (center->GetY() + radius * sin(phi-dphi)), _GC);
	  AddLink(_last_ins, _current);

	  _last_ins=_current;
	}

	// make a node from the endnode of link
	AddLink(_last_ins, end);
}

void Graph::CreateArc(Node* center, KBoolLine* incoming, Node* end,double radius,double aber)
{
	double distance=0;
	if (incoming->PointOnLine(center, distance, _GC->GetAccur()) == RIGHT_SIDE)
		CreateArc(center,incoming->GetEndNode(),end,radius,true,aber);
	else
		CreateArc(center,incoming->GetEndNode(),end,radius,false,aber);
}

void Graph::MakeOneDirection()
{
	int _nr_of_points = _linklist->count();
	KBoolLink* _current = (KBoolLink*)_linklist->headitem();

	Node* _last = _current->GetBeginNode();
	Node* dummy;

	for (int i = 0; i < _nr_of_points; i++)
	{
		// get the other node on the link
		_last = _current->GetOther(_last);
		// get the other link on the node
		_current = _current->Forth(_last);

		if (_current->GetBeginNode() != _last)
		{
			// swap the begin- and endnode of the current link
			dummy = _current->GetBeginNode();
			_current->SetBeginNode(_current->GetEndNode());
			_current->SetEndNode(dummy);
		}
	}
}

bool Graph::Small(B_INT howsmall)
{

   TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	_LI.tohead();
   Node* bg=_LI.item()->GetBeginNode();
   B_INT xmin=bg->GetX();
   B_INT xmax=bg->GetX();
   B_INT ymin=bg->GetY();
   B_INT ymax=bg ->GetY();
	while (!_LI.hitroot())
	{
     bg=_LI.item()->GetBeginNode();
     // make _boundingbox bigger if the link makes the graph bigger
	  // Checking if point is in bounding-box with marge
     xmin=bmin(xmin,bg->GetX());
     xmax=bmax(xmax,bg->GetX());
     ymin=bmin(ymin,bg->GetY());
     ymax=bmax(ymax,bg->GetY());
	  _LI++;
	}

	B_INT dx=(xmax-xmin);
	B_INT dy=(ymax-ymin);

	if ((dx < howsmall) && (dy < howsmall) )
      return true;

	return false;
}


//create a circle at end and begin point
// and block in between
void	Graph::Make_Rounded_Shape( KBoolLink* a_link, double factor)
{
	double phi,dphi,dx,dy;
	int Segments=6;
	int i;


	KBoolLine theline(a_link, _GC);
	theline.CalculateLineParameters();

	Node* _current;
	Node *_first = new Node(a_link->GetBeginNode(), _GC);
	Node *_last_ins = _first;

	theline.Virtual_Point(_first,factor);

	// make a node from this point
	_current = new Node(a_link->GetEndNode(), _GC);
	theline.Virtual_Point(_current,factor);

	// make a link between the current and the previous and add this to graph
	AddLink(_last_ins, _current);
	_last_ins=_current;

	// make a half circle around the clock with the opposite point as
	// the middle point of the circle
	dphi=M_PI/(Segments);
	for (i=1; i<Segments; i++)
	{
	  dx = (double) _last_ins->GetX() - a_link->GetEndNode()->GetX();
	  dy = (double) _last_ins->GetY() - a_link->GetEndNode()->GetY();
	  phi=atan2(dy,dx);

	  _current = new Node((B_INT) (a_link->GetEndNode()->GetX() + factor * cos(phi-dphi)),
								 (B_INT) (a_link->GetEndNode()->GetY() + factor * sin(phi-dphi)), _GC);

	  AddLink(_last_ins, _current);

	  _last_ins=_current;
	}

	// make a node from the endnode of link
	_current = new Node(a_link->GetEndNode(), _GC);
	theline.Virtual_Point(_current,-factor);
	AddLink(_last_ins, _current);
	_last_ins=_current;

	// make a node from this beginnode of link
	_current = new Node(a_link->GetBeginNode(), _GC);
	theline.Virtual_Point(_current,-factor);
	AddLink(_last_ins, _current);
	_last_ins=_current;

	for (i=1; i<Segments; i++)
	{
	  dx = (double) _last_ins->GetX() - a_link->GetBeginNode()->GetX();
	  dy = (double) _last_ins->GetY() - a_link->GetBeginNode()->GetY();
	  phi=atan2(dy,dx);

	  _current = new Node((B_INT)(a_link->GetBeginNode()->GetX() + factor * cos(phi-dphi)),
								 (B_INT)(a_link->GetBeginNode()->GetY() + factor * sin(phi-dphi)), _GC);

	  AddLink(_last_ins, _current);

	  _last_ins=_current;
	}

	// make a link between the last and the first to close the graph
	AddLink(_last_ins, _first);
};

//make the graph clockwise orientation,
//return if the graph needed redirection
bool Graph::MakeClockWise()
{
   if ( _GC->GetOrientationEntryMode() )
      return false;

	TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	if (_LI.empty()) return false;

	KBoolLink *currentlink;
	Node *begin;

	_LI.foreach_mf(&KBoolLink::UnMark);//reset bin and mark flag of each link
	_LI.mergesort(linkYXtopsorter);
   _LI.tohead();

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

	currentlink=begin->GetNotFlat();
	if (!currentlink)
   {
      char buf[100];
	   sprintf(buf,"no NON flat link MakeClockWise at %15.3lf , %15.3lf",
         				double(begin->GetX()),double(begin->GetY()));
		throw Bool_Engine_Error(buf, "Error", 9, 0);
	}

   //test to see if the orientation is right or left
   if (currentlink->GetBeginNode() == begin)
   {
      if ( currentlink->GetEndNode()->GetX() < begin->GetX())
      {
	      //going left
         //it needs redirection
         ReverseAllLinks();
         return true;
      }
   }
   else
   {
      if ( currentlink->GetBeginNode()->GetX() > begin->GetX())
      {  //going left
			//it needs redirection
         ReverseAllLinks();
         return true;
      }
   }
   return false;
}

bool Graph::writegraph(bool linked )
{
#if KBOOL_DEBUG == 1

   FILE* file = _GC->GetLogFile();

   if (file == NULL)
       return true;

	fprintf( file, "# graph\n" );

	TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	if (_LI.empty())
   {  
		return true;
   }

   _LI.tohead();
   while(!_LI.hitroot())
   {
	   KBoolLink* curl = _LI.item();

      fprintf( file, " linkbegin %I64d %I64d \n", curl->GetBeginNode()->GetX() , curl->GetBeginNode()->GetY() );

		if (linked)
      {
			TDLI<KBoolLink> Inode(curl->GetBeginNode()->GetLinklist());
         Inode.tohead();
		   while(!Inode.hitroot())
   		{

            fprintf( file, " b %I64d %I64d \n", Inode.item()->GetBeginNode()->GetX() , Inode.item()->GetBeginNode()->GetY() );

            fprintf( file, " e %I64d %I64d \n", Inode.item()->GetEndNode()->GetX() , Inode.item()->GetEndNode()->GetY() );

            Inode++;
         }
      }
      fprintf( file, " linkend %I64d %I64d \n", curl->GetEndNode()->GetX() , curl->GetEndNode()->GetY() );


      if (linked)
      {
			TDLI<KBoolLink> Inode(curl->GetEndNode()->GetLinklist());
         Inode.tohead();
		   while(!Inode.hitroot())
   		{

            fprintf( file, " b %I64d %I64d \n", Inode.item()->GetBeginNode()->GetX() , Inode.item()->GetBeginNode()->GetY() );

            fprintf( file, " e %I64d %I64d \n", Inode.item()->GetEndNode()->GetX() , Inode.item()->GetEndNode()->GetY() );

            Inode++;
         }

      }

      if ( curl->GetBeginNode() == curl->GetEndNode() )
		   fprintf( file, "     null_link \n" );

	   fprintf( file, "    group %d ", curl->Group() );
	   fprintf( file, "    bin   %d ", curl->BeenHere() );
	   fprintf( file, "    mark  %d ", curl->IsMarked() );
	   fprintf( file, "    leftA %d ", curl->GetLeftA() );
	   fprintf( file, "    rightA %d ", curl->GetRightA() );
	   fprintf( file, "    leftB %d ", curl->GetLeftB() );
	   fprintf( file, "    rightB %d \n", curl->GetRightB() );
	   fprintf( file, "    or %d ", curl->IsMarked(BOOL_OR) );
	   fprintf( file, "    and %d " , curl->IsMarked(BOOL_AND) );
	   fprintf( file, "    exor %d " , curl->IsMarked(BOOL_EXOR) );
	   fprintf( file, "    a_sub_b %d " , curl->IsMarked(BOOL_A_SUB_B) );
	   fprintf( file, "    b_sub_a %d " , curl->IsMarked(BOOL_B_SUB_A) );
	   fprintf( file, "    hole %d " , curl->GetHole() );
	   fprintf( file, "    top_hole %d \n" , curl->IsTopHole() );
      
      _LI++;
   }

#endif

   return true;
}

bool Graph::writeintersections()
{

#if KBOOL_DEBUG == 1

   FILE* file = _GC->GetLogFile();

   if (file == NULL)
       return true;

   fprintf( file, "# graph\n" );

	TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	if (_LI.empty())
   {  
		return true;
   }

   _LI.tohead();
   while(!_LI.hitroot())
   {
	   KBoolLink* curl=_LI.item();
      TDLI<KBoolLink> Inode(curl->GetBeginNode()->GetLinklist());
      Inode.tohead();
      if (Inode.count() > 2)
      {
         fprintf( file, " count %I64d", Inode.count() );
         fprintf( file, " b %I64d %I64d \n\n", curl->GetBeginNode()->GetX() , curl->GetBeginNode()->GetY() );
      }
      _LI++;
   }
#endif

   return true;
}

bool Graph::checksort()
{
	// if empty then just insert
	if (_linklist->empty())
		return true;

	TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
   // put new item left of the one that is bigger
   _LI.tohead();
   KBoolLink* prev=_LI.item();
   KBoolLink* cur=_LI.item();
   _LI++;
   while(!_LI.hitroot())
   {
      KBoolLink* aap=_LI.item();
      if (linkXYsorter(prev,_LI.item())==-1)
      {
         cur=aap;

         return false;
      }
      prev=_LI.item();
      _LI++;
   }
   return true;
}


void Graph::WriteKEY( Bool_Engine* GC, FILE* file )
{
   double scale = 1.0/GC->GetGrid()/GC->GetGrid();

   bool ownfile = false;
   if ( !file )
   {
      file = fopen("keyfile.key", "w");
      ownfile = true;

      fprintf(file,"\
         HEADER 5; \
         BGNLIB; \
         LASTMOD {2-11-15  15:39:21}; \
         LASTACC {2-11-15  15:39:21}; \
         LIBNAME trial; \
         UNITS; \
         USERUNITS 0.0001; PHYSUNITS 1e-009; \
      \
         BGNSTR;  \
         CREATION {2-11-15  15:39:21}; \
         LASTMOD  {2-11-15  15:39:21}; \
         STRNAME top; \
      ");
   }

	TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	if (_LI.empty())
   {  
      if ( ownfile )
      {
         fprintf(file,"\
            ENDSTR top; \
            ENDLIB; \
         ");
         fclose (file);

      }
		return;
   }


   _LI.tohead();
   KBoolLink* curl = _LI.item();

	if ( _LI.item()->Group() == GROUP_A )
      fprintf(file,"BOUNDARY; LAYER 0;  DATATYPE 0;\n");
   else
      fprintf(file,"BOUNDARY; LAYER 1;  DATATYPE 0;\n");
   fprintf(file," XY %d; \n", _LI.count()+1 );

   double firstx = curl->GetBeginNode()->GetX()*scale;
   double firsty = curl->GetBeginNode()->GetY()*scale;
   fprintf(file,"X %f;\t", firstx);
   fprintf(file,"Y %f; \n", firsty); 
   _LI++;

   while(!_LI.hitroot())
   {
	   KBoolLink* curl = _LI.item();

      fprintf(file,"X %f;\t", curl->GetBeginNode()->GetX()*scale);
      fprintf(file,"Y %f; \n", curl->GetBeginNode()->GetY()*scale); 
      
      _LI++;
   }
   fprintf(file,"X %f;\t", firstx);
   fprintf(file,"Y %f; \n", firsty); 
   fprintf(file,"ENDEL;\n");

   if ( ownfile )
   {
      fprintf(file,"\
         ENDSTR top; \
         ENDLIB; \
      ");
      fclose (file);

   }
}
 

void Graph::WriteGraphKEY(Bool_Engine* GC)
{
#if KBOOL_DEBUG == 1

   double scale = 1.0/GC->GetGrid()/GC->GetGrid();

   FILE* file = fopen("keygraphfile.key", "w");

   fprintf(file,"\
      HEADER 5; \
      BGNLIB; \
      LASTMOD {2-11-15  15:39:21}; \
      LASTACC {2-11-15  15:39:21}; \
      LIBNAME trial; \
      UNITS; \
      USERUNITS 1; PHYSUNITS 1e-006; \
   \
      BGNSTR;  \