1 /*! \file kbool/src/booleng.cpp
2 \author Klaas Holwerda
3
4 Copyright: 2001-2004 (C) Klaas Holwerda
5
6 Licence: see kboollicense.txt
7
8 RCS-ID: $Id: booleng.cpp,v 1.11 2005/05/24 19:13:38 titato Exp $
9 */
10
11 #ifdef __GNUG__
12 #pragma implementation
13 #endif
14
15 #include <math.h>
16 #include <time.h>
17
18 #include "kbool/include/booleng.h"
19 #include "kbool/include/link.h"
20 #include "kbool/include/line.h"
21 #include "kbool/include/node.h"
22 #include "kbool/include/graph.h"
23 #include "kbool/include/graphlst.h"
24
bmin(B_INT const value1,B_INT const value2)25 B_INT bmin(B_INT const value1, B_INT const value2)
26 {
27 return((value1 < value2) ? value1 : value2 );
28 }
29
bmax(B_INT const value1,B_INT const value2)30 B_INT bmax(B_INT const value1, B_INT const value2)
31 {
32 return((value1 > value2) ? value1 : value2 );
33 }
34
babs(B_INT a)35 B_INT babs(B_INT a)
36 {
37 if (a < 0) a=-a;
38 return a;
39 }
40
41 //-------------------------------------------------------------------/
42 //----------------- Bool_Engine_Error -------------------------------/
43 //-------------------------------------------------------------------/
44
Bool_Engine_Error(const char * message,const char * header,int degree,int fatal)45 Bool_Engine_Error::Bool_Engine_Error(const char* message, const char* header, int degree, int fatal)
46 {
47 _message = new char[LINELENGTH];
48 _header = new char[LINELENGTH];
49 if (message)
50 strcpy(_message, message);
51 else
52 strcpy(_message,"non specified");
53
54 if (header)
55 strcpy(_header, header);
56 else
57 strcpy(_header,"non specified");
58
59 _degree = degree;
60 _fatal = fatal;
61
62 }
63
Bool_Engine_Error(const Bool_Engine_Error & a)64 Bool_Engine_Error::Bool_Engine_Error(const Bool_Engine_Error& a)
65 {
66 _message = new char[LINELENGTH];
67 _header = new char[LINELENGTH];
68 if (a._message)
69 strcpy(_message, a._message);
70 else
71 strcpy(_message,"non specified");
72
73 if (a._header)
74 strcpy(_header, a._header);
75 else
76 strcpy(_header,"non specified");
77
78 _degree = a._degree;
79 _fatal = a._fatal;
80
81 }
82
~Bool_Engine_Error()83 Bool_Engine_Error::~Bool_Engine_Error()
84 {
85 strcpy(_message,"");
86 strcpy(_header,"");
87 delete _message;
88 delete _header;
89 }
90
GetErrorMessage()91 char* Bool_Engine_Error::GetErrorMessage()
92 {
93 return _message;
94 }
95
GetHeaderMessage()96 char* Bool_Engine_Error::GetHeaderMessage()
97 {
98 return _header;
99 }
100
GetErrorDegree()101 int Bool_Engine_Error::GetErrorDegree()
102 {
103 return _degree;
104 }
105
GetFatal()106 int Bool_Engine_Error::GetFatal()
107 {
108 return _fatal;
109 }
110
111 //-------------------------------------------------------------------/
112 //----------------- Bool_Engine -------------------------------------/
113 //-------------------------------------------------------------------/
114
Bool_Engine()115 Bool_Engine::Bool_Engine()
116 {
117 _linkiter=new TDLI<KBoolLink>();
118 m_intersectionruns = 1;
119
120 m_orientationEntryMode = false;
121 m_doLinkHoles = true;
122
123 m_graphlist = new GraphList(this);
124 m_ACCUR = 1e-4;
125 m_WINDINGRULE = true;
126 m_GraphToAdd = NULL;
127 m_firstNodeToAdd = NULL;
128 m_lastNodeToAdd = NULL;
129
130 m_logfile = NULL;
131
132 #if KBOOL_LOG == 1
133 SetLog( true );
134 #else
135 SetLog( false );
136 #endif
137 }
138
~Bool_Engine()139 Bool_Engine::~Bool_Engine()
140 {
141 if (m_logfile != NULL)
142 fclose (m_logfile);
143
144 delete _linkiter;
145 delete m_graphlist;
146 }
147
SetLog(bool OnOff)148 void Bool_Engine::SetLog( bool OnOff )
149 {
150 m_doLog = OnOff;
151 if ( m_doLog )
152 {
153 if ( m_logfile == NULL )
154 {
155 // create a new logfile
156 m_logfile = fopen(KBOOL_LOGFILE, "w");
157 if (m_logfile == NULL)
158 fprintf(stderr,"Bool_Engine: Unable to write to Boolean Engine logfile\n");
159 else
160 {
161 time_t timer;
162 struct tm * today;
163 timer = time(NULL);
164 today = localtime(&timer);
165
166 fprintf(m_logfile, "Logfile created on:\t\t\t%s", ctime( &timer ) );
167 }
168 }
169 }
170 else
171 {
172 if (m_logfile != NULL)
173 {
174 fclose (m_logfile);
175 m_logfile = NULL;
176 }
177 }
178 }
179
SetState(const char * process)180 void Bool_Engine::SetState( const char* process )
181 {
182 Write_Log(process);
183 }
184
error(const char * text,const char * title)185 void Bool_Engine::error(const char *text, const char *title)
186 {
187 Write_Log("FATAL ERROR: ", title);
188 Write_Log("FATAL ERROR: ", text);
189 throw Bool_Engine_Error(" Fatal Error", "Fatal Error", 9, 1);
190 };
191
info(const char * text,const char * title)192 void Bool_Engine::info(const char *text, const char *title)
193 {
194 Write_Log("FATAL ERROR: ", title);
195 Write_Log("FATAL ERROR: ", text);
196 };
197
SetMarge(double marge)198 void Bool_Engine::SetMarge(double marge)
199 {
200 m_MARGE = marge;
201 Write_Log("Bool_Engine::m_MARGE = %f\n", m_MARGE);
202 }
203
GetAccur()204 double Bool_Engine::GetAccur()
205 {
206 return m_ACCUR;
207 }
208
SetRoundfactor(double roundfac)209 void Bool_Engine::SetRoundfactor(double roundfac)
210 {
211 m_ROUNDFACTOR = roundfac;
212 Write_Log("Bool_Engine::m_ROUNDFACTOR = %f\n", m_ROUNDFACTOR);
213 }
214
GetRoundfactor()215 double Bool_Engine::GetRoundfactor()
216 {
217 return m_ROUNDFACTOR;
218 }
219
GetMarge()220 double Bool_Engine::GetMarge()
221 {
222 return m_MARGE;
223 }
224
SetDGrid(double dgrid)225 void Bool_Engine::SetDGrid(double dgrid)
226 {
227 m_DGRID = dgrid;
228 Write_Log("Bool_Engine::m_DGRID = %f\n", m_DGRID);
229 }
230
GetDGrid()231 double Bool_Engine::GetDGrid()
232 {
233 return m_DGRID;
234 }
235
SetGrid(B_INT grid)236 void Bool_Engine::SetGrid(B_INT grid)
237 {
238 m_GRID = grid;
239 Write_Log("Bool_Engine::m_GRID = %lld\n", m_GRID);
240 }
241
GetGrid()242 B_INT Bool_Engine::GetGrid()
243 {
244 return m_GRID;
245 }
246
SetCorrectionAber(double aber)247 void Bool_Engine::SetCorrectionAber(double aber)
248 {
249 m_CORRECTIONABER = aber;
250 Write_Log("Bool_Engine::m_CORRECTIONABER = %f\n", m_CORRECTIONABER);
251 }
252
GetCorrectionAber()253 double Bool_Engine::GetCorrectionAber()
254 {
255 return m_CORRECTIONABER;
256 }
257
SetCorrectionFactor(double aber)258 void Bool_Engine::SetCorrectionFactor(double aber)
259 {
260 m_CORRECTIONFACTOR = aber;
261 Write_Log("Bool_Engine::m_CORRECTIONFACTOR = %f\n", m_CORRECTIONFACTOR );
262 }
263
GetCorrectionFactor()264 double Bool_Engine::GetCorrectionFactor()
265 {
266 return m_CORRECTIONFACTOR;
267 }
268
SetSmoothAber(double aber)269 void Bool_Engine::SetSmoothAber(double aber)
270 {
271 m_SMOOTHABER = aber;
272 Write_Log("Bool_Engine::m_SMOOTHABER = %f\n",m_SMOOTHABER );
273 }
274
GetSmoothAber()275 double Bool_Engine::GetSmoothAber()
276 {
277 return m_SMOOTHABER;
278 }
279
SetMaxlinemerge(double maxline)280 void Bool_Engine::SetMaxlinemerge(double maxline)
281 {
282 m_MAXLINEMERGE = maxline;
283 Write_Log("Bool_Engine::m_MAXLINEMERGE = %f\n",m_MAXLINEMERGE );
284 }
285
GetMaxlinemerge()286 double Bool_Engine::GetMaxlinemerge()
287 {
288 return m_MAXLINEMERGE;
289 }
290
SetWindingRule(bool rule)291 void Bool_Engine::SetWindingRule(bool rule)
292 {
293 m_WINDINGRULE = rule;
294 }
295
GetWindingRule()296 bool Bool_Engine::GetWindingRule()
297 {
298 return m_WINDINGRULE;
299 }
300
301
SetInternalMarge(B_INT marge)302 void Bool_Engine::SetInternalMarge( B_INT marge )
303 {
304 m_MARGE = (double)marge/m_GRID/m_DGRID;
305 }
306
GetInternalMarge()307 B_INT Bool_Engine::GetInternalMarge()
308 {
309 return (B_INT) ( m_MARGE*m_GRID*m_DGRID );
310 }
311
GetInternalCorrectionAber()312 double Bool_Engine::GetInternalCorrectionAber()
313 {
314 return m_CORRECTIONABER*m_GRID*m_DGRID;
315 }
316
GetInternalCorrectionFactor()317 double Bool_Engine::GetInternalCorrectionFactor()
318 {
319 return m_CORRECTIONFACTOR*m_GRID*m_DGRID;
320 }
321
GetInternalSmoothAber()322 double Bool_Engine::GetInternalSmoothAber()
323 {
324 return m_SMOOTHABER*m_GRID*m_DGRID;
325 }
326
GetInternalMaxlinemerge()327 B_INT Bool_Engine::GetInternalMaxlinemerge()
328 {
329 return (B_INT) ( m_MAXLINEMERGE*m_GRID*m_DGRID );
330 }
331
332 #define TRIALS 30
333
Do_Operation(BOOL_OP operation)334 bool Bool_Engine::Do_Operation(BOOL_OP operation)
335 {
336
337 #if KBOOL_DEBUG
338 GraphList* saveme = new GraphList( m_graphlist );
339 #endif
340
341 try
342 {
343 switch (operation)
344 {
345 case (BOOL_OR):
346 case (BOOL_AND):
347 case (BOOL_EXOR):
348 case (BOOL_A_SUB_B):
349 case (BOOL_B_SUB_A):
350 m_graphlist->Boolean(operation, m_intersectionruns);
351 break;
352 case (BOOL_CORRECTION):
353 m_graphlist->Correction();
354 break;
355 case (BOOL_MAKERING):
356 m_graphlist->MakeRings();
357 break;
358 case (BOOL_SMOOTHEN):
359 m_graphlist->Smoothen( GetInternalSmoothAber() );
360 break;
361 default:
362 {
363 error("Wrong operation","Command Error");
364 return false;
365 }
366 }
367 }
368 catch (Bool_Engine_Error& error)
369 {
370
371 #if KBOOL_DEBUG
372 delete m_graphlist;
373 m_graphlist = new GraphList( saveme );
374 m_graphlist->WriteGraphsKEY(this);
375 #endif
376
377 if (m_logfile != NULL)
378 {
379 fclose (m_logfile);
380 m_logfile = NULL;
381 }
382
383 info(error.GetErrorMessage(), "error");
384 throw error;
385 }
386 catch(...)
387 {
388
389 #if KBOOL_DEBUG
390 delete m_graphlist;
391 m_graphlist = new GraphList( saveme );
392 m_graphlist->WriteGraphsKEY(this);
393 #endif
394
395 if (m_logfile != NULL)
396 {
397 fclose (m_logfile);
398 m_logfile = NULL;
399 }
400
401 info("Unknown exception", "error");
402 throw ;
403 }
404
405 #if KBOOL_DEBUG
406 delete saveme;
407 #endif
408
409 return true;
410 }
411
StartPolygonAdd(GroupType A_or_B)412 bool Bool_Engine::StartPolygonAdd(GroupType A_or_B)
413 {
414 #if KBOOL_DEBUG
415 if (m_logfile != NULL)
416 fprintf(m_logfile, "-> StartPolygonAdd(%d)\n", A_or_B);
417 #endif
418 if (m_GraphToAdd != NULL)
419 return false;
420
421 Graph *myGraph = new Graph(this);
422 m_graphlist->insbegin(myGraph);
423 m_GraphToAdd = myGraph;
424 m_groupType = A_or_B;
425
426 return true;
427 }
428
AddPoint(double x,double y,int user_data)429 bool Bool_Engine::AddPoint(double x, double y, int user_data)
430 {
431 if (m_GraphToAdd == NULL){return false;}
432
433 double scaledx = x * m_DGRID * m_GRID;
434 double scaledy = y * m_DGRID * m_GRID;
435
436 if ( scaledx > MAXB_INT || scaledx < MINB_INT )
437 error("X coordinate of vertex to big", "" );
438 if ( scaledy > MAXB_INT || scaledy < MINB_INT )
439 error("Y coordinate of vertex to big", "" );
440
441
442 B_INT rintx = ((B_INT) (x * m_DGRID)) * m_GRID;
443 B_INT rinty = ((B_INT) (y * m_DGRID)) * m_GRID;
444 Node *myNode = new Node( rintx, rinty, this );
445
446 // adding first point to graph
447 if (m_firstNodeToAdd == NULL)
448 {
449 #if KBOOL_DEBUG
450 if (m_logfile != NULL)
451 {
452 fprintf(m_logfile, "-> AddPt() *FIRST* :");
453 fprintf(m_logfile, " input: x = %f, y = %f\n", x, y);
454 fprintf(m_logfile, " input: x = %I64d, y = %I64d\n", rintx, rinty) ;
455 }
456 #endif
457
458 m_firstNodeToAdd = (Node *) myNode;
459 m_lastNodeToAdd = (Node *) myNode;
460 }
461 else
462 {
463 #if KBOOL_DEBUG
464 if (m_logfile != NULL)
465 {
466 fprintf(m_logfile, "-> AddPt():");
467 fprintf(m_logfile, " input: x = %f, y = %f\n", x, y);
468 fprintf(m_logfile, " input: x = %I64d, y = %I64d\n", rintx, rinty) ;
469 }
470 #endif
471
472 m_GraphToAdd->AddLink(m_lastNodeToAdd, myNode, user_data);
473 m_lastNodeToAdd = (Node *) myNode;
474 }
475
476 return true;
477 }
478
EndPolygonAdd()479 bool Bool_Engine::EndPolygonAdd()
480 {
481 if (m_GraphToAdd == NULL) {return false;}
482
483 m_GraphToAdd->AddLink(m_lastNodeToAdd, m_firstNodeToAdd, 0);
484 m_GraphToAdd->SetGroup(m_groupType);
485 m_GraphToAdd = NULL;
486 m_lastNodeToAdd = NULL;
487 m_firstNodeToAdd = NULL;
488
489 return true;
490 }
491
StartPolygonGet()492 bool Bool_Engine::StartPolygonGet()
493 {
494 if (!m_graphlist->empty())
495 {
496 m_getGraph = (Graph*) m_graphlist->headitem();
497 m_getLink = m_getGraph->GetFirstLink();
498 m_getNode = m_getLink->GetBeginNode();
499 m_numPtsInPolygon = m_getGraph->GetNumberOfLinks();
500 m_numNodesVisited = 0;
501 return true;
502 }
503 else
504 {
505 return false;
506 }
507 }
508
PolygonHasMorePoints()509 bool Bool_Engine::PolygonHasMorePoints()
510 {
511 // see if first point
512 if (m_numNodesVisited == 0)
513 {
514 // don't need to touch the m_getNode
515 m_numNodesVisited++;
516 return true;
517 }
518
519 if (m_numNodesVisited < m_numPtsInPolygon)
520 {
521 // traverse to the next node
522 m_getNode = m_getLink->GetOther(m_getNode);
523 m_getLink = m_getLink->Forth(m_getNode);
524
525 m_numNodesVisited++;
526 return true;
527 }
528 else
529 {
530 return false;
531 }
532 }
533
EndPolygonGet()534 void Bool_Engine::EndPolygonGet()
535 {
536 m_graphlist->removehead();
537 delete m_getGraph;
538 }
539
GetPolygonXPoint()540 double Bool_Engine::GetPolygonXPoint()
541 {
542 return m_getNode->GetX()/m_GRID/m_DGRID;
543 }
544
GetPolygonYPoint()545 double Bool_Engine::GetPolygonYPoint()
546 {
547 return m_getNode->GetY()/m_GRID/m_DGRID;
548 }
549
GetHoleSegment()550 bool Bool_Engine::GetHoleSegment()
551 {
552 if (m_getLink->GetHole())
553 return true;
554 return false;
555 }
556
GetHoleConnectionSegment()557 bool Bool_Engine::GetHoleConnectionSegment()
558 {
559 if (m_getLink->GetHoleLink())
560 return true;
561 return false;
562 }
563
GetPolygonPointEdgeType()564 kbEdgeType Bool_Engine::GetPolygonPointEdgeType()
565 {
566 // see if the point is the beginning of a false edge
567 if ( m_getLink->GetHoleLink() )
568 return KB_FALSE_EDGE;
569 else
570 // it's either an outside or inside edge
571 if ( m_getLink->GetHole() )
572 return KB_INSIDE_EDGE;
573 else
574 return KB_OUTSIDE_EDGE;
575 }
576
GetPolygonPointUserData()577 int Bool_Engine::GetPolygonPointUserData()
578 {
579 return m_getLink->m_user_data;
580 }
581
582
Write_Log(const char * msg1)583 void Bool_Engine::Write_Log(const char *msg1)
584 {
585 if (m_logfile == NULL)
586 return;
587
588 fprintf(m_logfile,"%s \n",msg1);
589 }
590
Write_Log(const char * msg1,const char * msg2)591 void Bool_Engine::Write_Log(const char *msg1, const char*msg2)
592 {
593 if (m_logfile == NULL)
594 return;
595
596 fprintf(m_logfile,"%s %s\n",msg1, msg2);
597 }
598
Write_Log(const char * fmt,double dval)599 void Bool_Engine::Write_Log(const char *fmt, double dval)
600 {
601 if (m_logfile == NULL)
602 return;
603
604 fprintf(m_logfile,fmt,dval);
605 }
606
Write_Log(const char * fmt,B_INT bval)607 void Bool_Engine::Write_Log(const char *fmt, B_INT bval)
608 {
609 if (m_logfile == NULL)
610 return;
611
612 fprintf(m_logfile,fmt,bval);
613 }
614