]> git.saurik.com Git - wxWidgets.git/blob - contrib/src/canvas/liner.cpp
added tree layout define
[wxWidgets.git] / contrib / src / canvas / liner.cpp
1 /*
2 Program wxLine.CPP
3 Purpose Mainly used for calculating crossings
4 Last Update 05-12-1995
5 */
6
7 #ifdef __GNUG__
8 #pragma implementation "liner.cpp"
9 #endif
10
11 // For compilers that support precompilation, includes "wx/wx.h".
12 #include "wx/wxprec.h"
13
14 #ifdef __BORLANDC__
15 #pragma hdrstop
16 #endif
17
18 #include <math.h>
19
20 #include <stdlib.h>
21
22 #include "wx/canvas/liner.h"
23
24 wxLine::wxLine( double x1, double y1, double x2, double y2 )
25 {
26 m_AA = 0.0;
27 m_BB = 0.0;
28 m_CC = 0.0;
29
30 m_a=wxPoint2DDouble(x1,y1);
31 m_b=wxPoint2DDouble(x2,y2);
32 if (m_a==m_b)
33 assert(0);
34
35 m_valid_parameters = FALSE;
36 }
37
38 wxLine::~wxLine()
39 {
40 }
41
42 wxLine::wxLine(const wxPoint2DDouble& a,const wxPoint2DDouble& b)
43 {
44 if (a==b)
45 assert(0);
46
47 m_a=a;
48 m_b=b;
49 m_valid_parameters = FALSE;
50 }
51
52
53
54 // ActionOnTable1
55 // This function decide which action must be taken, after PointInLine
56 // has given the results of two points in relation to a wxLine. See table 1 in the report
57 //
58 // input Result_beginPoint:
59 // Result_endPoint :
60 // The results can be R_R_LEFT_SIDE, R_R_RIGHT_SIDE, R_R_ON_AREA, R_R_IN_AREA
61 //
62 // return -1: Illegal combination
63 // 0: No action, no crosspoints
64 // 1: Investigate results points in relation to the other wxLine
65 // 2: endPoint is a crosspoint, no further investigation
66 // 3: beginPoint is a crosspoint, no further investigation
67 // 4: beginPoint and endPoint are crosspoints, no further investigation
68 // 5: beginPoint is a crosspoint, need further investigation
69 // 6: endPoint is a crosspoint, need further investigation
70 int wxLine::ActionOnTable1(R_PointStatus Result_beginPoint, R_PointStatus Result_endPoint)
71 {
72 // beginPoint and endPoint are crosspoints
73 if (
74 (Result_beginPoint == R_IN_AREA)
75 &&
76 (Result_endPoint == R_IN_AREA)
77 )
78 return 4;
79 // there are no crosspoints, no action
80 if (
81 (
82 (Result_beginPoint == R_LEFT_SIDE)
83 &&
84 (Result_endPoint == R_LEFT_SIDE)
85 )
86 ||
87 (
88 (Result_beginPoint == R_RIGHT_SIDE)
89 &&
90 (Result_endPoint == R_RIGHT_SIDE)
91 )
92 )
93 return 0;
94 // maybe there is a crosspoint, further investigation needed
95 if (
96 (
97 (Result_beginPoint == R_LEFT_SIDE)
98 &&
99 (
100 (Result_endPoint == R_RIGHT_SIDE)
101 ||
102 (Result_endPoint == R_ON_AREA)
103 )
104 )
105 ||
106 (
107 (Result_beginPoint == R_RIGHT_SIDE)
108 &&
109 (
110 (Result_endPoint == R_LEFT_SIDE)
111 ||
112 (Result_endPoint == R_ON_AREA)
113 )
114 )
115 ||
116 (
117 (Result_beginPoint == R_ON_AREA)
118 &&
119 (
120 (Result_endPoint == R_LEFT_SIDE)
121 ||
122 (Result_endPoint == R_RIGHT_SIDE)
123 ||
124 (Result_endPoint == R_ON_AREA)
125 )
126 )
127 )
128 return 1;
129 //there is a crosspoint
130 if (
131 (
132 (Result_beginPoint == R_LEFT_SIDE)
133 ||
134 (Result_beginPoint == R_RIGHT_SIDE)
135 )
136 &&
137 (Result_endPoint == R_IN_AREA)
138 )
139 return 2;
140 // there is a crosspoint
141 if (
142 (Result_beginPoint == R_IN_AREA)
143 &&
144 (
145 (Result_endPoint == R_LEFT_SIDE)
146 ||
147 (Result_endPoint == R_RIGHT_SIDE)
148 )
149 )
150 return 3;
151 // beginPoint is a crosspoint, further investigation needed
152 if (
153 (Result_beginPoint == R_IN_AREA)
154 &&
155 (Result_endPoint == R_ON_AREA)
156 )
157 return 5;
158 // endPoint is a crosspoint, further investigation needed
159 if (
160 (Result_beginPoint == R_ON_AREA)
161 &&
162 (Result_endPoint == R_IN_AREA)
163 )
164 return 6;
165 // All other combinations are illegal
166 return -1;
167 }
168
169
170 // ActionOnTable2
171 // This function decide which action must be taken, after PointInLine
172 // has given the results of two points in relation to a wxLine. It can only give a
173 // correct decision if first the relation of the points from the wxLine
174 // are investigated in relation to the wxLine wich can be constucted from the points.
175 //
176 // input Result_beginPoint:
177 // Result_endPoint :
178 // The results can be R_LEFT_SIDE, R_RIGHT_SIDE, R_ON_AREA, R_IN_AREA
179 //
180 // return -1: Illegal combination
181 // 0: No action, no crosspoints
182 // 1: Calculate crosspoint
183 // 2: endPoint is a crosspoint
184 // 3: beginPoint is a crosspoint
185 // 4: beginPoint and endPoint are crosspoints
186 int wxLine::ActionOnTable2(R_PointStatus Result_beginPoint, R_PointStatus Result_endPoint)
187 {
188 // beginPoint and eindpoint are crosspoints
189 if (
190 (Result_beginPoint == R_IN_AREA)
191 &&
192 (Result_endPoint == R_IN_AREA)
193 )
194 return 4;
195 // there are no crosspoints
196 if (
197 (
198 (Result_beginPoint == R_LEFT_SIDE)
199 &&
200 (
201 (Result_endPoint == R_LEFT_SIDE)
202 ||
203 (Result_endPoint == R_ON_AREA)
204 )
205 )
206 ||
207 (
208 (Result_beginPoint == R_RIGHT_SIDE)
209 &&
210 (
211 (Result_endPoint == R_RIGHT_SIDE)
212 ||
213 (Result_endPoint == R_ON_AREA)
214 )
215 )
216 ||
217 (
218 (Result_beginPoint == R_ON_AREA)
219 &&
220 (
221 (Result_endPoint == R_LEFT_SIDE)
222 ||
223 (Result_endPoint == R_RIGHT_SIDE)
224 ||
225 (Result_endPoint == R_ON_AREA)
226 )
227 )
228 )
229 return 0;
230 // there is a real intersection, which must be calculated
231 if (
232 (
233 (Result_beginPoint == R_LEFT_SIDE)
234 &&
235 (Result_endPoint == R_RIGHT_SIDE)
236 )
237 ||
238 (
239 (Result_beginPoint == R_RIGHT_SIDE)
240 &&
241 (Result_endPoint == R_LEFT_SIDE)
242 )
243 )
244 return 1;
245 // endPoint is a crosspoint
246 if (
247 (
248 (Result_beginPoint == R_LEFT_SIDE)
249 ||
250 (Result_beginPoint == R_RIGHT_SIDE)
251 ||
252 (Result_beginPoint == R_ON_AREA)
253 )
254 &&
255 (Result_endPoint == R_IN_AREA)
256 )
257 return 2;
258 // beginPoint is a crosspoint
259 if (
260 (Result_beginPoint == R_IN_AREA)
261 &&
262 (
263 (Result_endPoint == R_LEFT_SIDE)
264 ||
265 (Result_endPoint == R_RIGHT_SIDE)
266 ||
267 (Result_endPoint == R_ON_AREA)
268 )
269 )
270 return 3;
271 // All other combinations are illegal
272 return -1;
273 }
274
275 // Calculate the Y when the X is given
276 double wxLine::Calculate_Y(double X)
277 {
278 CalculateLineParameters();
279 if (m_AA != 0)
280 return -(m_AA * X + m_CC) / m_BB;
281 else
282 // horizontal wxLine
283 return m_a.m_y;
284 }
285
286 void wxLine::Virtual_Point(wxPoint2DDouble& a_point,double distance) const
287 {
288 assert(m_valid_parameters);
289
290 //calculate the distance using the slope of the wxLine
291 //and rotate 90 degrees
292
293 a_point.m_y=a_point.m_y + (distance * -m_BB);
294 a_point.m_x=a_point.m_x - (distance * m_AA );
295 }
296
297
298
299 //
300 // Calculate the lineparameters for the wxLine if nessecary
301 //
302 void wxLine::CalculateLineParameters()
303 {
304 // if not valid_parameters calculate the parameters
305 if (!m_valid_parameters)
306 {
307 double length;
308
309 // bp AND ep may not be the same
310 if (m_a == m_b)
311 assert (0);
312
313 m_AA = (m_b.m_y - m_a.m_y); // A = (Y2-Y1)
314 m_BB = (m_a.m_x - m_b.m_x); // B = (X1-X2)
315
316 // the parameters A end B can now be normalized
317 length = sqrt(m_AA*m_AA + m_BB*m_BB);
318
319 assert(length !=0);
320
321 m_AA = (m_AA / length);
322 m_BB = (m_BB / length);
323
324 m_CC = -((m_AA * m_a.m_x) + (m_a.m_y * m_BB));
325
326 m_valid_parameters = TRUE;
327 }
328 }
329
330
331 // Checks if a wxLine intersect with another wxLine
332 // inout wxLine : another wxLine
333 // Marge: optional, standard on MARGE (declared in MISC.CPP)
334 //
335 // return true : wxLines are crossing
336 // false: wxLines are not crossing
337 //
338 bool wxLine::CheckIntersect (wxLine& lijn, double Marge)
339 {
340 double distance=0;
341
342 // bp AND ep may not be the same
343 if (m_a == m_b)
344 assert (0);
345
346 int Take_Action1, Take_Action2;
347 bool Total_Result=FALSE;
348 R_PointStatus Result_beginPoint,Result_endPoint;
349
350 Result_beginPoint = PointInLine(lijn.m_a,distance,Marge);
351 Result_endPoint = PointInLine(lijn.m_b,distance,Marge);
352 Take_Action1 = ActionOnTable1(Result_beginPoint,Result_endPoint);
353 switch (Take_Action1)
354 {
355 case 0: Total_Result = FALSE ; break;
356 case 1: {
357 Result_beginPoint = lijn.PointInLine(m_a,distance,Marge);
358 Result_endPoint = lijn.PointInLine(m_b,distance,Marge);
359 Take_Action2 = ActionOnTable2(Result_beginPoint,Result_endPoint);
360 switch (Take_Action2)
361 {
362 case 0: Total_Result = FALSE; break;
363 case 1: case 2: case 3: case 4: Total_Result = TRUE; break;
364 }
365 }; break; // This break belongs to the switch(Take_Action1)
366 case 2: case 3: case 4: case 5: case 6: Total_Result = TRUE; break;
367 }
368 return Total_Result; //This is the final decision
369 }
370
371
372 //
373 // Get the beginPoint from the wxLine
374 // usage: Point aPoint = a_line.GetBeginPoint()
375 //
376 wxPoint2DDouble wxLine::GetBeginPoint()
377 {
378 return m_a;
379 }
380
381
382 //
383 // Get the endPoint from the wxLine
384 // usage: Point aPoint = a_line.GetEndPoint()
385 //
386 wxPoint2DDouble wxLine::GetEndPoint()
387 {
388 return m_b;
389 }
390
391 // Intersects two wxLines
392 // input wxLine : another wxLine
393 // Marge: optional, standard on MARGE
394 //
395 // return 0: If there are no crossings
396 // 1: If there is one crossing
397 // 2: If there are two crossings
398 int wxLine::Intersect(wxLine& lijn, wxPoint2DDouble& c1 ,wxPoint2DDouble& c2 , double Marge)
399 {
400 double distance=0;
401
402 // bp AND ep may not be the same
403 if (m_a == m_b)
404 assert (0);
405
406 R_PointStatus Result_beginPoint,Result_endPoint;
407 int Take_Action1, Take_Action2, Number_of_Crossings = 0;
408
409 Result_beginPoint = PointInLine(lijn.m_a,distance,Marge);
410 Result_endPoint = PointInLine(lijn.m_b,distance,Marge);
411
412 Take_Action1 = ActionOnTable1(Result_beginPoint,Result_endPoint);
413 // 0: No action, no crosspoints
414 // 1: Investigate results points in relation to the other wxLine
415 // 2: endPoint is a crosspoint, no further investigation
416 // 3: beginPoint is a crosspoint, no further investigation
417 // 4: beginPoint and endPoint are crosspoints, no further investigation
418 // 5: beginPoint is a crosspoint, need further investigation
419 // 6: endPoint is a crosspoint, need further investigation
420
421 // The first switch will insert a crosspoint immediatly
422 switch (Take_Action1)
423 {
424 case 2: case 6: c1=lijn.m_b;
425 Number_of_Crossings = 1;
426 break;
427 case 3: case 5: c1=lijn.m_a;
428 Number_of_Crossings = 1;
429 break;
430 case 4: c1=lijn.m_a;
431 c2=lijn.m_b;
432 Number_of_Crossings = 2;
433 break;
434 default:
435 break;
436 }
437
438 // This switch wil investigate the points of this wxLine in relation to lijn
439 // 1: Investigate results points in relation to the other wxLine
440 // 5: beginPoint is a crosspoint, need further investigation
441 // 6: endPoint is a crosspoint, need further investigation
442 switch (Take_Action1)
443 {
444 case 1: case 5: case 6:
445 {
446 Result_beginPoint = lijn.PointInLine(m_a,distance,Marge);
447 Result_endPoint = lijn.PointInLine(m_b,distance,Marge);
448 Take_Action2 = ActionOnTable2(Result_beginPoint,Result_endPoint);
449 // return -1: Illegal combination
450 // 0: No action, no crosspoints
451 // 1: Calculate crosspoint
452 // 2: endPoint is a crosspoint
453 // 3: beginPoint is a crosspoint
454 // 4: beginPoint and endPoint are crosspoints
455 switch (Take_Action2)
456 {
457 // for the cases see the returnvalue of ActionTable2
458 case 1: { // begin of scope to calculate the intersection
459 double X, Y, Denominator;
460 CalculateLineParameters();
461 Denominator = (m_AA * lijn.m_BB) - (lijn.m_AA * m_BB);
462 // Denominator may not be 0
463 assert(Denominator != 0.0);
464 // Calculate intersection of both linesegments
465 X = ((m_BB * lijn.m_CC) - (lijn.m_BB * m_CC)) / Denominator;
466 Y = ((lijn.m_AA * m_CC) - (m_AA * lijn.m_CC)) / Denominator;
467
468 c1.m_x=X;
469 c1.m_y=Y;
470 }
471 Number_of_Crossings++;
472 break;
473 case 2: c2=m_a;
474 Number_of_Crossings++;
475 break;
476 case 3: c2=m_b;
477 Number_of_Crossings++;
478 break;
479 case 4: c1=m_a;
480 c2=m_b;
481 Number_of_Crossings = 2;
482 break;
483 }
484 };
485 break;
486 default:
487 break;
488 }
489 return Number_of_Crossings; //This is de final number of crossings
490 }
491
492 //
493 // test if a point lies in the linesegment. If the point isn't on the wxLine
494 // the function returns a value that indicates on which side of the
495 // wxLine the point is (in linedirection from first point to second point
496 //
497 // returns R_LEFT_SIDE, when point lies on the left side of the wxLine
498 // R_RIGHT_SIDE, when point lies on the right side of the wxLine
499 // R_ON_AREA, when point lies on the infinite wxLine within a range
500 // R_IN_AREA, when point lies in the area of the linesegment
501 // the returnvalues are declared in (wxLine.H)
502 R_PointStatus wxLine::PointInLine(const wxPoint2DDouble& a_Point, double& Distance,double Marge)
503 {
504 Distance=0;
505
506 // Point may not be the same
507 assert(m_a != m_b);
508
509 int Result_ofm_BBox=FALSE;
510 R_PointStatus Result_of_Online;
511
512 //quick test if point is begin or endpoint
513 if (a_Point == m_a || a_Point == m_b)
514 return R_IN_AREA;
515
516 // Checking if point is in bounding-box with marge
517 double xmin=wxMin(m_a.m_x,m_b.m_x);
518 double xmax=wxMax(m_a.m_x,m_b.m_x);
519 double ymin=wxMin(m_a.m_y,m_b.m_y);
520 double ymax=wxMax(m_a.m_y,m_b.m_y);
521
522 if ( a_Point.m_x >= (xmin - Marge) && a_Point.m_x <= (xmax + Marge) &&
523 a_Point.m_y >= (ymin - Marge) && a_Point.m_y <= (ymax + Marge) )
524 Result_ofm_BBox=TRUE;
525
526 // Checking if point is on the infinite wxLine
527 Result_of_Online = PointOnLine(a_Point, Distance, Marge);
528
529 // point in boundingbox of the wxLine and is on the wxLine then the point is R_IN_AREA
530 if ((Result_ofm_BBox) && (Result_of_Online == R_ON_AREA))
531 return R_IN_AREA;
532 else
533 return Result_of_Online;
534 }
535
536
537 //
538 // test if a point lies on the wxLine. If the point isn't on the wxLine
539 // the function returns a value that indicates on which side of the
540 // wxLine the point is (in linedirection from first point to second point
541 //
542 // returns R_LEFT_SIDE, when point lies on the left side of the wxLine
543 // R_ON_AREA, when point lies on the infinite wxLine within a range
544 // R_RIGHT_SIDE, when point lies on the right side of the wxLine
545 // R_LEFT_SIDE , R_RIGHT_SIDE , R_ON_AREA
546 R_PointStatus wxLine::PointOnLine(const wxPoint2DDouble& a_Point, double& Distance, double Marge)
547 {
548 Distance=0;
549 // Point may not be queal
550 assert(m_a!=m_b);
551
552 //quick test if point is begin or endpoint
553 if (a_Point == m_a || a_Point == m_b)
554 return R_ON_AREA;
555
556 CalculateLineParameters();
557 // calculate the distance of a_Point in relation to the wxLine
558 Distance = (m_AA * a_Point.m_x)+(m_BB * a_Point.m_y) + m_CC;
559
560 if (Distance < -Marge)
561 return R_LEFT_SIDE;
562 else
563 {
564 if (Distance > Marge)
565 return R_RIGHT_SIDE;
566 else
567 return R_ON_AREA;
568 }
569 }
570
571 // makes a wxLine same as these
572 // usage : wxLine1 = wxLine2;
573 wxLine& wxLine::operator=(const wxLine& a_line)
574 {
575 m_AA = a_line.m_AA;
576 m_BB = a_line.m_BB;
577 m_CC = a_line.m_CC;
578
579 m_a= a_line.m_a;
580 m_b= a_line.m_b;
581 m_valid_parameters = a_line.m_valid_parameters;
582 return *this;
583 }
584
585 void wxLine::OffsetContour(const wxLine& nextline,double factor,wxPoint2DDouble& offsetpoint) const
586 {
587 wxPoint2DDouble offs_begin(m_a);
588 wxPoint2DDouble offs_end(m_b);
589
590 wxPoint2DDouble offs_bgn_next(nextline.m_a);
591 wxPoint2DDouble offs_end_next(nextline.m_b);
592 // make a wxPoint2DDouble from this point
593
594 Virtual_Point(offs_begin,factor);
595 Virtual_Point(offs_end,factor);
596 wxLine offs_currentline(offs_begin,offs_end);
597
598 nextline.Virtual_Point(offs_bgn_next,factor);
599 nextline.Virtual_Point(offs_end_next,factor);
600 wxLine offs_nextline(offs_bgn_next, offs_end_next);
601
602 offs_nextline.CalculateLineParameters();
603 offs_currentline.CalculateLineParameters();
604 offs_currentline.Intersect(offs_nextline,offsetpoint);
605 }
606
607 // Return the position of the second wxLine compared to this wxLine
608 // Result = IS_ON | IS_LEFT | IS_RIGHT
609 // Here Left and Right is defined as being left or right from
610 // the this wxLine towards the center (common) node
611 // direction of vetors taken as begin to endpoint with end of this at
612 // begin of wxLine two
613 OUTPRODUCT wxLine::OutProduct(const wxLine& two,double accur)
614 {
615 R_PointStatus uitp;
616 double distance;
617 if (two.m_a==two.m_b)
618 assert(0);
619 if (m_a==m_b)
620 assert(0);
621
622 uitp=PointOnLine(two.m_b, distance, accur);
623
624
625 /*double uitp= (_x - first._x) * (third._y - _y) -
626 (_y - first._y) * (third._x - _x);
627 if (uitp>0) return IS_LEFT;
628 if (uitp<0) return IS_RIGHT;
629 return IS_ON;*/
630
631 //depending on direction of this link (going to or coming from centre)
632 if (uitp==R_LEFT_SIDE)
633 return R_IS_LEFT;
634 if (uitp==R_RIGHT_SIDE)
635 return R_IS_RIGHT;
636 return R_IS_ON;
637 }
638
639 // Intersects two lines if a crossing return TRUE
640 // else FALSE
641 bool wxLine::Intersect(wxLine& lijn,wxPoint2DDouble& crossing)
642 {
643 // lijn must exist
644 assert(m_valid_parameters);
645 assert(lijn.m_valid_parameters);
646
647 double X, Y, Denominator;
648 Denominator = (m_AA * lijn.m_BB) - (lijn.m_AA * m_BB);
649 // Denominator may not be 0
650 if (Denominator == 0.0)
651 return FALSE;
652 // Calculate intersection of both linesegments
653 X = ((m_BB * lijn.m_CC) - (lijn.m_BB * m_CC)) / Denominator;
654 Y = ((lijn.m_AA * m_CC) - (m_AA * lijn.m_CC)) / Denominator;
655
656 crossing.m_x=X;
657 crossing.m_y=Y;
658 return TRUE;
659 }
660