graph.cpp

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

/*! \file ../src/graph.cpp
    \brief Used to Intercect and other process functions
    \author Probably Klaas Holwerda 

    Copyright: 2001-2004 (C) Probably Klaas Holwerda

    Licence: wxWidgets Licence

    RCS-ID: $Id: graph.cpp,v 1.13 2005/06/17 22:42:58 kbluck Exp $
*/

// Grpah is the structure used to store polygons

#ifdef __GNUG__
#pragma implementation 
#endif

#include <math.h>
#include <assert.h>

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

// Prototype of function
int linkXYsorter(KBoolLink *, KBoolLink *);
int linkYXsorter(KBoolLink *, KBoolLink *);
int linkLsorter(KBoolLink *, KBoolLink *);
int linkYXtopsorter(KBoolLink *a, KBoolLink *b);
int linkGraphNumsorter(KBoolLink *_l1, KBoolLink* _l2);

// constructor, initialize with one link
// usage: Graph *a_graph = new Graph(a_link);
Graph::Graph(KBoolLink *a_link, Bool_Engine* GC )
{
   _GC = GC;
	_linklist=new DL_List<void*>();

	_linklist->insbegin(a_link);
	_bin = false;

}


// constructor, initialize graph with no contents
// usage: Graph *a_graph = new Graph();
Graph::Graph(Bool_Engine* GC)
{
   _GC = GC;
	_linklist=new DL_List<void*>();
	_bin = false;
}

Graph::Graph( Graph* other )
{
   _GC = other->_GC;
	_linklist = new DL_List<void*>();
	_bin = false;

	int _nr_of_points = other->_linklist->count();
	KBoolLink* _current = other->GetFirstLink();

	Node* _last = _current->GetBeginNode();
	Node* node = new Node( _current->GetBeginNode()->GetX(), _current->GetBeginNode()->GetY(), _GC );
	Node* nodefirst = node;
	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 _last node
		_current = _current->Forth(_last);

   	Node* node2 = new Node( _current->GetBeginNode()->GetX(), _current->GetBeginNode()->GetY(), _GC );
      _linklist->insend( new KBoolLink( node,  node2, _GC ) );
      node = node2;
	}
   _linklist->insend( new KBoolLink( node,  nodefirst, _GC ) );
}

// destructor
// deletes all object of the linklist
Graph::~Graph()
{
   {
      TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);

      //first empty the graph
      _LI.delete_all();
   }

   delete _linklist;
}

KBoolLink*	Graph::GetFirstLink()
{
   return (KBoolLink*) _linklist->headitem();
};


void Graph::Prepare( int intersectionruns )
{
	_GC->SetState("Intersection");

   bool found = true;
   int run = 0;
   while( run < intersectionruns && found )
   {    
	   found = CalculateCrossings(_GC->GetInternalMarge());
      run++;
   }

//WHY
//	Round(_GC->Get_Grid());

   {
   	TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
		_LI.foreach_mf(&KBoolLink::UnMark);// Reset Bin and Mark flag
   }
	_GC->SetState("Set group A/B Flags");

   bool dummy = false;

   if (_GC->GetWindingRule())
	   ScanGraph2( INOUT, dummy );

   ScanGraph2( GENLR, dummy );

//	writegraph();

	_GC->SetState("Set operation Flags");
	Set_Operation_Flags();

	_GC->SetState("Remove doubles");
	// Remove the marked links
   {
   	TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
      _LI.tohead();
      while(!_LI.hitroot())
      {
         if (_LI.item()->IsMarked())
         {
            delete _LI.item();
            _LI.remove();
         }
         else
            _LI++;
      }
   }

	_GC->SetState("Remove inlinks");
	Remove_IN_Links();


	_GC->SetState("Finished prepare graph");
}



// x and y of the point will be rounded to the nearest
// xnew=N*grid and ynew=N*grid
void Graph::RoundInt(B_INT grid)
{
   TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	_LI.tohead();
	while (!_LI.hitroot())
	{
			_LI.item()->GetBeginNode()->RoundInt(grid);
			_LI.item()->GetEndNode()->RoundInt(grid);
			_LI++;
	}
}

// rotate graph minus 90 degrees or plus 90 degrees
void Graph::Rotate(bool plus90)
{
	B_INT swap;
	Node* last=NULL;

   B_INT neg=-1;
   if (plus90)
      neg=1;

   TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	_LI.mergesort(linkXYsorter);

	_LI.tohead();
	while (!_LI.hitroot())
	{
			if (_LI.item()->GetBeginNode() != last)
			{
				swap=_LI.item()->GetBeginNode()->GetX();
				_LI.item()->GetBeginNode()->SetX(-neg*(_LI.item()->GetBeginNode()->GetY()));
				_LI.item()->GetBeginNode()->SetY(neg*swap);
				last=_LI.item()->GetBeginNode();
			}
			_LI++;
	}
}

bool Graph::RemoveNullLinks()
{
	bool graph_is_modified = false;

   TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	_LI.tohead();
	while (!_LI.hitroot())
	{
		if (_LI.item()->GetBeginNode() == _LI.item()->GetEndNode())
		{
			_LI.item()->MergeNodes(_LI.item()->GetBeginNode());
			delete _LI.item();
			_LI.remove();
			graph_is_modified = true;
		}
		else
		  _LI++;
	}
	return (graph_is_modified);
}

// Add a link to the graph connection with
// other links is through the link his nodes
void Graph::AddLink(KBoolLink *a_link)
{
	assert(a_link);

	_linklist->insend(a_link);
}


// Add a link to the graph, by giving it two nodes
// the link is then made and added to the graph
void Graph::AddLink(Node *begin, Node *end)
{
	 assert(begin && end);
	 assert(begin != end);
	 AddLink(new KBoolLink(0, begin, end, _GC));
}


// Checks if there is a zeroline in the graph
bool Graph::AreZeroLines(B_INT Marge)
{
	bool Found_it = false;

   TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	_LI.tohead();
	while (!_LI.hitroot())
	{
		if (_LI.item()->IsZero(Marge))
		{
			Found_it = true;
			break;
		}
		_LI++;
	}
	return Found_it;
}


// Delete links that do not fit the condition for given operation
void Graph::DeleteNonCond(BOOL_OP operation)
{
   TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	_LI.tohead();
	while(!_LI.hitroot())
	{
		if ( !_LI.item()->IsMarked(operation))
		{
			delete _LI.item();
			_LI.remove();
		}
		else
			_LI++;
	}
}

void Graph::HandleNonCond(BOOL_OP operation)
{
   TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	_LI.tohead();
	while(!_LI.hitroot())
	{
		if ( !_LI.item()->IsMarked(operation))
      {
         _LI.item()->SetBeenHere();
         _LI.item()->SetGraphNum( -1 );
      }   
   	_LI++;
	}
}

// All lines in the graph wich have a length < _GC->Get_Marge() will be deleted
//
// input : a marge, standard on _GC->Get_Marge()
// return: true if lines in the graph are deleted
//       : false if no lines in the graph are deleted
bool Graph::DeleteZeroLines(B_INT Marge)
{
	// Is the graph modified ?
	bool Is_Modified = false;
   TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);

	int Processed = _LI.count();

	_LI.tohead();
	while (Processed > 0)
	{
		Processed--;
		if (_LI.item()->IsZero(Marge))
		{
			// the current link is zero, so make from both nodes one node
			// and delete the current link from this graph
			_LI.item()->MergeNodes(_LI.item()->GetBeginNode());
			// if an item is deleted the cursor of the list is set to the next
			// so no explicit forth is needed
			delete _LI.item();
			_LI.remove();
			// we have to set Processed, because if a zero line is deleted
			// another can be made zero by this deletion
			Processed = _LI.count();
			Is_Modified = true;
			if (_LI.hitroot())
				_LI.tohead();
		}
		else
			_LI++;
			if (_LI.hitroot())
				_LI.tohead();
	}
	return Is_Modified;
}


// Collects a graph starting at currentnode or attached link
// follow graphs right around.
// since the input node is always a topleft node, we can see on
// a connected link if we or dealing with a hole or NON hole.
// for instance a top link of a hole that is horizontal, always
// is IN above the link and OUT underneath the link.
// this for a non hole the opposite
void Graph::CollectGraph(Node *current_node,BOOL_OP operation, bool detecthole,int graphnumber, bool& foundholes )
{
	KBoolLink *currentlink;
	KBoolLink *nextlink;
	Node *next_node;
	Node *MyFirst;
	Node *Unlinked;
	KBoolLink *MyFirstlink;

	bool Hole;
	LinkStatus whatside;

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

	currentlink->SetBeenHere();

   if (detecthole)
		Hole = currentlink->IsHole(operation);
   else
      Hole = currentlink->GetHole(); //simple extract do not detect holes, but use hole flag.

   currentlink->Redirect(current_node);

   foundholes = Hole || foundholes;

	//depending if we have a hole or not
	//we take the left node or right node from the selected link (currentlink)
	//this MEANS for holes go left around and for non holes go right around
   //since the currentlink is already set to binhere, it will not go in that direction
	if (Hole)
	{
      whatside = IS_LEFT;
	   if ( currentlink->GetEndNode()->GetX() > current_node->GetX())
		   current_node=currentlink->GetEndNode();
	}
	else
	{
      whatside = IS_RIGHT;
	   if ( currentlink->GetEndNode()->GetX() < current_node->GetX())
			current_node=currentlink->GetEndNode();
	}
   currentlink->Redirect(current_node);
   MyFirst=current_node; //remember this as the start
   MyFirstlink=currentlink;

	next_node = currentlink->GetEndNode();

	// If this is a hole, Set as special link, this is the top link of this hole !
	// from this link we have to make links to the link above later on.
	if (Hole)
		currentlink->SetTopHole(true);
   //set also the link as being part of a hole
   if (detecthole)
		currentlink->SetHole(Hole);
	currentlink->SetGraphNum(graphnumber);

	// Walk over links and redirect them. taking most right links around
	while (currentlink != NULL)
	{
      if ( Hole )
      {
         nextlink = next_node->GetMost(currentlink, IS_RIGHT, operation);
      }
      else
      {
         nextlink = next_node->GetMost(currentlink, IS_LEFT, operation);
         // next works too if same is used in CollectGraphLast
         //nextlink = next_node->GetMost(currentlink, IS_RIGHT, operation);
      }

		if (nextlink == NULL)
		{	//END POINT MUST BE EQAUL TO BEGIN POINT
			if (!next_node->Equal(MyFirst, 1))
			{
            throw Bool_Engine_Error("no next (endpoint != beginpoint)","graph", 9, 0);

          //for god sake try this
				  //nextlink = next_node->GetMost(currentlink, whatside ,operation);
			}
		}

		current_node = next_node;

		if (nextlink!=NULL)
		{
		   nextlink->Redirect(current_node);
			nextlink->SetBeenHere();
			next_node = nextlink->GetEndNode();

         if ( current_node->GetNumberOfLinks() > 2)
         {  // replace endnode of currentlink and beginnode of nextlink with new node
            Unlinked = new Node(current_node, _GC);
				currentlink->Replace(current_node,Unlinked);
				nextlink->Replace(current_node,Unlinked);
         }

		   if (detecthole)
				nextlink->SetHole(Hole);
			nextlink->SetGraphNum(graphnumber);
		}
      else
      {
         //close the found graph properly
         if ( current_node->GetNumberOfLinks() > 2)
         {  // replace endnode of currentlink and beginnode of nextlink with new node
            Unlinked = new Node(current_node, _GC);
            currentlink->Replace(current_node,Unlinked);
            MyFirstlink->Replace(current_node,Unlinked);
         }
      }

		currentlink = nextlink;
	}

	//END POINT MUST BE EQAUL TO BEGIN POINT
	if (!current_node->Equal(MyFirst, 1))
   {
      throw Bool_Engine_Error("in collect graph endpoint != beginpoint", "Error", 9, 0);
   }
}

void Graph::CollectGraphLast(Node *current_node,BOOL_OP operation, bool detecthole,int graphnumber, bool& foundholes )
{
	KBoolLink *currentlink;
	KBoolLink *nextlink;
	Node *next_node;
	Node *MyFirst;
	Node *Unlinked;
	KBoolLink *MyFirstlink;

	bool Hole;
	LinkStatus whatside;

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

	currentlink->SetBeenHere();

   if (detecthole)
		Hole = currentlink->IsHole(operation);
   else
      Hole = currentlink->GetHole(); //simple extract do not detect holes, but use hole flag.

   currentlink->Redirect(current_node);

   foundholes = Hole || foundholes;

	//depending if we have a hole or not
	//we take the left node or right node from the selected link (currentlink)
	//this MEANS for holes go left around and for non holes go right around
   //since the currentlink is already set to binhere, it will not go in that direction
	if (Hole)
	{