graph.cpp

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

	thislink=_LI.item();
	B = thislink->GetEndNode();
	nextlink = thislink->Forth(B);

	// Type 1
	while (todo>0)
	{
		if (kill==true)
		{
			// remove link from graph
			_LI.toitem(thislink);
			graph_is_modified = true;
			delete _LI.item();
			_LI.remove();
			kill=false;
			thislink=nextlink;
			todo--;
			if (_LI.count()<3)
				break;
		}

		A = thislink->GetBeginNode();
		B = thislink->GetEndNode();

		if (A->ShorterThan(B,1))
		{
			A->Merge(B);
			kill = true;
			continue;
		}

		Z = thislink->Forth(A)->GetBeginNode();
		C = thislink->Forth(B)->GetEndNode();
		thisline.Set(thislink);
		thisline.CalculateLineParameters();
		nextlink = thislink->Forth(B);

		if (thisline.PointInLine(Z,distance,0.0) == ON_AREA)
		{	// Z--A--B	=>		Z--B							Merge this to previous
			thislink->MergeNodes(B);	// remove A
			kill = true;
			continue;
		}
		else if (thisline.PointInLine(C,distance,0.0) == ON_AREA)
		{	// A--B--C	=>		A--C							Merge this to next
			thislink->MergeNodes(A);	//	remove B
			kill = true;
			continue;
		}

		thislink=nextlink;
		todo--;
	}

	kill=false;
	todo = _LI.count();
	_LI.mergesort(linkLsorter);
	_LI.tohead();

	while (todo>0)
	{
		if (kill==true)
		{
			delete _LI.item();
			_LI.remove();
			graph_is_modified = true;
			kill = false;
			//mergesort(linkLsorter);
			_LI.mergesort(linkLsorter);
			_LI.tohead();
			todo = _LI.count();
			if (todo<3)		// A polygon, at least, has 3 sides
				break;
		}

		// Keep this order!
		thislink = _LI.item();
		A = thislink->GetBeginNode();
		B = thislink->GetEndNode();
		prevlink = thislink->Forth(A);
		nextlink = thislink->Forth(B);
		Z = prevlink->GetBeginNode();
		C = nextlink->GetEndNode();

		if (A->ShorterThan(B,1))
		{
			A->Merge(B);
			kill = true;
			continue;
		}

		prevline.Set(prevlink);
		prevline.CalculateLineParameters();
		nextline.Set(nextlink);
		nextline.CalculateLineParameters();

		// Type 2
		if (B->ShorterThan(Z,Marge))
		{	// Z--A--B	=>		Z--B							Merge this to previous
			thislink->MergeNodes(B);	// remove A
			kill = true;
			continue;
		}
		else if (A->ShorterThan(C,Marge))
		{	// A--B--C	=>		A--C							Merge this to next
			thislink->MergeNodes(A);	//	remove B
			kill = true;
			continue;
		}


		*LZB.GetBeginNode()=*Z;
		*LZB.GetEndNode()=*B;
		*LAC.GetBeginNode()=*A;
		*LAC.GetEndNode()=*C;
		prevhelp.Set(&LZB);
		nexthelp.Set(&LAC);
		prevhelp.CalculateLineParameters();
		nexthelp.CalculateLineParameters();


		//	Type 4
		doprev = bool(prevhelp.PointInLine(A,prevdist,(double)Marge) == IN_AREA);
		donext = bool(nexthelp.PointInLine(B,nextdist,(double)Marge) == IN_AREA);
		doprev = bool(B->ShorterThan(Z,_GC->GetInternalMaxlinemerge()) && doprev);
		donext = bool(A->ShorterThan(C,_GC->GetInternalMaxlinemerge()) && donext);

		if (doprev && donext)
		{
			if (fabs(prevdist)<=fabs(nextdist))
				thislink->MergeNodes(B);	// remove A
			else
				thislink->MergeNodes(A);	// remove B

			kill = true;
			continue;
		}
		else if (doprev)
		{
			thislink->MergeNodes(B);	// remove A
			kill = true;
			continue;
		}
		else if (donext)
		{
			thislink->MergeNodes(A);	// remove B
			kill = true;
			continue;
		}


		thisline.Set(thislink);
		thisline.CalculateLineParameters();

		// Type 1
		if (thisline.PointInLine(Z,distance,0.0) == ON_AREA)
		{	// Z--A--B	=>		Z--B							Merge this to previous
			thislink->MergeNodes(B);	// remove A
			kill = true;
			continue;
		}
		else if (thisline.PointInLine(C,distance,0.0) == ON_AREA)
		{	// A--B--C	=>		A--C							Merge this to next
			thislink->MergeNodes(A);	//	remove B
			kill = true;
			continue;
		}


		// Type 3
		if (nextline.PointInLine(A,distance, (double) Marge)==IN_AREA)
		{
			if (nextline.Intersect2(cross_node,&prevline))
			{
				if (nextline.PointInLine(cross_node,distance,0.0)==IN_AREA)
				{
					B->Set(cross_node);
					thislink->MergeNodes(B);	// remove A
					kill=true;
					continue;
				}
				else
				{
					thislink->MergeNodes(A);	// remove B
					kill=true;
					continue;
				}
			}
			else
			{
				thislink->MergeNodes(A);	// remove B
				kill=true;
				continue;
			}
		}

		// Type 3
		if (prevline.PointInLine(B,distance,(double)Marge)==IN_AREA)
		{
			if (prevline.Intersect2(cross_node,&nextline))
			{
				if (prevline.PointInLine(cross_node,distance,0.0)==IN_AREA)
				{
					A->Set(cross_node);
					thislink->MergeNodes(A);	// remove B
					kill=true;
					continue;
				}
				else
				{
					thislink->MergeNodes(B);	// remove A
					kill=true;
					continue;
				}
			}
			else
			{
				thislink->MergeNodes(B);	// remove A
				kill=true;
				continue;
			}
		}

		todo--;
		_LI++;
	}	// end: while all processed

	delete cross_node;

	return graph_is_modified;
}


// Give the graphnumber of the first link in the graphlist
int Graph::GetGraphNum()
{
	return ((KBoolLink*)_linklist->headitem())->GetGraphNum();
}


// get the node with the highest Y value
Node* Graph::GetTopNode()
{
	B_INT max_Y = MAXB_INT;
	Node* result;

   TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);

	_LI.tohead();
	while (!_LI.hitroot())
	{
		if (!(_LI.item()->GetBeginNode()->GetY() < max_Y))
			 break;
		_LI++;
	}
	result = _LI.item()->GetBeginNode();

	return result;
}

// THE GRAPH MUST be SORTED before using this function
//	mergesort(linkYXtopsorter);
// Get the mostleft top node from the graph  for which the link flag is not set yet
Node*	Graph::GetMostTopLeft(TDLI<KBoolLink>* _LI)
{
	while (!_LI->hitroot())
	{
		if (!_LI->item()->BeenHere())
      {
         KBoolLink* a=_LI->item();
         //find the top node of this link (sorted on top allready)
         if (a->GetBeginNode()->GetY() > a->GetEndNode()->GetY())
				return(a->GetBeginNode());
         if (a->GetBeginNode()->GetY() < a->GetEndNode()->GetY())
   			return(a->GetEndNode());
         else
   			return(a->GetBeginNode());
      }
		(*_LI)++;
	}
	return NULL;
}

// Take the linkslist over from a other graph
// The linklist of the other graph will be empty afterwards
void Graph::TakeOver(Graph *other)
{
   TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
	_LI.takeover( other->_linklist);
}

// calculate crossing with scanbeams   
bool Graph::CalculateCrossings(B_INT Marge)
{
	// POINT <==> POINT
	_GC->SetState("Node to Node");

   bool found = false;
   bool dummy = false;

	found = Merge_NodeToNode(Marge) != 0;

	if (_linklist->count() < 3)
		  return found;

	// POINT <==> LINK
	_GC->SetState("Node to KBoolLink 0");

   found = ScanGraph2(NODELINK, dummy) != 0 || found;

	_GC->SetState("Rotate -90");
	Rotate(false);

	_GC->SetState("Node to KBoolLink -90");
   found = ScanGraph2(NODELINK, dummy) != 0 || found;

	_GC->SetState("Rotate +90");
	Rotate(true);

	// LINK <==> LINK
	_GC->SetState("intersect");

   found = ScanGraph2(LINKLINK, dummy) != 0 || found;

/*
   if (!checksort())
   { {
	   TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
		_LI.mergesort(linkXYsorter);
     }
	  writeintersections();
	  writegraph(true);
   }
*/

//	Rotate(false);
//	_GC->SetState("KBoolLink to KBoolLink -90");
//   ScanGraph2(LINKLINK);
//	Rotate(true);

   writegraph(true);

   _GC->Write_Log("Node to Node");
	_GC->SetState("Node to Node");

	found = Merge_NodeToNode(Marge) != 0 || found;
   writegraph(true);

   return found;
}

// neem de nodes die binnen de margeafstand bij elkaar liggen samen	RICHARD
int Graph::Merge_NodeToNode(B_INT Marge)
{
	//aantal punten dat verplaatst is
	int merges = 0;
   {
      TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);

      //unmark all links; markflag wordt gebruikt om aan te geven
      //of een link (eigenlijk beginnode ervan) al verwerkt is
      _LI.foreach_mf(&KBoolLink::UnMark);

      //sort links on x value of beginnode
      _LI.mergesort(linkXYsorter);

      //extra iterator voor doorlopen links in graph
      {
      TDLI<KBoolLink> 	links=TDLI<KBoolLink>(_linklist);

      Node *nodeOne, *nodeTwo;
      //verwerk alle links (alle (begin)nodes)
      for(_LI.tohead(); !_LI.hitroot(); _LI++)
      {
         nodeOne = _LI.item()->GetBeginNode();

         // link (beginnode) al verwerkt?
         if(!_LI.item()->IsMarked())
         {
            // wordt verwerkt dus markeer
            _LI.item()->Mark();

            // doorloop alle links vanaf huidige tot link buiten marge
            links.toiter(&_LI);links++;
            while (!links.hitroot())
            {
               nodeTwo = links.item()->GetBeginNode();

               // marked?
               if(!links.item()->IsMarked())
               {
                  // x van beginnode vd link binnen marge?
                  if(babs(nodeOne->GetX()-nodeTwo->GetX()) <= Marge )
                  {
                     // y van beginnode vd link binnen marge?
                     // zijn twee node-object referenties wel verschillend?
                     if(babs(nodeOne->GetY()-nodeTwo->GetY()) <= Marge &&
                        (!(nodeOne == nodeTwo))
                       )
                     {
                        links.item()->Mark();
                        nodeOne->Merge(nodeTwo);
                        merges++;
                     }//y binnen marge en niet zelfde node
                  }//x binnen marge?
                  else
                  {
                     // link valt buiten marge; de rest vd links
                     // dus ook (omdat lijst gesorteerd is)
                     links.totail();
                  }
               }//marked?
               links++;
            }//current -> ongeldig
         }//verwerkt?
      }//all links

      }//om de extra iterator te verwijderen
   }
	RemoveNullLinks();

	return merges;
}


int Graph::ScanGraph2(SCANTYPE scantype, bool& holes )
{
   TDLI<KBoolLink> _LI=TDLI<KBoolLink>(_linklist);
   int found=0;

	//sort links on x and y value of beginnode
	_LI.mergesort(linkXYsorter);

	writegraph( false );

	//bin flag is used in scanbeam so reset
   _LI.foreach_mf(&KBoolLink::SetNotBeenHere);

	ScanBeam* scanbeam = new ScanBeam(_GC);
   Node*  _low;
   Node*  _high;

   _LI.tohead();
   while (!_LI.attail())
   {
         _low = _LI.item()->GetBeginNode();
         //find new links for the new beam and remove the old links
         if ( scanbeam->FindNew(scantype,&_LI, holes ) )
            found++;

         //find a new low node, this should be a node not eqaul to the current _low
         do
         {  _LI++;}
         while (!_LI.hitroot() && (_low == _LI.item()->GetBeginNode()));
         if (_LI.hitroot())
            //if the last few links share the same beginnode
            //we arive here
            break;
         else
            _high=_LI.item()->GetBeginNode();

         scanbeam->SetType(_low,_high);

         if (scanbeam->RemoveOld(scantype,&_LI, holes ) )
            found++;
   }

	delete scanbeam;
	return found;
}


/*

//      	scanbeam->writebeam();

      if (j%100 ==0)
      {
        long x;
        long y;
        char buf[80];
		   x=(long)_lowlink->GetBeginNode()->GetX();
		   y=(long)_lowlink->GetBeginNode()->GetY();
        sprintf(buf," x=%I64d , y=%I64d here %I64d",x,y,scanbeam->count());
			_GC->SetState(buf);
      	scanbeam->writebeam();
      }



         writegraph(false);
            if (!checksort())
            {
               double x=_lowlink->GetBeginNode()->GetX();
               checksort();
            }



         _LI++;
      }
   }

	delete scanbeam;
	return 0;
}


         if (!checksort())
         {
            x=_lowlink->GetBeginNode()->GetX();
            checksort();
         }

         if (x >= -112200)
         {