graph.cpp

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

      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);
	currentlink->SetGraphNum(graphnumber);

	// Walk over links and redirect them. taking most right links around
	while (currentlink != NULL)
	{
      if ( Hole )
      {
         if ( currentlink->GetHoleLink() )
         {
            //in case we entered the hole via the hole link just now, we followe the hole.
            //This is taking as many holes as possible ( most right around)
            nextlink = next_node->GetMostHole(currentlink, IS_RIGHT ,operation );
            if ( !nextlink ) // hole done?
               //if we did get to this hole via a holelink?, then we might now be on the return link.
               //BTW it is also possible that holes are already found via a non linked hole path,
               //in that case, we did go to the HoleLink here, and directly return on the other holelink. 
   		      nextlink = next_node->GetHoleLink(currentlink, true, operation );
            if ( !nextlink )
            {
               //we did get to this hole via a holelink and we are on the returning holelink.
               //So we left the hole collection, and continue with contours.
               //Most Right is needed!
               nextlink = next_node->GetMost(currentlink, IS_RIGHT, operation);
            }
         }
         else
         {
 		      nextlink = next_node->GetHoleLink(currentlink, true, operation ); // other linked holes first
            if ( !nextlink ) 
               nextlink = next_node->GetMostHole(currentlink, IS_RIGHT, operation ); // other holes first
            if ( !nextlink ) 
            {
               //We are leaving the hole.
               //So we left the hole collection, and continue with contours.
               //Most Right is needed!
               nextlink = next_node->GetMost(currentlink, IS_RIGHT, operation);
            }
         }
      }
      else
      {

         //a hole link is preferred above a normal link. If not no holes would be linked in anyway.
         nextlink = next_node->GetHoleLink(currentlink, true, operation );
         if ( !nextlink )
            //also if we can get to a hole directly within a contour, that is better (get as much as possible)
            nextlink = next_node->GetMostHole(currentlink, IS_RIGHT, operation);
         if ( !nextlink )
            //if non of the above, we are still on the contour and take as must as possible to the left.
            //Like that we take as many contour togethere as possible.

            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);
			}
		}
      else
      {
         // when holes are already know, use the hole information to
         // go left are right around.
         Hole = nextlink->GetHole() || nextlink->GetHoleLink();
      }
		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);
         }

			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);
   }
}
//==============================================================================
//==============================================================================

// Extract bi-directional graphs from this graph
// Mark the graphs also as being a hole or not.
void Graph::Extract_Simples(BOOL_OP operation, bool detecthole, bool& foundholes )
{
	TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	if (_LI.empty()) return;
	Node *begin;
   int graphnumber=1;

	_LI.mergesort(linkYXtopsorter);
   _LI.tohead();
	while (true)
	{
		begin = GetMostTopLeft(&_LI); // from all the most Top nodes,
												// take the most left one
												// to most or not to most, that is the question
		if (!begin)
			break;

		try // collect the graph
		{
         if ( detecthole )
				CollectGraph( begin,operation,detecthole,graphnumber++, foundholes );
         else 
				//CollectGraph( begin,operation,detecthole,graphnumber++, foundholes );
				CollectGraphLast( begin,operation,detecthole,graphnumber++, foundholes );
		}
		catch (Bool_Engine_Error& error)
		{
			_GC->info(error.GetErrorMessage(), "error");
			throw error;
		}
	}
}

void Graph::Split(GraphList* partlist)
{
  TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
  if (_LI.empty()) return;

  Graph *part = NULL;
  int graphnumber=0;

  //sort the graph on graphnumber
  _LI.mergesort(linkGraphNumsorter);

  _LI.tohead();
  while (!_LI.hitroot())
  {
    if ( _LI.item()->GetGraphNum() > 0 && graphnumber != _LI.item()->GetGraphNum())
    {
      graphnumber=_LI.item()->GetGraphNum();
      part = new Graph(_GC);
      partlist->insend(part);
    }
    KBoolLink* tmp=_LI.item();
    if ( _LI.item()->GetGraphNum() > 0 )
    {
      part->AddLink(tmp);
    }
    else
    {
      delete tmp; 
    }
    _LI.remove();
	}
}

bool Graph::GetBeenHere()
{
	return _bin;
}

// return total number of links in this graph
int Graph::GetNumberOfLinks()
{
   TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	return _LI.count();
}

//for all operations set the operation flags for the links
//based on the Group_Left_Right values
void Graph::Set_Operation_Flags()
{
   TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	_LI.tohead();
	while(!_LI.hitroot())
	{
	  _LI.item()->SetLineTypes();
	  _LI++;
	}
}

//  Remove unused (those not used for any operation) links
void Graph::Remove_IN_Links()
{
   TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	_LI.tohead();
	for (int t = _LI.count() ; t > 0; t--)
	{
		// Is this link not used for any operation?
		if (_LI.item()->IsUnused())
		{
			delete _LI.item();
			_LI.remove();
		}
		else
			_LI++;
	}
}

void Graph::ResetBinMark()
{
	TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	if (_LI.empty()) return;
	_LI.foreach_mf(&KBoolLink::UnMark);//reset bin and mark flag of each link
}

void Graph::ReverseAllLinks()
{
	Node *dummy;
   TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	_LI.tohead();
	while (!_LI.hitroot())
	{
		// swap the begin- and endnode of the current link
		dummy = _LI.item()->GetBeginNode();
		_LI.item()->SetBeginNode(_LI.item()->GetEndNode());
		_LI.item()->SetEndNode(dummy);
		_LI++;
	}
}

void Graph::SetBeenHere(bool value)
{
	_bin=value;
}

// ReSet the flags  of the links
void Graph::Reset_flags()
{
   TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	_LI.foreach_mf(&KBoolLink::Reset_flags);
}

// ReSet the bin and mark flag of the links
void Graph::Reset_Mark_and_Bin()
{
   TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	_LI.foreach_mf(&KBoolLink::UnMark);//reset bin and mark flag of each link
}

// Set the group of the links to the same as newgroup
void Graph::SetGroup(GroupType newgroup)
{
   TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	_LI.tohead();
	while (!_LI.hitroot())
	{
		_LI.item()->SetGroup(newgroup);
		_LI++;
	}
}


// Set the number of the links to the same as newnr
void Graph::SetNumber(const int newnr)
{
   TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	_LI.tohead();
	while (!_LI.hitroot())
	{
		_LI.item()->SetGraphNum(newnr);
		_LI++;
	}
}


// This function will simplify a graph with the following rules
//
// This are the rules for symplifying the graphs
// 1. The following point is the same as the current one
// 2. The point after the following point is the same as the current one
// 3. The point after the following point lies on the same line as the current
//
// input : a marge
// return: true if graph is modified
// 		: false if graph is NOT simplified
bool Graph::Simplify( B_INT Marge )
{
	bool graph_is_modified = false;
   TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	int Processed = _LI.count();

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

	_LI.tohead();
	GroupType mygroup=_LI.item()->Group();

	// All items must be processed
	while (Processed > 0)
	{
		// Gives the number of items to process
		Processed--;
		// Check if line is marked
		// Links will be marked during the process
		if (_LI.item()->IsMarked())
		{
			delete _LI.item();
			_LI.remove();
			graph_is_modified = true;
			Processed = _LI.count();
			if (_LI.hitroot())
				_LI.tohead();
			continue;
		}

		// Line is not marked, check if line is zero
		if (_LI.item()->IsZero(Marge))
		{
			_LI.item()->MergeNodes(_LI.item()->GetBeginNode());
			delete _LI.item();
			_LI.remove();
			graph_is_modified = true;
			Processed = _LI.count();
			if (_LI.hitroot())
				_LI.tohead();
			continue;
		}

		// begin with trying to simplify the link
		{
			// Line is not marked, not zero, so maybe it can be simplified
			bool virtual_link_is_modified;
			Node *new_begin, *new_end, *a_node;
			KBoolLink *a_link;

			_LI.item()->Mark();
			new_begin = _LI.item()->GetBeginNode();
			new_end   = _LI.item()->GetEndNode();

			// while virtual link is modified
			do
			{
				virtual_link_is_modified = false;
				// look in the previous direction
				if ((a_link = new_begin->GetPrevLink()) != NULL)
				{
					a_node = a_link->GetBeginNode();
					if (a_node->Simplify(new_begin,new_end,Marge))
					{
						new_begin->GetPrevLink()->Mark();
						new_begin = a_node;
						virtual_link_is_modified = true;
					}
				}
				// look in the next direction
				if ((a_link = new_end->GetNextLink()) != NULL)
				{
					a_node = a_link->GetEndNode();
					if (a_node->Simplify(new_begin,new_end,Marge))
					{
						new_end->GetNextLink()->Mark();
						new_end = a_node;
						virtual_link_is_modified = true;
					}
				}
				graph_is_modified = (bool) (graph_is_modified || virtual_link_is_modified);
			} while (virtual_link_is_modified);

			// was the link simplified
			if ((_LI.item()->GetBeginNode() != new_begin) ||
				(_LI.item()->GetEndNode() != new_end))
			{
				// YES !!!!!
				int number = _LI.item()->GetGraphNum();
				delete _LI.item();
				_LI.remove();

            if (_LI.hitroot())
               _LI.tohead();

				KBoolLink *newlink = new KBoolLink(number, new_begin, new_end, _GC);
				newlink->SetGroup(mygroup);

				_LI.insend(newlink);
				Processed = _LI.count();
				graph_is_modified = true;
				continue;
			}
			_LI.item()->UnMark();
		}	// end of try to simplify
		_LI++;
		if (_LI.hitroot())
			_LI.tohead();
	}//end while all processed

	return graph_is_modified;
}

/*
// This function will smoothen a graph with the following rules
//
// 0.	Process graphs with more than 3 links only. (while more than 3)
//		Otherwise some objects may end-up as lines or disappear completely.
// 1.
// 	a. ?  Does begin-node lay on line(prevline.beginnode,endnode)
//    	->  merge beginnode to endnode
// 	b. ?  Does end-node lay on line(beginnode,nextline.endnode)
//   		->  merge endnode to beginnode
// 2.
//		a. ?  Is distance between prevline.beginnode and endnode to short
//   		->  merge beginnode to endnode
//	 	b.	?  Is distance between beginnode and nextline.endnode to short
//   		->  merge endnode to beginnode
// 3.
//		a. ?  Does (this)beginnode lay in area of nextline
//				AND does cross-node lay on nextline
//			->   move endnode to crossing of prevline and nextline
//		b. ?  Does (this)endnode lay in area of prevline
//				AND does cross-node lay on prevline
//			->   move beginnode to crossing of prevline and nextline
// 4.
//		?  Is this link too short
//			?  Is prevline shorter than nextline
//		   Y ->  ?  Is prevlink shorter than maxlength
//					->  merge endnode to beginnode
//		   N ->  ?  Is nextlink shorter than maxlength
//					->  merge endnode to beginnode
//
//
//	Types of glitches / lines to remove :
//
//    \         /      \   		/							\         /
//		 Z---A---B	 OR 	Z-------B---A				=> 	 Z-------B
//
//	  (1)
//
//	  ----A   	C----										=>		----A-----C----
//			 \   /
//	  (2)   \ /
//		      B
//
//	  ---Z                                        		---Z
//	      \                                                \
//	  (3)  \                                                \
//	        \   B----------C--							=>          A---B----------C--
//          \ /
//           A
//
//	  --Z---A                                          --Z__
//          \                                              -__
//	  (4)     B------------C--							=>            B------------C--
//
//	linkLsorter(L1,L2)
//		ret:
//			+1		L1 <	L2
//			 0		L1 ==	L2
//			-1		L1 >	L2
//
*/
bool Graph::Smoothen( B_INT Marge )
{
   TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	if (_LI.count()<=3)	// Don't modify it
		return false;

	Node *Z, *A, *B, *C, *cross_node = new Node(_GC);
	KBoolLink *prevlink, *nextlink, *thislink;
	KBoolLine	prevline(_GC),  nextline(_GC),  thisline(_GC);
	KBoolLine	prevhelp(_GC),  nexthelp(_GC);

	KBoolLink  LZB(new Node(_GC), new Node(_GC), _GC),
			LAC(new Node(_GC), new Node(_GC), _GC);

	double distance=0;
   double prevdist,nextdist;

	bool doprev, donext;
	bool graph_is_modified = false;
	bool kill = false;	// for first instance

	_LI.tohead();
	int todo = _LI.count();