/*! \file 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.6 2009/09/13 18:34:06 titato Exp $
*/

// Standard include files
#include "kbool/booleng.h"

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

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

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

//
// The default constructor
//
kbLine::kbLine( 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;
}

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

//
// constructor with a link
//
kbLine::kbLine( kbLink *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 kbLine::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 kbLine::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 intersection, 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 kbLine::AddLineCrossing( B_INT X, B_INT Y, kbLine *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 kbLine::Calculate_Y( B_INT X )
{
    // link must exist to get info about the nodes
    assert( m_link );

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

B_INT kbLine::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 kbLine::Virtual_Point( kbLPoint *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 kbLine::CalculateLineParameters()
{
    // linkmust exist to get beginnode AND endnode
    assert( m_link );

    // if not valid_parameters calculate the parameters
    if ( !m_valid_parameters )
    {
        kbNode * 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 kbLine::CheckIntersect ( kbLine * 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;
    kbNode *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: kbNode *anode = a_line.GetBeginNode()
//
kbNode *kbLine::GetBeginNode()
{
    // link must exist
    assert( m_link );
    return m_link->GetBeginNode();
}


//
// Get the endnode from the line
// usage: kbNode *anode = a_line.GetEndNode()
//
kbNode *kbLine::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 kbLine::Intersect( kbLine * 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 );

    kbNode *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 kbLine::Intersect_simple( kbLine * 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 kbLine::Intersect2( kbNode* crossing, kbLine * 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 kbLine::PointInLine( kbNode *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
    kbNode *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 kbLine::PointOnLine( kbNode *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
    kbNode *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 kbLine::Set( kbLink *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;
}

kbLink* kbLine::GetLink()
{
    return m_link;
}
//
// makes a line same as these
// usage : line1 = line2;
//
kbLine& kbLine::operator=( const kbLine& 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;
}

kbNode* kbLine::OffsetContour( kbLine* const nextline, kbNode* _last_ins, double factor, kbGraph *shape )
{
    kbLink * offs_currentlink;
    kbLine  offs_currentline( m_GC );
    kbLink* offs_nextlink;
    kbLine  offs_nextline( m_GC );
    kbNode* offs_end;

    kbNode* offs_bgn_next;
    kbNode* offs_end_next;

    // make a node from this point
    offs_end = new kbNode( GetEndNode(), m_GC );
    Virtual_Point( offs_end, factor );
    offs_currentlink = new kbLink( 0, _last_ins, offs_end, m_GC );
    offs_currentline.Set( offs_currentlink );

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

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

    offs_nextlink = new kbLink( 0, 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 kbGraph
    shape->AddLink( offs_currentlink );

    delete offs_nextlink;

    return( offs_end );
}


kbNode* kbLine::OffsetContour_rounded( kbLine* const nextline, kbNode* _last_ins, double factor, kbGraph *shape )
{
    kbLink * offs_currentlink;
    kbLine  offs_currentline( m_GC );
    kbLink* offs_nextlink;
    kbLine  offs_nextline( m_GC );
    kbNode* offs_end;
    kbNode* medial_axes_point = new kbNode( m_GC );
    kbNode* bu_last_ins = new kbNode( _last_ins, m_GC );

    kbNode* offs_bgn_next;
    kbNode* offs_end_next;

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

    *_last_ins = *GetBeginNode();
    Virtual_Point( _last_ins, factor );
    Virtual_Point( offs_end, factor );
    offs_currentlink = new kbLink( 0, _last_ins, offs_end, m_GC );
    offs_currentline.Set( offs_currentlink );

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

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

    offs_nextlink = new kbLink( 0, 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 kbGraph
        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;
        kbNode* endarc = new kbNode( offs_bgn_next, m_GC );
        shape->AddLink( offs_currentlink );
        delete offs_nextlink;
        shape->CreateArc( GetEndNode(), &offs_currentline, endarc, fabs( factor ), m_GC->GetInternalCorrectionAber() );
        return( endarc );
    }
}


bool kbLine::OkeForContour( kbLine* const nextline, double factor, kbNode* LastLeft, kbNode* 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;

    kbNode 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 kbLine::Create_Ring_Shape( kbLine* nextline, kbNode** _last_ins_left, kbNode** _last_ins_right, double factor, kbGraph *shape )
{
    kbNode * _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 kbNode( m_link->GetEndNode(), m_GC );
                Virtual_Point( _current, factor );

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

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

                shape->AddLink( *_last_ins_right, _current );
                *_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 kbNode(m_link->GetEndNode());
        Virtual_Point(_current,factor);
     
        // make a link between the current and the previous and add this to kbGraph
        Ishape->AddLink(*_last_ins_left, _current);
        *_last_ins_left=_current;
     
        _current = new kbNode(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 kbLine::Create_Begin_Shape( kbLine* nextline, kbNode** _last_ins_left, kbNode** _last_ins_right, double factor, kbGraph *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 kbNode( m_link->GetEndNode(), m_GC );

            Virtual_Point( *_last_ins_left, factor );

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

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

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

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

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

            *_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 kbNode( nextline->m_link->GetBeginNode(), m_GC );
            Virtual_Point( *_last_ins_left, factor );

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

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

}

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

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

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

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

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

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

}

//
// Generate from the found crossings a part of the kbGraph
//
bool kbLine::ProcessCrossings( TDLI<kbLink>* _LI )
{
    kbNode * last; kbLink *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 kbLink( m_link->GetGraphNum(), ( kbNode* ) linecrosslist->tailitem(), last, m_GC );
        dummy->SetBeenHere();
        dummy->SetGroup( m_link->Group() );
        _LI->insbegin( dummy );
        last = ( kbNode* )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(kbNode* a, kbNode* 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
kbLink* kbLine::ProcessCrossingsSmart(TDLI<kbLink>* _LI)
{
   kbNode *lastinserted;
   kbLink *new_link;
   kbLink *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=(kbNode*) 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 kbLink(graphnum,lastinserted,(kbNode*) 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=((kbNode*)(linecrosslist->headitem()))->GetX();
                 y=((kbNode*)(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
            {  kbNode* todelete=_LI->item()->beginnode;
     new_link->beginnode->Merge(todelete);
     delete todelete;
            }
 
            //set back iter
            (*_LI) << (i+1);
         }
 
         lastinserted=(kbNode*)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=(kbNode*) 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 kbLink(graphnum,lastinserted,(kbNode*) linecrosslist->headitem());
         new_link->group=group;
 
         inbeam=NodeXYsorter(_LI->item()->beginnode,(kbNode*) 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
            {  kbNode* todelete=_LI->item()->beginnode;
     new_link->beginnode->Merge(todelete);
     delete todelete;
            }
            //set back iter
            (*_LI) << (i+1);
         }
 
         lastinserted=(kbNode*)linecrosslist->headitem();
         linecrosslist->removehead();
      }
   }
 delete linecrosslist;
 linecrosslist=NULL;
 
   return returnlink;
}
*/

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

    return( -1 );
}

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

    return( -1 );
}

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

static int NODE_Y_DESCENDING_L( kbNode* a, kbNode* 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 kbLine::SortLineCrossings()
{
    TDLI<kbNode> 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 kbLine::AddCrossing( kbNode *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<kbNode> I( linecrosslist );
        if ( !I.has( a_node ) )
            I.insend( a_node );
    }
}

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

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

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

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