booleng.cpp 12.2 KB
Newer Older
1 2
/*! \file src/booleng.cpp
    \author Klaas Holwerda
charras's avatar
charras committed
3
 
4
    Copyright: 2001-2004 (C) Klaas Holwerda
charras's avatar
charras committed
5 6 7
 
    Licence: see kboollicense.txt 
 
8
    RCS-ID: $Id: booleng.cpp,v 1.7 2009/09/14 16:50:12 titato Exp $
9 10
*/

11
#include "kbool/booleng.h"
12 13 14

#include <time.h>

15 16 17 18 19
#include "kbool/link.h"
#include "kbool/line.h"
#include "kbool/node.h"
#include "kbool/graph.h"
#include "kbool/graphlst.h"
20

21
B_INT bmin( B_INT const value1, B_INT const value2 )
22
{
23
    return( ( value1 < value2 ) ? value1 : value2 );
24 25
}

26
B_INT bmax( B_INT const value1, B_INT const value2 )
27
{
28
    return( ( value1 > value2 ) ? value1 : value2 );
29 30
}

31
B_INT babs( B_INT a )
32
{
33 34
    if ( a < 0 ) a = -a;
    return a;
35 36 37 38 39 40
}

//-------------------------------------------------------------------/
//----------------- Bool_Engine_Error -------------------------------/
//-------------------------------------------------------------------/

charras's avatar
charras committed
41
Bool_Engine_Error::Bool_Engine_Error( string message, string header, int degree, int fatal )
42
{
charras's avatar
charras committed
43 44
    _message = message;
    _header = header;
45

46 47
    _degree = degree;
    _fatal = fatal;
48 49 50

}

51
Bool_Engine_Error::Bool_Engine_Error( const Bool_Engine_Error& a )
52
{
charras's avatar
charras committed
53 54
    _message = a._message;
    _header = a._header;
55

56 57
    _degree = a._degree;
    _fatal = a._fatal;
58 59 60 61 62

}

Bool_Engine_Error::~Bool_Engine_Error()
{
charras's avatar
charras committed
63 64
    _message = "";
    _header = "";
65 66
}

charras's avatar
charras committed
67
string Bool_Engine_Error::GetErrorMessage()
68
{
69
    return _message;
70 71
}

charras's avatar
charras committed
72
string Bool_Engine_Error::GetHeaderMessage()
73
{
74
    return _header;
75 76 77 78
}

int Bool_Engine_Error::GetErrorDegree()
{
79
    return _degree;
80 81 82 83
}

int Bool_Engine_Error::GetFatal()
{
84
    return _fatal;
85 86 87 88 89 90 91 92
}

//-------------------------------------------------------------------/
//----------------- Bool_Engine -------------------------------------/
//-------------------------------------------------------------------/

Bool_Engine::Bool_Engine()
{
charras's avatar
charras committed
93
    _linkiter = new TDLI<kbLink>();
94
    m_intersectionruns = 1;
95

96 97
    m_orientationEntryMode = false;
    m_doLinkHoles = true;
98
    m_allowNonTopHoleLinking = true;
99

charras's avatar
charras committed
100
    m_graphlist = new kbGraphList( this );
101 102 103 104 105 106 107
    m_ACCUR = 1e-4;
    m_WINDINGRULE = true;
    m_GraphToAdd = NULL;
    m_firstNodeToAdd = NULL;
    m_lastNodeToAdd = NULL;

    m_logfile = NULL;
108 109

#if KBOOL_LOG == 1
110
    SetLog( true );
111
#else
112
    SetLog( false );
113 114 115 116 117
#endif
}

Bool_Engine::~Bool_Engine()
{
118 119
    if ( m_logfile != NULL )
        fclose ( m_logfile );
120

121 122
    delete _linkiter;
    delete m_graphlist;
123 124 125 126
}

void Bool_Engine::SetLog( bool OnOff )
{
127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154
    m_doLog = OnOff;
    if ( m_doLog )
    {
        if ( m_logfile == NULL )
        {
            // create a new logfile
            m_logfile = fopen( KBOOL_LOGFILE, "w" );
            if ( m_logfile == NULL )
                fprintf( stderr, "Bool_Engine: Unable to write to Boolean Engine logfile\n" );
            else
            {
                time_t timer;
                struct tm * today;
                timer = time( NULL );
                today = localtime( &timer );

                fprintf( m_logfile, "Logfile created on:\t\t\t%s", ctime( &timer ) );
            }
        }
    }
    else
    {
        if ( m_logfile != NULL )
        {
            fclose ( m_logfile );
            m_logfile = NULL;
        }
    }
155 156
}

charras's avatar
charras committed
157
void Bool_Engine::SetState( string process )
158
{
159
    Write_Log( process );
160 161
}

charras's avatar
charras committed
162
void Bool_Engine::error( string text, string title )
163
{
164 165 166
    Write_Log( "FATAL ERROR: ", title );
    Write_Log( "FATAL ERROR: ", text );
    throw Bool_Engine_Error( " Fatal Error", "Fatal Error", 9, 1 );
jean-pierre charras's avatar
jean-pierre charras committed
167
}
168

charras's avatar
charras committed
169
void Bool_Engine::info( string text, string title )
170
{
171 172
    Write_Log( "FATAL ERROR: ", title );
    Write_Log( "FATAL ERROR: ", text );
jean-pierre charras's avatar
jean-pierre charras committed
173
}
174

175
void Bool_Engine::SetMarge( double marge )
176 177
{
    m_MARGE = marge;
178
    Write_Log( "Bool_Engine::m_MARGE = %f\n", m_MARGE );
179 180 181 182 183 184 185
}

double Bool_Engine::GetAccur()
{
    return m_ACCUR;
}

186
void Bool_Engine::SetRoundfactor( double roundfac )
187 188
{
    m_ROUNDFACTOR = roundfac;
189
    Write_Log( "Bool_Engine::m_ROUNDFACTOR = %f\n", m_ROUNDFACTOR );
190 191 192 193 194 195 196 197 198 199 200 201
}

double Bool_Engine::GetRoundfactor()
{
    return m_ROUNDFACTOR;
}

double Bool_Engine::GetMarge()
{
    return m_MARGE;
}

202
void Bool_Engine::SetDGrid( double dgrid )
203 204
{
    m_DGRID = dgrid;
205
    Write_Log( "Bool_Engine::m_DGRID = %f\n", m_DGRID );
206 207 208 209 210 211 212
}

double Bool_Engine::GetDGrid()
{
    return m_DGRID;
}

213
void Bool_Engine::SetGrid( B_INT grid )
214 215
{
    m_GRID = grid;
216
    Write_Log( "Bool_Engine::m_GRID = %lld\n", m_GRID );
217 218 219 220 221 222 223
}

B_INT Bool_Engine::GetGrid()
{
    return m_GRID;
}

224
void Bool_Engine::SetCorrectionAber( double aber )
225 226
{
    m_CORRECTIONABER = aber;
227
    Write_Log( "Bool_Engine::m_CORRECTIONABER = %f\n", m_CORRECTIONABER );
228 229 230 231 232 233 234
}

double Bool_Engine::GetCorrectionAber()
{
    return m_CORRECTIONABER;
}

235
void Bool_Engine::SetCorrectionFactor( double aber )
236 237
{
    m_CORRECTIONFACTOR = aber;
238
    Write_Log( "Bool_Engine::m_CORRECTIONFACTOR = %f\n", m_CORRECTIONFACTOR );
239 240 241 242 243 244 245
}

double Bool_Engine::GetCorrectionFactor()
{
    return m_CORRECTIONFACTOR;
}

246
void Bool_Engine::SetSmoothAber( double aber )
247 248
{
    m_SMOOTHABER = aber;
249
    Write_Log( "Bool_Engine::m_SMOOTHABER = %f\n", m_SMOOTHABER );
250 251 252 253 254 255 256
}

double Bool_Engine::GetSmoothAber()
{
    return m_SMOOTHABER;
}

257
void Bool_Engine::SetMaxlinemerge( double maxline )
258 259
{
    m_MAXLINEMERGE = maxline;
260
    Write_Log( "Bool_Engine::m_MAXLINEMERGE = %f\n", m_MAXLINEMERGE );
261 262 263 264 265 266 267
}

double Bool_Engine::GetMaxlinemerge()
{
    return m_MAXLINEMERGE;
}

268
void Bool_Engine::SetWindingRule( bool rule )
269 270 271 272 273 274 275 276 277 278 279 280
{
    m_WINDINGRULE = rule;
}

bool Bool_Engine::GetWindingRule()
{
    return m_WINDINGRULE;
}


void Bool_Engine::SetInternalMarge( B_INT marge )
{
281
    m_MARGE = ( double )marge / m_GRID / m_DGRID;
282 283 284 285
}

B_INT Bool_Engine::GetInternalMarge()
{
286
    return ( B_INT ) ( m_MARGE * m_GRID * m_DGRID );
287 288 289 290
}

double Bool_Engine::GetInternalCorrectionAber()
{
291
    return  m_CORRECTIONABER * m_GRID * m_DGRID;
292 293 294 295
}

double Bool_Engine::GetInternalCorrectionFactor()
{
296
    return m_CORRECTIONFACTOR * m_GRID * m_DGRID;
297 298 299 300
}

double Bool_Engine::GetInternalSmoothAber()
{
301
    return m_SMOOTHABER * m_GRID * m_DGRID;
302 303 304 305
}

B_INT Bool_Engine::GetInternalMaxlinemerge()
{
306
    return ( B_INT ) ( m_MAXLINEMERGE * m_GRID * m_DGRID );
307 308
}

309
#define TRIALS 30
310

311
bool Bool_Engine::Do_Operation( BOOL_OP operation )
312 313 314
{

#if KBOOL_DEBUG
charras's avatar
charras committed
315
    kbGraphList * saveme = new kbGraphList( m_graphlist );
316 317
#endif

318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346
    try
    {
        switch ( operation )
        {
            case ( BOOL_OR ):
                        case ( BOOL_AND ):
                            case ( BOOL_EXOR ):
                                case ( BOOL_A_SUB_B ):
                                    case ( BOOL_B_SUB_A ):
                                            m_graphlist->Boolean( operation, m_intersectionruns );
                break;
            case ( BOOL_CORRECTION ):
                            m_graphlist->Correction();
                break;
            case ( BOOL_MAKERING ):
                            m_graphlist->MakeRings();
                break;
            case ( BOOL_SMOOTHEN ):
                            m_graphlist->Smoothen( GetInternalSmoothAber() );
                break;
            default:
    {
                error( "Wrong operation", "Command Error" );
                return false;
            }
        }
    }
    catch ( Bool_Engine_Error & error )
    {
347 348

#if KBOOL_DEBUG
349
        delete m_graphlist;
charras's avatar
charras committed
350
        m_graphlist = new kbGraphList( saveme );
351
        m_graphlist->WriteGraphsKEY( this );
352 353
#endif

354 355 356 357 358
        if ( m_logfile != NULL )
        {
            fclose ( m_logfile );
            m_logfile = NULL;
        }
359

360 361 362 363 364
        info( error.GetErrorMessage(), "error" );
        throw error;
    }
    catch( ... )
    {
365 366

#if KBOOL_DEBUG
367
        delete m_graphlist;
charras's avatar
charras committed
368
        m_graphlist = new kbGraphList( saveme );
369
        m_graphlist->WriteGraphsKEY( this );
370 371
#endif

372 373 374 375 376
        if ( m_logfile != NULL )
        {
            fclose ( m_logfile );
            m_logfile = NULL;
        }
377

378 379 380
        info( "Unknown exception", "error" );
        throw ;
    }
381 382

#if KBOOL_DEBUG
383
    delete saveme;
384 385
#endif

386
    return true;
387 388
}

389
bool Bool_Engine::StartPolygonAdd( GroupType A_or_B )
390 391
{
#if KBOOL_DEBUG
392 393
    if ( m_logfile != NULL )
        fprintf( m_logfile, "-> StartPolygonAdd(%d)\n", A_or_B );
394
#endif
395 396
    if ( m_GraphToAdd != NULL )
        return false;
397

charras's avatar
charras committed
398
    kbGraph *myGraph = new kbGraph( this );
399
    m_graphlist->insbegin( myGraph );
400 401 402 403 404 405
    m_GraphToAdd = myGraph;
    m_groupType = A_or_B;

    return true;
}

406
bool Bool_Engine::AddPoint( double x, double y )
407
{
408
    if ( m_GraphToAdd == NULL ){return false;}
409

410 411
    double scaledx = x * m_DGRID * m_GRID;
    double scaledy = y * m_DGRID * m_GRID;
412

413 414 415 416
    if ( scaledx > MAXB_INT  || scaledx < MINB_INT )
        error( "X coordinate of vertex to big", "" );
    if ( scaledy > MAXB_INT || scaledy < MINB_INT )
        error( "Y coordinate of vertex to big", "" );
417 418


419 420
    B_INT rintx = ( ( B_INT ) ( x * m_DGRID ) ) * m_GRID;
    B_INT rinty = ( ( B_INT ) ( y * m_DGRID ) ) * m_GRID;
charras's avatar
charras committed
421
    kbNode *myNode = new kbNode( rintx, rinty, this );
422 423

    // adding first point to graph
424 425
    if ( m_firstNodeToAdd == NULL )
    {
426
#if KBOOL_DEBUG
427 428 429 430 431 432
        if ( m_logfile != NULL )
        {
            fprintf( m_logfile, "-> AddPt() *FIRST* :" );
            fprintf( m_logfile, " input: x = %f, y = %f\n", x, y );
            fprintf( m_logfile, " input: x = %I64d, y = %I64d\n", rintx, rinty ) ;
        }
433 434
#endif

charras's avatar
charras committed
435 436
        m_firstNodeToAdd = ( kbNode * ) myNode;
        m_lastNodeToAdd  = ( kbNode * ) myNode;
437 438 439
    }
    else
    {
440
#if KBOOL_DEBUG
441 442 443 444 445 446
        if ( m_logfile != NULL )
        {
            fprintf( m_logfile, "-> AddPt():" );
            fprintf( m_logfile, " input: x = %f, y = %f\n", x, y );
            fprintf( m_logfile, " input: x = %I64d, y = %I64d\n", rintx, rinty ) ;
        }
447 448
#endif

449
        m_GraphToAdd->AddLink( m_lastNodeToAdd, myNode );
charras's avatar
charras committed
450
        m_lastNodeToAdd = ( kbNode * ) myNode;
451
    }
452

453
    return true;
454 455 456 457
}

bool Bool_Engine::EndPolygonAdd()
{
458
    if ( m_GraphToAdd == NULL ) {return false;}
459

460 461 462 463 464
    m_GraphToAdd->AddLink( m_lastNodeToAdd, m_firstNodeToAdd );
    m_GraphToAdd->SetGroup( m_groupType );
    m_GraphToAdd = NULL;
    m_lastNodeToAdd  = NULL;
    m_firstNodeToAdd = NULL;
465

466
    return true;
467 468 469 470
}

bool Bool_Engine::StartPolygonGet()
{
471 472
    if ( !m_graphlist->empty() )
    {
charras's avatar
charras committed
473
        m_getGraph = ( kbGraph* ) m_graphlist->headitem();
474 475 476 477 478 479 480 481 482 483
        m_getLink  = m_getGraph->GetFirstLink();
        m_getNode  = m_getLink->GetBeginNode();
        m_numPtsInPolygon = m_getGraph->GetNumberOfLinks();
        m_numNodesVisited = 0;
        return true;
    }
    else
    {
        return false;
    }
484 485 486 487 488
}

bool Bool_Engine::PolygonHasMorePoints()
{
    // see if first point
489
    if ( m_numNodesVisited == 0 )
490 491 492 493 494 495
    {
        // don't need to touch the m_getNode
        m_numNodesVisited++;
        return true;
    }

496
    if ( m_numNodesVisited < m_numPtsInPolygon )
497 498
    {
        // traverse to the next node
499 500
        m_getNode = m_getLink->GetOther( m_getNode );
        m_getLink = m_getLink->Forth( m_getNode );
501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518

        m_numNodesVisited++;
        return true;
    }
    else
    {
        return false;
    }
}

void Bool_Engine::EndPolygonGet()
{
    m_graphlist->removehead();
    delete m_getGraph;
}

double Bool_Engine::GetPolygonXPoint()
{
519
    return m_getNode->GetX() / m_GRID / m_DGRID;
520 521 522 523
}

double Bool_Engine::GetPolygonYPoint()
{
524
    return m_getNode->GetY() / m_GRID / m_DGRID;
525 526 527 528
}

bool Bool_Engine::GetHoleSegment()
{
529 530 531
    if ( m_getLink->GetHole() )
        return true;
    return false;
532 533 534 535
}

bool Bool_Engine::GetHoleConnectionSegment()
{
536 537 538
    if ( m_getLink->GetHoleLink() )
        return true;
    return false;
539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554
}

kbEdgeType Bool_Engine::GetPolygonPointEdgeType()
{
    // see if the point is the beginning of a false edge
    if ( m_getLink->GetHoleLink() )
        return KB_FALSE_EDGE;
    else
        // it's either an outside or inside edge
        if ( m_getLink->GetHole() )
            return KB_INSIDE_EDGE;
        else
            return KB_OUTSIDE_EDGE;
}


charras's avatar
charras committed
555
void Bool_Engine::Write_Log( string msg1 )
556
{
557 558
    if ( m_logfile == NULL )
        return;
559

charras's avatar
charras committed
560
    fprintf( m_logfile, "%s \n", msg1.c_str() );
561 562
}

charras's avatar
charras committed
563
void Bool_Engine::Write_Log( string msg1, string msg2 )
564
{
565 566
    if ( m_logfile == NULL )
        return;
567

charras's avatar
charras committed
568
    fprintf( m_logfile, "%s %s\n", msg1.c_str(), msg2.c_str() );
569 570
}

charras's avatar
charras committed
571
void Bool_Engine::Write_Log( string fmt, double dval )
572
{
573 574
    if ( m_logfile == NULL )
        return;
575

charras's avatar
charras committed
576
    fprintf( m_logfile, fmt.c_str(), dval );
577 578
}

charras's avatar
charras committed
579
void Bool_Engine::Write_Log( string fmt, B_INT bval )
580
{
581 582
    if ( m_logfile == NULL )
        return;
583

charras's avatar
charras committed
584
    fprintf( m_logfile, fmt.c_str(), bval );
585
}