xref: /dports/devel/libarea/libarea-2752cd9/kbool/src/line.cpp

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

    Copyright: 2001-2004 (C) Klaas Holwerda

    Licence: see kboollicense.txt

    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 "kbool/include/booleng.h"

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

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

#include "kbool/include/graph.h"
#include "kbool/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();
	ep = lijn->m_link->GetEndNode();

  	Result_beginnode = PointInLine(bp,distance,Marge);
	Result_endnode   = PointInLine(ep,distance,Marge);

	Take_Action1 = ActionOnTable1(Result_beginnode,Result_endnode);

	// The first switch will insert a crosspoint immediatly
	switch (Take_Action1)
	{
		// for the cases see the returnvalue of ActionTable1
		case 2: case 6: AddCrossing(ep);
							 Number_of_Crossings = 1;
							 break;
		case 3: case 5: AddCrossing(bp);
							 Number_of_Crossings = 1;
							 break;
		case 4: 			 AddCrossing(bp);
							 AddCrossing(ep);
							 Number_of_Crossings = 2;
							 break;
	}
	// This switch wil investigate the points of this line in relation to lijn
	switch (Take_Action1)
	{
		// for the cases see the returnvalue of ActionTable1
		case 1: case 5: case 6:
		  {
				// Get the nodes from this line via the link
				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)
				{
					// for the cases see the returnvalue of ActionTable2
					case 1: {   // begin of scope to calculate the intersection
									double X, Y, Denominator;
									CalculateLineParameters();
									Denominator  = (m_AA * lijn->m_BB) - (lijn->m_AA * m_BB);
									// Denominator may not be 0
									assert(Denominator != 0.0);
									// Calculate intersection of both linesegments
									X = ((m_BB * lijn->m_CC) - (lijn->m_BB * m_CC)) / Denominator;
									Y = ((lijn->m_AA * m_CC) - (m_AA * lijn->m_CC)) / Denominator;

                           //make a decent rounding to B_INT
                           AddLineCrossing((B_INT)X,(B_INT)Y,lijn);
							  }   // end of scope to calculate the intersection
							  Number_of_Crossings++;
							  break;
					case 2: lijn->AddCrossing(ep);
							  Number_of_Crossings++;
							  break;
					case 3: lijn->AddCrossing(bp);
							  Number_of_Crossings++;
							  break;
					case 4: lijn->AddCrossing(bp);
							  lijn->AddCrossing(ep);
							  Number_of_Crossings = 2;
							  break;
				}
		  }; break; // This break belongs to the outer switch
	}
	return Number_of_Crossings; //This is de final number of crossings
}


// Intersects two lines there must be a crossing
int KBoolLine::Intersect_simple(KBoolLine * lijn)
{
	// lijn must exist
	assert(lijn);

	double X, Y, Denominator;
	Denominator  = (m_AA * lijn->m_BB) - (lijn->m_AA * m_BB);
	// Denominator may not be 0
	if (Denominator == 0.0)
			m_GC->error("colliniar lines","line");
	// Calculate intersection of both linesegments
	X = ((m_BB * lijn->m_CC) - (lijn->m_BB * m_CC)) / Denominator;
	Y = ((lijn->m_AA * m_CC) - (m_AA * lijn->m_CC)) / Denominator;
	AddLineCrossing((B_INT)X,(B_INT)Y,lijn);

	return(0);
}

// Intersects two lines there must be a crossing
bool KBoolLine::Intersect2(Node* crossing,KBoolLine * lijn)
{
	// lijn must exist
	assert(lijn);

	double X, Y, Denominator;
	Denominator  = (m_AA * lijn->m_BB) - (lijn->m_AA * m_BB);
	// Denominator may not be 0
	if (Denominator == 0.0)
		return false;
	// Calculate intersection of both linesegments
	X = ((m_BB * lijn->m_CC) - (lijn->m_BB * m_CC)) / Denominator;
	Y = ((lijn->m_AA * m_CC) - (m_AA * lijn->m_CC)) / Denominator;

	crossing->SetX((B_INT)X);
	crossing->SetY((B_INT)Y);
	return true;
}

//
// test if a point lies in the linesegment. If the point isn't on the line
// the function returns a value that indicates on which side of the
// line the point is (in linedirection from first point to second point
//
// returns LEFT_SIDE, when point lies on the left side of the line
//         RIGHT_SIDE, when point lies on the right side of the line
//         ON_AREA, when point lies on the infinite line within a range
//			  IN_AREA, when point lies in the area of the linesegment
// 		  the returnvalues are declared in (LINE.H)
PointStatus KBoolLine::PointInLine(Node *a_node, double& Distance, double Marge)
{
	  Distance=0;

	  //Punt must exist
	  assert(a_node);
	  // link must exist to get beginnode and endnode via link
	  assert(m_link);

	  // get the nodes form the line via the link
	  Node *bp, *ep;
	  bp = m_link->GetBeginNode();
	  ep = m_link->GetEndNode();

	  // both node must exist
	  assert(bp && ep);
	  // node may not be the same
	  assert(bp != ep);

     //quick test if point is begin or endpoint
     if (a_node == bp || a_node == ep)
        return IN_AREA;

	  int Result_of_BBox=false;
	  PointStatus Result_of_Online;

	  // Checking if point is in bounding-box with marge
     B_INT xmin=bmin(bp->GetX(),ep->GetX());
     B_INT xmax=bmax(bp->GetX(),ep->GetX());
     B_INT ymin=bmin(bp->GetY(),ep->GetY());
     B_INT ymax=bmax(bp->GetY(),ep->GetY());

     if (  a_node->GetX() >= (xmin - Marge) && a_node->GetX() <= (xmax + Marge) &&
           a_node->GetY() >= (ymin - Marge) && a_node->GetY() <= (ymax + Marge) )
		  Result_of_BBox=true;

	  // Checking if point is on the infinite line
	  Result_of_Online = PointOnLine(a_node, Distance, Marge);

	  // point in boundingbox of the line and is on the line then the point is IN_AREA
	  if ((Result_of_BBox) && (Result_of_Online == ON_AREA))
			return IN_AREA;
	  else
			return Result_of_Online;
}


//
// test if a point lies on the line. If the point isn't on the line
// the function returns a value that indicates on which side of the
// line the point is (in linedirection from first point to second point
//
// returns LEFT_SIDE, when point lies on the left side of the line
//         ON_AREA, when point lies on the infinite line within a range
//         RIGHT_SIDE, when point lies on the right side of the line
// 		  LEFT_SIDE , RIGHT_SIDE , ON_AREA
PointStatus KBoolLine::PointOnLine(Node *a_node, double& Distance, double Marge)
{
   Distance=0;

	// a_node must exist
	assert(a_node);
	// link must exist to get beginnode and endnode
	assert(m_link);

	// get the nodes from the line via the link
	Node *bp, *ep;
	bp = m_link->GetBeginNode();
	ep = m_link->GetEndNode();

	// both node must exist
	assert(bp && ep);
	// node may not be queal
	assert(bp!=ep);

   //quick test if point is begin or endpoint
   if (a_node == bp || a_node == ep)
      return ON_AREA;

	CalculateLineParameters();
	// calculate the distance of a_node in relation to the line
	Distance = (m_AA * a_node->GetX())+(m_BB * a_node->GetY()) + m_CC;

	if (Distance < -Marge)
		return LEFT_SIDE;
	else
	{
		if (Distance > Marge)
			return RIGHT_SIDE;
		else
		 return ON_AREA;
	}
}


//
// Sets lines parameters
// usage: a_line.Set(a_pointer_to_a_link);
//
void KBoolLine::Set(KBoolLink *a_link)
{
	// points 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(),MARGE)) assert(!a_link);

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

KBoolLink* KBoolLine::GetLink()
{
   return m_link;
}
//
// makes a line same as these
// usage : line1 = line2;
//
KBoolLine& KBoolLine::operator=(const KBoolLine& a_line)
{
	m_AA = a_line.m_AA;
	m_BB = a_line.m_BB;
	m_CC = a_line.m_CC;
	m_link = a_line.m_link;
  	linecrosslist = NULL;
	m_valid_parameters = a_line.m_valid_parameters;
	return *this;
}

Node* KBoolLine::OffsetContour(KBoolLine* const nextline,Node* _last_ins, double factor,Graph *shape)
{
	KBoolLink* offs_currentlink;
	KBoolLine  offs_currentline(m_GC);
	KBoolLink* offs_nextlink;
	KBoolLine  offs_nextline(m_GC);
	Node* offs_end;

	Node* offs_bgn_next;
	Node* offs_end_next;

	// make a node from this point
	offs_end = new Node(GetEndNode(), m_GC);
	Virtual_Point(offs_end,factor);
	offs_currentlink=new KBoolLink(0, m_link->m_user_data, _last_ins,offs_end, m_GC);
	offs_currentline.Set(offs_currentlink);

	offs_bgn_next = new Node(nextline->m_link->GetBeginNode(), m_GC);
	nextline->Virtual_Point(offs_bgn_next,factor);

	offs_end_next = new Node(nextline->m_link->GetEndNode(), m_GC);
	nextline->Virtual_Point(offs_end_next,factor);

	offs_nextlink=new KBoolLink(0, m_link->m_user_data, offs_bgn_next, offs_end_next, m_GC);
	offs_nextline.Set(offs_nextlink);

	offs_currentline.CalculateLineParameters();
	offs_nextline.CalculateLineParameters();
	offs_currentline.Intersect2(offs_end,&offs_nextline);

	// make a link between the current and the previous and add this to graph
	shape->AddLink(offs_currentlink);

	delete offs_nextlink;

	return(offs_end);
}


Node* KBoolLine::OffsetContour_rounded(KBoolLine* const nextline,Node* _last_ins, double factor,Graph *shape)
{
	KBoolLink* offs_currentlink;
	KBoolLine  offs_currentline(m_GC);
	KBoolLink* offs_nextlink;
	KBoolLine  offs_nextline(m_GC);
	Node* offs_end;
	Node* medial_axes_point= new Node(m_GC);
	Node* bu_last_ins = new Node(_last_ins, m_GC);

	Node* offs_bgn_next;
	Node* offs_end_next;

	// make a node from this point
	offs_end = new Node(GetEndNode(), m_GC);

	*_last_ins = *GetBeginNode();
	Virtual_Point(_last_ins,factor);
	Virtual_Point(offs_end,factor);
	offs_currentlink=new KBoolLink(0, m_link->m_user_data, _last_ins,offs_end, m_GC);
	offs_currentline.Set(offs_currentlink);

	offs_bgn_next = new Node(nextline->m_link->GetBeginNode(), m_GC);
	nextline->Virtual_Point(offs_bgn_next,factor);

	offs_end_next = new Node(nextline->m_link->GetEndNode(), m_GC);
	nextline->Virtual_Point(offs_end_next,factor);

	offs_nextlink=new KBoolLink(0, m_link->m_user_data, offs_bgn_next, offs_end_next, m_GC);
	offs_nextline.Set(offs_nextlink);

	offs_currentline.CalculateLineParameters();
	offs_nextline.CalculateLineParameters();
	offs_currentline.Intersect2(medial_axes_point,&offs_nextline);

	double result_offs=sqrt( pow((double)GetEndNode()->GetY()-medial_axes_point->GetY(),2) +
							 pow((double)GetEndNode()->GetX()-medial_axes_point->GetX(),2) );

	if ( result_offs < fabs(m_GC->GetRoundfactor()*factor))
	{
		*_last_ins=*bu_last_ins;
		*offs_end=*medial_axes_point;
		delete medial_axes_point;
		delete bu_last_ins;
		// make a link between the current and the previous and add this to graph
		delete offs_nextlink;
		shape->AddLink(offs_currentlink);
		return(offs_end);
	}
	else
	{ //let us create a circle
		*_last_ins=*bu_last_ins;
		delete medial_axes_point;
		delete bu_last_ins;
		Node* endarc= new Node(offs_bgn_next, m_GC);
		shape->AddLink(offs_currentlink);
		delete offs_nextlink;
		shape->CreateArc(GetEndNode(), &offs_currentline, endarc,fabs(factor),m_GC->GetInternalCorrectionAber(), m_link->m_user_data);
		return(endarc);
	}
}


bool KBoolLine::OkeForContour(KBoolLine* const nextline,double factor,Node* LastLeft,Node* LastRight, LinkStatus& _outproduct)
{
	assert(m_link);
	assert(m_valid_parameters);
	assert(nextline->m_link);
	assert(nextline->m_valid_parameters);

	factor = fabs(factor);

//	PointStatus status=ON_AREA;
	double distance=0;

	Node offs_end_next(nextline->m_link->GetEndNode(), m_GC);

	_outproduct= m_link->OutProduct(nextline->m_link,m_GC->GetAccur());

	switch (_outproduct)
	{
		// current line lies on  leftside of prev line
		case IS_RIGHT :
		{
			nextline->Virtual_Point(&offs_end_next,-factor);

			// status=
			nextline->PointOnLine(LastRight, distance, m_GC->GetAccur());
			if (distance > factor)
			{  PointOnLine(&offs_end_next, distance, m_GC->GetAccur());
				if (distance > factor)
					 return(true);
			}
		}
		break;
		// current line lies on  rightside of prev line
		case IS_LEFT :
		{
			nextline->Virtual_Point(&offs_end_next,factor);

			// status=
			nextline->PointOnLine(LastLeft, distance, m_GC->GetAccur());
			if (distance < -factor)
			{  PointOnLine(&offs_end_next, distance, m_GC->GetAccur());
				if (distance <-factor)
					 return(true);
			}
		}
		break;
		// current line  lies on prev line
		case IS_ON	 :
		{
			return(true);
		}
	}//end switch

	return(false);
}


bool KBoolLine::Create_Ring_Shape(KBoolLine* nextline,Node** _last_ins_left,Node** _last_ins_right,double factor,Graph *shape)
{
	Node* _current;
	LinkStatus _outproduct=IS_ON;

	if (OkeForContour(nextline,factor,*_last_ins_left,*_last_ins_right,_outproduct))
	{
		switch (_outproduct)
		{
			// Line 2 lies on  leftside of this line
			case IS_RIGHT :
			{
				*_last_ins_left  =OffsetContour_rounded(nextline,*_last_ins_left,factor,shape);
				*_last_ins_right =OffsetContour(nextline,*_last_ins_right,-factor,shape);
			}
			break;
			case IS_LEFT :
			{
				*_last_ins_left  =OffsetContour(nextline,*_last_ins_left,factor,shape);
				*_last_ins_right =OffsetContour_rounded(nextline,*_last_ins_right,-factor,shape);

			}
			break;
			// Line 2 lies on this line
			case IS_ON	 :
			{
				// make a node from this point
				_current = new Node(m_link->GetEndNode(), m_GC);
				Virtual_Point(_current,factor);

				// make a link between the current and the previous and add this to graph
				shape->AddLink(*_last_ins_left, _current, m_link->m_user_data);
				*_last_ins_left=_current;

				_current = new Node(m_link->GetEndNode(), m_GC);
				Virtual_Point(_current,-factor);

				shape->AddLink(*_last_ins_right, _current, m_link->m_user_data);
				*_last_ins_right=_current;
			}
			break;
		}//end switch
		return(true);
	}
/*	else
	{
		switch (_outproduct)
		{
			// Line 2 lies on  leftside of this line
			case IS_RIGHT :
			{
				*_last_ins_left  =OffsetContour_rounded(nextline,*_last_ins_left,factor,Ishape);
				*_last_ins_right =OffsetContour(nextline,*_last_ins_right,-factor,Ishape);
			}
			break;
			case IS_LEFT :
			{
				*_last_ins_left  =OffsetContour(nextline,*_last_ins_left,factor,Ishape);
				*_last_ins_right =OffsetContour_rounded(nextline,*_last_ins_right,-factor,Ishape);

			}
			break;
			// Line 2 lies on this line
			case IS_ON	 :
			{
				// make a node from this point
				_current = new Node(m_link->GetEndNode());
				Virtual_Point(_current,factor);

				// make a link between the current and the previous and add this to graph
				Ishape->AddLink(*_last_ins_left, _current);
				*_last_ins_left=_current;

				_current = new Node(m_link->GetEndNode());
				Virtual_Point(_current,-factor);

				Ishape->AddLink(*_last_ins_right, _current);
				*_last_ins_right=_current;
			}
			break;
		}//end switch
		return(true);
	}
*/
	return(false);
}


void KBoolLine::Create_Begin_Shape(KBoolLine* nextline,Node** _last_ins_left,Node** _last_ins_right,double factor,Graph *shape)
{
	factor = fabs(factor);
	LinkStatus _outproduct;
	_outproduct= m_link->OutProduct(nextline->m_link,m_GC->GetAccur());

	switch (_outproduct)
	{
		case IS_RIGHT :
		{
			*_last_ins_left = new Node(m_link->GetEndNode(), m_GC);

			Virtual_Point(*_last_ins_left,factor);

			*_last_ins_right = new Node(nextline->m_link->GetBeginNode(), m_GC);
			nextline->Virtual_Point(*_last_ins_right,-factor);

			shape->AddLink(*_last_ins_left, *_last_ins_right, m_link->m_user_data);

			*_last_ins_left=OffsetContour_rounded(nextline,*_last_ins_left,factor,shape);
		}
		break;
		case IS_LEFT :
		{
			*_last_ins_left = new Node(nextline->m_link->GetBeginNode(), m_GC);
			nextline->Virtual_Point(*_last_ins_left,factor);

			*_last_ins_right = new Node(m_link->GetEndNode(), m_GC);
			Virtual_Point(*_last_ins_right,-factor);

			shape->AddLink(*_last_ins_left, *_last_ins_right, m_link->m_user_data);

			*_last_ins_right=OffsetContour_rounded(nextline,*_last_ins_right,-factor,shape);
		}
		break;
		// Line 2 lies on this line
		case IS_ON	 :
		{
			*_last_ins_left = new Node(nextline->m_link->GetBeginNode(), m_GC);
			Virtual_Point(*_last_ins_left,factor);

			*_last_ins_right = new Node(nextline->m_link->GetBeginNode(), m_GC);
			Virtual_Point(*_last_ins_right,-factor);

			shape->AddLink(*_last_ins_left, *_last_ins_right, m_link->m_user_data);
		}
		break;
	}//end switch

}

void KBoolLine::Create_End_Shape(KBoolLine* nextline,Node* _last_ins_left,Node* _last_ins_right,double factor,Graph *shape)
{
	Node* _current;
	factor = fabs(factor);
	LinkStatus _outproduct;
	_outproduct= m_link->OutProduct(nextline->m_link,m_GC->GetAccur());

	switch (_outproduct)
	{
		case IS_RIGHT :
		{
			_current = new Node(m_link->GetEndNode(), m_GC);
			Virtual_Point(_current,-factor);
			shape->AddLink(_last_ins_right, _current, m_link->m_user_data);
			_last_ins_right=_current;

			_last_ins_left=OffsetContour_rounded(nextline,_last_ins_left,factor,shape);
			shape->AddLink(_last_ins_left,_last_ins_right, m_link->m_user_data);
		}
		break;
		case IS_LEFT :
		{
			_current = new Node(m_link->GetEndNode(), m_GC);
			Virtual_Point(_current,factor);
			shape->AddLink(_last_ins_left, _current, m_link->m_user_data);
			_last_ins_left=_current;

			_last_ins_right=OffsetContour_rounded(nextline,_last_ins_right,-factor,shape);
			shape->AddLink(_last_ins_right, _last_ins_left, m_link->m_user_data);
		}
		break;
		// Line 2 lies on this line
		case IS_ON	 :
		{
			_current = new Node(m_link->GetEndNode(), m_GC);
			Virtual_Point(_current,factor);
			shape->AddLink(_last_ins_left, _current, m_link->m_user_data);
			_last_ins_left=_current;

			_current = new Node(m_link->GetEndNode(), m_GC);
			Virtual_Point(_current,-factor);
			shape->AddLink(_last_ins_right, _current, m_link->m_user_data);
			_last_ins_right=_current;

			shape->AddLink(_last_ins_left, _last_ins_right, m_link->m_user_data);
		}
		break;
	}//end switch

}

//
// Generate from the found crossings a part of the graph
//
bool KBoolLine::ProcessCrossings(TDLI<KBoolLink>* _LI)
{
	Node *last;	KBoolLink *dummy;
//	assert (beginnode && endnode);

	if (!linecrosslist)	return false;

	if (linecrosslist->empty())	return false;
	if (linecrosslist->count()>1)	SortLineCrossings();
	m_link->GetEndNode()->RemoveLink(m_link);
	last=m_link->GetEndNode();
	// Make new links :
	while (!linecrosslist->empty())
	{
		dummy=new KBoolLink(m_link->GetGraphNum(), m_link->m_user_data, (Node*) linecrosslist->tailitem(),last, m_GC);
      dummy->SetBeenHere();
		dummy->SetGroup(m_link->Group());
      _LI->insbegin(dummy);
		last=(Node*)linecrosslist->tailitem();
		linecrosslist->removetail();
	}
	// Recycle this link :
	last->AddLink(m_link);
	m_link->SetEndNode(last);
	delete linecrosslist;
	linecrosslist=NULL;
	return true;
}

/*
// Sorts the links on the X values
int NodeXYsorter(Node* a, Node* b)
{
	if ( a->GetX() < b->GetX())
		return(1);
	if ( a->GetX() > b->GetX())
		return(-1);
   //they are eqaul in x
	if ( a->GetY() < b->GetY())
		return(-1);
	if ( a->GetY() > b->GetY())
		return(1);
   //they are eqaul in y
	return(0);
}

//
// Generate from the found crossings a part of the graph
// this routine is used in combination with the scanbeam class
// the this link most stay at the same place in the sorted graph
// The link is split into peaces wich are inserted sorted into the graph
// on beginnode.
// The mostleft link most become the new link for the beam record
// therefore the mostleft new/old link is returned to become the beam record link
// also the part returned needs to have the bin flag set to the original value it had in the beam
KBoolLink* KBoolLine::ProcessCrossingsSmart(TDLI<KBoolLink>* _LI)
{
   Node *lastinserted;
   KBoolLink *new_link;
   KBoolLink *returnlink;
	assert (beginnode && endnode);
	if (!linecrosslist)	return this;

	if (linecrosslist->empty())	return this;
	if (linecrosslist->count()>1)
   {
   	SortLineCrossings();
   }
	int inbeam;

   //most left at the beginnode or endnode
   if (NodeXYsorter(beginnode,endnode)==1)
   {
      //re_use this link
      endnode->RemoveLink(this);
      linecrosslist->insend(endnode); //the last link to create is towards this node
      endnode=(Node*) linecrosslist->headitem();
      endnode->AddLink(this);
      inbeam=NodeXYsorter(_LI->item()->beginnode,beginnode);
      switch (inbeam)
      {
        case -1:
        case 0:
            bin=true;
            break;
        case 1:
            bin=false;
            break;
      }
      returnlink=this;

      lastinserted=endnode;
      linecrosslist->removehead();
      // Make new links starting at endnode
      while (!linecrosslist->empty())
      {
         new_link=new KBoolLink(graphnum,lastinserted,(Node*) linecrosslist->headitem());

         new_link->group=group;
         int inbeam=NodeXYsorter(_LI->item()->beginnode,lastinserted);
         switch (inbeam)
         {
           case -1:
               {
                 double x,y,xl,yl;
                 char buf[80];
                 x=((Node*)(linecrosslist->headitem()))->GetX();
                 y=((Node*)(linecrosslist->headitem()))->GetY();
					  xl=_LI->item()->beginnode->GetX();
                 yl=_LI->item()->beginnode->GetY();
                 sprintf(buf," x=%f , y=%f inserted before %f,%f",x,y,xl,yl);
                 _messagehandler->info(buf,"scanbeam");
		           new_link->bin=true;
               }
               break;
           case 0:
	            new_link->bin=true;
	            returnlink=new_link;
               break;
           case 1:
	            new_link->bin=false;
               break;
         }

         //insert a link into the graph that is already sorted on beginnodes of the links.
         //starting at a given position
         // if empty then just insert

         if (_LI->empty())
            _LI->insend(new_link);
         else
         {
            // put new item left of the one that is bigger are equal
            int i=0;
            int insert=0;
            while(!_LI->hitroot())
            {
               if ((insert=linkXYsorter(new_link,_LI->item()))!=-1)
                  break;
               (*_LI)++;
               i++;
            }

            _LI->insbefore_unsave(new_link);
            if (insert==0 && _LI->item()->beginnode!=new_link->beginnode)
             //the begin nodes are equal but not the same merge them into one node
            {  Node* todelete=_LI->item()->beginnode;
					new_link->beginnode->Merge(todelete);
					delete todelete;
            }

            //set back iter
            (*_LI) << (i+1);
         }

         lastinserted=(Node*)linecrosslist->headitem();
         linecrosslist->removehead();
      }
   }
   else
   {
      //re_use this link
      endnode->RemoveLink(this);
      linecrosslist->insend(endnode); //the last link to create is towards this node
      endnode=(Node*) linecrosslist->headitem();
      endnode->AddLink(this);
      inbeam=NodeXYsorter(_LI->item()->beginnode,endnode);
      switch (inbeam)
      {
        case -1:
        case 0:
            bin=true;
            break;
        case 1:
            bin=false;
            break;
      }
      returnlink=this;

      lastinserted=endnode;
      linecrosslist->removehead();

      // Make new links starting at endnode
      while (!linecrosslist->empty())
      {
         new_link=new KBoolLink(graphnum,lastinserted,(Node*) linecrosslist->headitem());
         new_link->group=group;

         inbeam=NodeXYsorter(_LI->item()->beginnode,(Node*) linecrosslist->headitem());
         switch (inbeam)
         {
           case -1:
           case 0:
	            new_link->bin=true;
               break;
           case 1:
	            new_link->bin=false;
               break;
         }
         inbeam=NodeXYsorter(_LI->item()->beginnode,lastinserted);
         switch (inbeam)
         {
           case -1:
               {
                 double x,y,xl,yl;
                 char buf[80];
                 x=lastinserted->GetX();
                 y=lastinserted->GetY();
					  xl=_LI->item()->beginnode->GetX();
                 yl=_LI->item()->beginnode->GetY();
                 sprintf(buf," x=%f , y=%f inserted before %f,%f",x,y,xl,yl);
                 _messagehandler->info(buf,"scanbeam");
               }
               break;
           case 0:
               break;
           case 1:
	            returnlink=new_link;
               break;
         }

         //insert a link into the graph that is already sorted on beginnodes of the links.
         //starting at a given position
         // if empty then just insert

         if (_LI->empty())
            _LI->insend(new_link);
         else
         {
            // put new item left of the one that is bigger are equal
            int i=0;
            int insert=0;
            while(!_LI->hitroot())
            {
               if ((insert=linkXYsorter(new_link,_LI->item()))!=-1)
                  break;
               (*_LI)++;
               i++;
            }

            _LI->insbefore_unsave(new_link);
            if (insert==0 && _LI->item()->beginnode!=new_link->beginnode)
             //the begin nodes are equal but not the same merge them into one node
            {  Node* todelete=_LI->item()->beginnode;
					new_link->beginnode->Merge(todelete);
					delete todelete;
            }
            //set back iter
            (*_LI) << (i+1);
         }

         lastinserted=(Node*)linecrosslist->headitem();
         linecrosslist->removehead();
      }
   }
	delete linecrosslist;
	linecrosslist=NULL;

  	return returnlink;
}
*/

static int NODE_X_ASCENDING_L (Node* a, Node* b)
{
	if(b->GetX() > a->GetX()) return(1);
	else
	if(b->GetX() == a->GetX()) return(0);

	return(-1);
}

static int NODE_X_DESCENDING_L(Node* a, Node* b)
{
	if(a->GetX() > b->GetX()) return(1);
	else
	if(a->GetX() == b->GetX()) return(0);

	return(-1);
}

static int NODE_Y_ASCENDING_L (Node* a, Node* b)
{
	if(b->GetY() > a->GetY()) return(1);
	else
	if(b->GetY() == a->GetY()) return(0);
	return(-1);
}

static int NODE_Y_DESCENDING_L(Node* a, Node* b)
{
	if(a->GetY() > b->GetY()) return(1);
	else
	if(a->GetY() == b->GetY()) return(0);

	return(-1);
}

//
// This function finds out which sortfunction to use with sorting
// the crossings.
//
void KBoolLine::SortLineCrossings()
{
	TDLI<Node> I(linecrosslist);

	B_INT dx, dy;
	dx=babs(m_link->GetEndNode()->GetX() - m_link->GetBeginNode()->GetX());
	dy=babs(m_link->GetEndNode()->GetY() - m_link->GetBeginNode()->GetY());
	if (dx > dy)
	{	// thislink is more horizontal then vertical
		if (m_link->GetEndNode()->GetX() > m_link->GetBeginNode()->GetX())
			I.mergesort(NODE_X_ASCENDING_L);
		else
			I.mergesort(NODE_X_DESCENDING_L);
	}
	else
	{	// this link is more vertical then horizontal
		if (m_link->GetEndNode()->GetY() > m_link->GetBeginNode()->GetY())
			I.mergesort(NODE_Y_ASCENDING_L);
		else
			I.mergesort(NODE_Y_DESCENDING_L);
	}
}

//
// Adds a cross Node to this. a_node may not be deleted before processing the crossings
//
void KBoolLine::AddCrossing(Node *a_node)
{
	if (a_node==m_link->GetBeginNode() || a_node==m_link->GetEndNode())	return;


	if (!linecrosslist)
	{
		linecrosslist=new DL_List<void*>();
		linecrosslist->insend(a_node);
	}
	else
	{
		TDLI<Node> I(linecrosslist);
		if (!I.has(a_node))
			I.insend(a_node);
	}
}

//
// see above
//
Node* KBoolLine::AddCrossing(B_INT X, B_INT Y)
{
	Node* result=new Node(X,Y, m_GC);
	AddCrossing(result);
	return result;
}

DL_List<void*>* KBoolLine::GetCrossList()
{
	if (linecrosslist)
		return linecrosslist;
	return NULL;
}

bool KBoolLine::CrossListEmpty()
{
	if (linecrosslist)
		return linecrosslist->empty();
	return true;
}

/*
bool KBoolLine::HasInCrossList(Node *n)
{
	if(linecrosslist!=NULL)
	{
		TDLI<Node> I(linecrosslist);
		return I.has(n);
	}
	return false;
}
*/