line.cpp

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

/*! \file ../src/line.cpp
    \brief Mainly used for calculating crossings
    \author Probably Klaas Holwerda 

    Copyright: 2001-2004 (C) Probably Klaas Holwerda 

    Licence: wxWidgets Licence

    RCS-ID: $Id: line.cpp,v 1.10 2005/06/17 22:48:46 kbluck Exp $
*/

#ifdef __GNUG__
#pragma implementation
#endif

// Standard include files
#include <assert.h>
#include <math.h>

#include "../include/booleng.h"

// Include files for forward declarations
#include "../include/link.h"
#include "../include/node.h"

// header
#include "../include/line.h"

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

//
// The default constructor
//
KBoolLine::KBoolLine(Bool_Engine* GC)
{
    m_GC=GC;
	m_AA = 0.0;
	m_BB = 0.0;
	m_CC = 0.0;
	m_link = 0;
	linecrosslist = NULL;
	m_valid_parameters = false;
}

KBoolLine::~KBoolLine()
{
	if (linecrosslist)
		delete linecrosslist;
}

//
// constructor with a link
//
KBoolLine::KBoolLine(KBoolLink *a_link,Bool_Engine* GC)
{
	m_GC=GC;
	// a_link must exist
	assert(a_link);
	// points may not be equal
	// must be an if statement because if an assert is used there will
	// be a macro expansion error

	//if (a_link->GetBeginNode()->Equal(a_link->GetEndNode(), 1))
	//	assert(!a_link);

	linecrosslist = NULL;
	m_link = a_link;
	m_valid_parameters = false;
}



// ActionOnTable1
// This function decide which action must be taken, after PointInLine
// has given the results of two points in relation to a line. See table 1 in the report
//
// input Result_beginnode:
//			Result_endnode :
//       The results can be LEFT_SIDE, RIGHT_SIDE, ON_AREA, IN_AREA
//
// return -1: Illegal combination
//         0: No action, no crosspoints
//         1: Investigate results points in relation to the other line
//         2: endnode is a crosspoint, no further investigation
//         3: beginnode is a crosspoint, no further investigation
//			  4: beginnode and endnode are crosspoints, no further investigation
//         5: beginnode is a crosspoint, need further investigation
//         6: endnode is a crosspoint, need further investigation
int KBoolLine::ActionOnTable1(PointStatus Result_beginnode, PointStatus Result_endnode)
{
	// Action 1.5 beginnode and endnode are crosspoints, no further investigation needed
	if (
		 (Result_beginnode == IN_AREA)
		 &&
		 (Result_endnode == IN_AREA)
		)
		return 4;
   // Action 1.1, there are no crosspoints, no action
	if (
		 (
		  (Result_beginnode == LEFT_SIDE)
		  &&
		  (Result_endnode == LEFT_SIDE)
		 )
		 ||
		 (
		  (Result_beginnode == RIGHT_SIDE)
		  &&
		  (Result_endnode == RIGHT_SIDE)
		 )
		)
		return 0;
	// Action 1.2, maybe there is a crosspoint, further investigation needed
	if (
		 (
		  (Result_beginnode == LEFT_SIDE)
		  &&
		  (
			(Result_endnode == RIGHT_SIDE)
			||
			(Result_endnode == ON_AREA)
		  )
		 )
		 ||
		 (
		  (Result_beginnode == RIGHT_SIDE)
		  &&
		  (
			(Result_endnode == LEFT_SIDE)
			||
			(Result_endnode == ON_AREA)
		  )
		 )
		 ||
		 (
		  (Result_beginnode == ON_AREA)
		  &&
		  (
			(Result_endnode == LEFT_SIDE)
			||
			(Result_endnode == RIGHT_SIDE)
			||
			(Result_endnode == ON_AREA)
		  )
		 )
		)
		return 1;
	// Action 1.3, there is a crosspoint, no further investigation
	if (
		 (
		  (Result_beginnode == LEFT_SIDE)
		  ||
		  (Result_beginnode == RIGHT_SIDE)
		 )
		 &&
		 (Result_endnode == IN_AREA)
		)
		return 2;
	// Action 1.4  there is a crosspoint, no further investigation
	if (
		 (Result_beginnode == IN_AREA)
		 &&
		 (
		  (Result_endnode == LEFT_SIDE)
		  ||
		  (Result_endnode == RIGHT_SIDE)
		 )
		)
		return 3;
	// Action 1.6  beginnode is a crosspoint, further investigation needed
	if (
		 (Result_beginnode == IN_AREA)
		 &&
		 (Result_endnode == ON_AREA)
		)
		return 5;
	// Action 1.7  endnode is a crosspoint, further investigation needed
	if (
		 (Result_beginnode == ON_AREA)
		 &&
		 (Result_endnode == IN_AREA)
		)
		return 6;
	// All other combinations are illegal
	return -1;
}


// ActionOnTable2
// This function decide which action must be taken, after PointInLine
// has given the results of two points in relation to a line. It can only give a
// correct decision if first the relation of the points from the line
// are investigated in relation to the line wich can be constucted from the points.
//
// input Result_beginnode:
//			Result_endnode :
//       The results can be LEFT_SIDE, RIGHT_SIDE, ON_AREA, IN_AREA
//
// return -1: Illegal combination
//         0: No action, no crosspoints
//         1: Calculate crosspoint
//         2: endnode is a crosspoint
//         3: beginnode is a crosspoint
//         4: beginnode and endnode are crosspoints
int KBoolLine::ActionOnTable2(PointStatus Result_beginnode, PointStatus Result_endnode)
{
	// Action 2.5, beginnode and eindpoint are crosspoints
	if (
		 (Result_beginnode == IN_AREA)
		 &&
		 (Result_endnode == IN_AREA)
		)
		return 4;
	// Action 2.1, there are no crosspoints
	if (
		 (
		  (Result_beginnode == LEFT_SIDE)
		  &&
		  (
			(Result_endnode == LEFT_SIDE)
			||
			(Result_endnode == ON_AREA)
		  )
		 )
		 ||
		 (
		  (Result_beginnode == RIGHT_SIDE)
		  &&
		  (
			(Result_endnode == RIGHT_SIDE)
			||
			(Result_endnode == ON_AREA)
		  )
		 )
		 ||
		 (
		  (Result_beginnode == ON_AREA)
		  &&
		  (
			(Result_endnode == LEFT_SIDE)
			||
			(Result_endnode == RIGHT_SIDE)
			||
			(Result_endnode == ON_AREA)
		  )
		 )
		)
		return 0;
	// Action 2.2, there is a real intersection, which must be calculated
	if (
		 (
		  (Result_beginnode == LEFT_SIDE)
		  &&
		  (Result_endnode == RIGHT_SIDE)
		 )
		 ||
		 (
		  (Result_beginnode == RIGHT_SIDE)
		  &&
		  (Result_endnode == LEFT_SIDE)
		 )
		)
		return 1;
	// Action 2.3, endnode is a crosspoint
	if (
		 (
		  (Result_beginnode == LEFT_SIDE)
		  ||
		  (Result_beginnode == RIGHT_SIDE)
		  ||
		  (Result_beginnode == ON_AREA)
		 )
		 &&
		 (Result_endnode == IN_AREA)
		)
		return 2;
	// Action 2.4, beginnode is a crosspoint
	if (
		 (Result_beginnode == IN_AREA)
		 &&
		 (
		  (Result_endnode == LEFT_SIDE)
		  ||
		  (Result_endnode == RIGHT_SIDE)
		  ||
		  (Result_endnode == ON_AREA)
		 )
		)
		return 3;
	// All other combinations are illegal
	return -1;
}

//
// This fucntion will ad a crossing to this line and the other line
// the crossing will be put in the link, because the line will be destructed
// after use of the variable
//
void KBoolLine::AddLineCrossing(B_INT X, B_INT Y, KBoolLine *other_line)
{
	// the other line must exist
	assert(other_line);
	// the links of the lines must exist
	assert(other_line->m_link && m_link);
	other_line->AddCrossing(AddCrossing(X,Y));
}

// Calculate the Y when the X is given
//
B_INT KBoolLine::Calculate_Y(B_INT X)
{
	// link must exist to get info about the nodes
	assert(m_link);

	CalculateLineParameters();
	if (m_AA != 0)
		return (B_INT)(-(m_AA * X + m_CC) / m_BB);
	else
		// horizontal line
		return m_link->GetBeginNode()->GetY();
}

B_INT KBoolLine::Calculate_Y_from_X(B_INT X)
{
	// link must exist to get info about the nodes
	assert(m_link);
	assert(m_valid_parameters);

	if (m_AA != 0)
		return (B_INT) ((-(m_AA * X + m_CC) / m_BB)+0.5);
	else
		// horizontal line
		return m_link->GetBeginNode()->GetY();
}

void KBoolLine::Virtual_Point(LPoint *a_point,double distance)
{
	// link must exist to get info about the nodes
	assert(m_link);
	assert(m_valid_parameters);

	//calculate the distance using the slope of the line
   //and rotate 90 degrees

	a_point->SetY((B_INT)(a_point->GetY() + (distance * -(m_BB))));
	a_point->SetX((B_INT)(a_point->GetX() - (distance * m_AA   )));
}



//
// Calculate the lineparameters for the line if nessecary
//
void KBoolLine::CalculateLineParameters()
{
	// linkmust exist to get beginnode AND endnode
	assert(m_link);

	// if not valid_parameters calculate the parameters
	if (!m_valid_parameters)
	{
		Node *bp, *ep;
		double length;

		// get the begin and endnode via the link
		bp = m_link->GetBeginNode();
		ep = m_link->GetEndNode();

		// bp AND ep may not be the same
		if (bp == ep)
			assert (bp != ep);

		m_AA = (double) (ep->GetY() - bp->GetY()); // A = (Y2-Y1)
		m_BB = (double) (bp->GetX() - ep->GetX()); // B = (X1-X2)

		// the parameters A end B can now be normalized
		length = sqrt(m_AA*m_AA + m_BB*m_BB);

		if(length ==0)
			m_GC->error("length = 0","CalculateLineParameters");

		m_AA = (m_AA / length);
		m_BB = (m_BB / length);

		m_CC = -((m_AA * bp->GetX()) + (bp->GetY() * m_BB));

		m_valid_parameters = true;
	}
}


// Checks if a line intersect with another line
// inout    Line : another line
//          Marge: optional, standard on MARGE (declared in MISC.CPP)
//
// return	true : lines are crossing
// 			false: lines are not crossing
//
int KBoolLine::CheckIntersect (KBoolLine * lijn, double Marge)
{
	double distance=0;
	// link must exist
	assert(m_link);
	// lijn must exist
	assert(lijn);

	// points may not be equal
	// must be an if statement because if an assert is used there will
	// be a macro expansion error
	if (m_link->GetBeginNode() == m_link->GetEndNode())
		assert(!m_link);

	int Take_Action1, Take_Action2, Total_Result;
	Node *bp, *ep;
	PointStatus Result_beginnode,Result_endnode;

	bp = lijn->m_link->GetBeginNode();
	ep = lijn->m_link->GetEndNode();
	Result_beginnode = PointInLine(bp,distance,Marge);
	Result_endnode   = PointInLine(ep,distance,Marge);
	Take_Action1 = ActionOnTable1(Result_beginnode,Result_endnode);
	switch (Take_Action1)
	{
		case 0: Total_Result = false ; break;
		case 1: {
						bp = m_link->GetBeginNode();
						ep = m_link->GetEndNode();
						Result_beginnode = lijn->PointInLine(bp,distance,Marge);
						Result_endnode   = lijn->PointInLine(ep,distance,Marge);
						Take_Action2 = ActionOnTable2(Result_beginnode,Result_endnode);
						switch (Take_Action2)
						{
							case 0: Total_Result = false; break;
							case 1: case 2: case 3: case 4: Total_Result = true; break;
              default: Total_Result = false; assert( Total_Result );
						}
				  }; break; // This break belongs to the switch(Take_Action1)
		case 2: case 3: case 4: case 5: case 6: Total_Result = true; break;
    default: Total_Result = false; assert( Total_Result );
	}
	return Total_Result; //This is the final decision
}


//
// Get the beginnode from the line
// usage: Node *anode = a_line.GetBeginNode()
//
Node *KBoolLine::GetBeginNode()
{
  // link must exist
  assert(m_link);
  return m_link->GetBeginNode();
}


//
// Get the endnode from the line
// usage: Node *anode = a_line.GetEndNode()
//
Node *KBoolLine::GetEndNode()
{
	// link must exist
	assert(m_link);
	return m_link->GetEndNode();
}

// Intersects two lines
// input    Line : another line
//          Marge: optional, standard on MARGE
//
// return	0: If there are no crossings
//				1: If there is one crossing
//				2: If there are two crossings
int KBoolLine::Intersect(KBoolLine * lijn, double Marge)
{
	double distance=0;
	// lijn must exist
	assert(lijn);

	// points may not be equal
	// must be an if statement because if an assert is used there will
	// be a macro expansion error
	if (m_link->GetBeginNode() == m_link->GetEndNode())
		assert(!m_link);

	Node *bp, *ep;
	PointStatus Result_beginnode,Result_endnode;
	int Take_Action1, Take_Action2, Number_of_Crossings = 0;

	// Get the nodes from lijn via the link
	bp = lijn->m_link->GetBeginNode();