1 /*
2 Copyright (C) 2017-2021, Dirk Krause
3 SPDX-License-Identifier: BSD-3-Clause
4 */
5
6 /*
7 WARNING: This file was generated by the dkct program (see
8 http://dktools.sourceforge.net/ for details).
9 Changes you make here will be lost if dkct is run again!
10 You should modify the original source and run dkct on it.
11 Original source: dk4bb.ctr
12 */
13
14 /** @file dk4bb.c The dk4bb module.
15 */
16
17
18 #include "dk4conf.h"
19 #include <libdk4gra/dk4bb.h>
20 #if DK4_HAVE_STDLIB_H
21 #ifndef STDLIB_H_INCLUDED
22 #include <stdlib.h>
23 #define STDLIB_H_INCLUDED 1
24 #endif
25 #endif
26
27 #if DK4_HAVE_MATH_H
28 #ifndef MATH_H_INCLUDED
29 #if DK4_ON_WINDOWS
30 #ifndef _USE_MATH_DEFINES
31 #define _USE_MATH_DEFINES 1
32 #endif
33 #endif
34 #include <math.h>
35 #define MATH_H_INCLUDED 1
36 #endif
37 #endif
38
39 #ifndef DK4MEM_H_INCLUDED
40 #include <libdk4base/dk4mem.h>
41 #endif
42
43 #ifndef DK4MATH_H_INCLUDED
44 #include <libdk4c/dk4math.h>
45 #endif
46
47 #if DK4_HAVE_ASSERT_H
48 #ifndef ASSERT_H_INCLUDED
49 #include <assert.h>
50 #define ASSERT_H_INCLUDED 1
51 #endif
52 #endif
53
54
55
56
57
58 /** Flag value to indicate information not present.
59 */
60 static const unsigned char have_not = ((unsigned char)0U);
61
62 /** Flag value to indicate X information presence.
63 */
64 static const unsigned char have_x = ((unsigned char)1U);
65
66 /** Flag value to indicate Y information presence.
67 */
68 static const unsigned char have_y = ((unsigned char)2U);
69
70 /** Flag value to check for information about both directions.
71 */
72 static const unsigned char have_both = ((unsigned char)3U);
73
74
75 /** Internally add an x value to bounding box.
76 @param bbptr Bounding box to modify.
77 @param x X value to add.
78 */
79
80 static
81 void
dk4bb_i_add_x(dk4_bb_t * bbptr,double x)82 dk4bb_i_add_x(
83 dk4_bb_t *bbptr,
84 double x
85 )
86 {
87
88 #if DK4_USE_ASSERT
89 assert(NULL != bbptr);
90 #endif
91 if (have_not != (have_x & (bbptr->fl))) {
92
93 if (x < bbptr->xmin) {
94 bbptr->xmin = x;
95 }
96 if (x > bbptr->xmax) {
97 bbptr->xmax = x;
98 }
99 }
100 else {
101 bbptr->xmin = bbptr->xmax = x;
102 bbptr->fl |= have_x;
103 }
104
105 }
106
107
108
109 /** Internally add an y value to bounding box.
110 @param bbptr Bounding box to modify.
111 @param y Y value to add.
112 */
113
114 static
115 void
dk4bb_i_add_y(dk4_bb_t * bbptr,double y)116 dk4bb_i_add_y(
117 dk4_bb_t *bbptr,
118 double y
119 )
120 {
121
122 #if DK4_USE_ASSERT
123 assert(NULL != bbptr);
124 #endif
125 if (have_not != (have_y & (bbptr->fl))) {
126
127 if (y < bbptr->ymin) {
128 bbptr->ymin = y;
129 }
130 if (y > bbptr->ymax) {
131 bbptr->ymax = y;
132 }
133 }
134 else {
135 bbptr->ymin = bbptr->ymax = y;
136 bbptr->fl |= have_y;
137 }
138
139 }
140
141
142
143 /*
144 The formula to calculate x for a given t in range 0 to 1 is
145 x(t) = (1-t)^3*x0 + 3*(1-t)^2*t*x0c + 3*(1-t)*t^2*x1c + t^3*x1
146 with
147 x0 Left point coordinate
148 x0c Left control point coordinate
149 x1c Right control point coordinate
150 x1 Right point coordinate.
151 The ^ operator is used as power here (t^3 is t*t*t).
152
153 The formula for y is similar.
154 */
155
156 /** Calculate coordinate value for a t value, save to minimum and/or
157 maximum if necessary.
158 @param pmin Address of bounding box minimum component.
159 @param pmax Address of bounding box maximum component.
160 @param pflags Address of bounding box flags component.
161 @param flval Flag bit for test (1=x, 2=y).
162 @param x0 Left point value.
163 @param x0c Left control point value.
164 @param x1c Right control point value.
165 @param x1 Right point value.
166 @param t Variable t value.
167 */
168
169 static
170 void
dk4bb_i_apply_t_bezier(double * pmin,double * pmax,unsigned char * pflags,unsigned char flval,double x0,double x0c,double x1c,double x1,double t)171 dk4bb_i_apply_t_bezier(
172 double *pmin,
173 double *pmax,
174 unsigned char *pflags,
175 unsigned char flval,
176 double x0,
177 double x0c,
178 double x1c,
179 double x1,
180 double t
181 )
182 {
183 double omt; /* 1 - t */
184 double x; /* x value */
185
186 #if DK4_USE_ASSERT
187 assert(NULL != pmin);
188 assert(NULL != pmax);
189 assert(NULL != pflags);
190 #endif
191 #if TRACE_DEBUG
192 if (isfinite(t)) {
193 }
194 else {
195 }
196 #endif
197 if ( isgreaterequal(t, 0.0) ) {
198 if ( islessequal(t, 1.0) ) {
199 omt = 1.0 - t;
200 x = omt * omt * omt * x0
201 + 3.0 * omt * omt * t * x0c
202 + 3.0 * omt * t * t * x1c
203 + t * t * t * x1;
204 if (0 != ((*pflags) & flval)) {
205 if (isless(x, *pmin)) {
206 *pmin = x;
207 }
208 if (isgreater(x, *pmax)) {
209 *pmax = x;
210 }
211 }
212 else {
213 *pmin = x;
214 *pmax = x;
215 *pflags |= flval;
216 }
217 }
218 #if TRACE_DEBUG
219 else {
220 }
221 #endif
222 }
223 #if TRACE_DEBUG
224 else {
225 }
226 #endif
227
228 }
229
230
231
232 /*
233 The formula used here was found using wxMaxima, input was
234
235 x: (1-t)^3*x0 + 3*(1-t)^2*t*x0c + 3*(1-t)*t^2*x1c + t^3*x1;
236 solve([diff(x, t)=0],[t]);
237
238 To find minima and maxima values we derive the Bezier curve
239 formula and search for zeroes of the derived function.
240 */
241
242 /** Check minimum and maximum coordinate value of a Bezier curve,
243 save values in bounding box if necessary.
244 @param pmin Address of bounding box minimum component.
245 @param pmax Address of bounding box maximum component.
246 @param pflags Address of bounding box flags component.
247 @param flval Flag bit for test (1=x, 2=y).
248 @param x0 Left point value.
249 @param x0c Left control point value.
250 @param x1c Right control point value.
251 @param x1 Right point value.
252 */
253
254 static
255 void
dk4bb_i_apply_bezier(double * pmin,double * pmax,unsigned char * pflags,unsigned char flval,double x0,double x0c,double x1c,double x1)256 dk4bb_i_apply_bezier(
257 double *pmin,
258 double *pmax,
259 unsigned char *pflags,
260 unsigned char flval,
261 double x0,
262 double x0c,
263 double x1c,
264 double x1
265 )
266 {
267 double a; /* Coefficient to third power of t */
268 double b; /* Coefficient to second power of t */
269 double c; /* Coefficient to t */
270 double denom; /* Denominator */
271 double sqop; /* Operand to square root */
272 double sqv; /* Square root result */
273 double t1; /* First extremum */
274 double t2; /* Second extremum */
275
276 #if DK4_USE_ASSERT
277 assert(NULL != pmin);
278 assert(NULL != pmax);
279 assert(NULL != pflags);
280 #endif
281 a = x1 - 3.0 * x1c + 3.0 * x0c - x0;
282 b = 3.0 * x0 - 6.0 * x0c + 3.0 * x1c;
283 c = 3.0 * (x0c - x0);
284 denom = 3.0 * a;
285 sqop = b * b - 3.0 * a * c;
286 sqv = sqrt(sqop);
287 t1 = (0.0 - b + sqv) / denom;
288 t2 = (0.0 - b - sqv) / denom;
289 #if DK4_HAVE_ISFINITE
290 if ((isfinite(t1)) && (isfinite(t2)))
291 #else
292 #if DK4_HAVE__FINITE
293 if ((_finite(t1)) && (_finite(t2)))
294 #else
295 #error "Neither isfinite() nor _finite() available!"
296 if(1)
297 #endif
298 #endif
299 {
300 dk4bb_i_apply_t_bezier(pmin, pmax, pflags, flval, x0, x0c, x1c, x1, t1);
301 dk4bb_i_apply_t_bezier(pmin, pmax, pflags, flval, x0, x0c, x1c, x1, t2);
302 }
303 else {
304 t1 = (0.0 - c) / (2.0 * b);
305 #if DK4_HAVE_ISFINITE
306 if (isfinite(t1))
307 #else
308 #if DK4_HAVE__FINITE
309 if (_finite(t1))
310 #else
311 #error "Neither isfinite() nor _finite() available!"
312 if(1)
313 #endif
314 #endif
315 {
316 dk4bb_i_apply_t_bezier(pmin,pmax,pflags,flval,x0,x0c,x1c,x1,t1);
317 }
318 #if TRACE_DEBUG
319 else {
320 }
321 #endif
322 }
323
324 }
325
326
327
328 /** Internal function to add Bezier spline segment to bounding box.
329 The bbptr pointer is already checked to be not NULL.
330 @param bbptr Bounding box to modify.
331 @param x0 Start point, x coordinate.
332 @param y0 Start point, y coordinate.
333 @param c0x Control point next to start point, x coordinate.
334 @param c0y Control point next to start point, y coordinate.
335 @param c1x Control point next to end point, x coordinate.
336 @param c1y Control point next to end point, y coordinate.
337 @param x1 End point, x coordinate.
338 @param y1 End point, y coordinate.
339 */
340
341 static
342 void
dk4bb_i_bezier(dk4_bb_t * bbptr,double x0,double y0,double c0x,double c0y,double c1x,double c1y,double x1,double y1)343 dk4bb_i_bezier(
344 dk4_bb_t *bbptr,
345 double x0,
346 double y0,
347 double c0x,
348 double c0y,
349 double c1x,
350 double c1y,
351 double x1,
352 double y1
353 )
354 {
355
356 #if DK4_USE_ASSERT
357 assert(NULL != bbptr);
358 #endif
359 dk4bb_i_add_x(bbptr, x0);
360 dk4bb_i_add_y(bbptr, y0);
361 dk4bb_i_add_x(bbptr, x1);
362 dk4bb_i_add_y(bbptr, y1);
363 dk4bb_i_apply_bezier(
364 &(bbptr->xmin), &(bbptr->xmax), &(bbptr->fl), have_x,
365 x0, c0x, c1x, x1
366 );
367 dk4bb_i_apply_bezier(
368 &(bbptr->ymin), &(bbptr->ymax), &(bbptr->fl), have_y,
369 y0, c0y, c1y, y1
370 );
371
372 }
373
374
375
376 static
377 double
dk4bb_sq(double x)378 dk4bb_sq(double x)
379 {
380 return (x * x);
381 }
382
383
384 static
385 void
dk4bb_i_add_rotated_ellipse(dk4_bb_t * bbptr,double xc,double yc,double rx,double ry,double rot)386 dk4bb_i_add_rotated_ellipse(
387 dk4_bb_t *bbptr,
388 double xc,
389 double yc,
390 double rx,
391 double ry,
392 double rot
393 )
394 {
395 double th;
396 double tw;
397 double xw;
398 double yw;
399 double xh;
400 double yh;
401 double h;
402 double w;
403 double beta;
404
405 #if DK4_USE_ASSERT
406 assert(NULL != bbptr);
407 #endif
408 th = atan2((-1.0 * ry), (rx * tan(M_PI - rot)));
409 tw = atan2((-1.0 * ry), (rx * tan(M_PI_2 - rot)));
410
411 xh = rx * cos(th);
412 yh = ry * sin(th);
413
414 xw = rx * cos(tw);
415 yw = ry * sin(tw);
416
417 beta = 0.0 - rot;
418 h = sqrt(
419 dk4bb_sq(yh - (yh*sin(beta)+xh*cos(beta))*sin(beta))
420 + dk4bb_sq(xh - (yh*sin(beta)+xh*cos(beta))*cos(beta))
421 );
422 beta += M_PI_2;
423 w = sqrt(
424 dk4bb_sq(yw - (yw*sin(beta)+xw*cos(beta))*sin(beta))
425 + dk4bb_sq(xw - (yw*sin(beta)+xw*cos(beta))*cos(beta))
426 );
427 dk4bb_i_add_x(bbptr, xc + w);
428 dk4bb_i_add_x(bbptr, xc - w);
429 dk4bb_i_add_y(bbptr, yc + h);
430 dk4bb_i_add_y(bbptr, yc - h);
431
432 }
433
434
435
436 void
dk4bb_init(dk4_bb_t * bbptr)437 dk4bb_init(
438 dk4_bb_t *bbptr
439 )
440 {
441
442 #if DK4_USE_ASSERT
443 assert(NULL != bbptr);
444 #endif
445 if (NULL != bbptr) {
446 DK4_MEMRES(bbptr, sizeof(dk4_bb_t));
447 bbptr->xmin = bbptr->xmax = bbptr->ymin = bbptr->ymax = 0.0;
448 bbptr->fl = have_not;
449 }
450 #if TRACE_DEBUG
451 else {
452 }
453 #endif
454
455 }
456
457
458
459 void
dk4bb_add_x(dk4_bb_t * bbptr,double x)460 dk4bb_add_x(
461 dk4_bb_t *bbptr,
462 double x
463 )
464 {
465
466 #if DK4_USE_ASSERT
467 assert(NULL != bbptr);
468 #endif
469 if (NULL != bbptr) {
470 dk4bb_i_add_x(bbptr, x);
471 }
472 #if TRACE_DEBUG
473 else {
474 }
475 #endif
476
477 }
478
479
480
481 void
dk4bb_add_y(dk4_bb_t * bbptr,double y)482 dk4bb_add_y(
483 dk4_bb_t *bbptr,
484 double y
485 )
486 {
487
488 #if DK4_USE_ASSERT
489 assert(NULL != bbptr);
490 #endif
491 if (NULL != bbptr) {
492 dk4bb_i_add_y(bbptr, y);
493 }
494 #if TRACE_DEBUG
495 else {
496 }
497 #endif
498
499 }
500
501
502
503 void
dk4bb_add_point(dk4_bb_t * bbptr,double x,double y)504 dk4bb_add_point(
505 dk4_bb_t *bbptr,
506 double x,
507 double y
508 )
509 {
510
511 #if DK4_USE_ASSERT
512 assert(NULL != bbptr);
513 #endif
514 if (NULL != bbptr) {
515 dk4bb_i_add_x(bbptr, x);
516 dk4bb_i_add_y(bbptr, y);
517 }
518 #if TRACE_DEBUG
519 else {
520 }
521 #endif
522
523 }
524
525
526
527 void
dk4bb_add_bezier(dk4_bb_t * bbptr,double x0,double y0,double c0x,double c0y,double c1x,double c1y,double x1,double y1)528 dk4bb_add_bezier(
529 dk4_bb_t *bbptr,
530 double x0,
531 double y0,
532 double c0x,
533 double c0y,
534 double c1x,
535 double c1y,
536 double x1,
537 double y1
538 )
539 {
540 #if DK4_USE_ASSERT
541 assert(NULL != bbptr);
542 #endif
543 if (NULL != bbptr) {
544 dk4bb_i_bezier(bbptr, x0, y0, c0x, c0y, c1x, c1y, x1, y1);
545 }
546 }
547
548
549 void
dk4bb_add_rotated_ellipse(dk4_bb_t * bbptr,double xc,double yc,double rx,double ry,double rot)550 dk4bb_add_rotated_ellipse(
551 dk4_bb_t *bbptr,
552 double xc,
553 double yc,
554 double rx,
555 double ry,
556 double rot
557 )
558 {
559 #if DK4_USE_ASSERT
560 assert(NULL != bbptr);
561 #endif
562 if (NULL != bbptr) {
563 dk4bb_i_add_rotated_ellipse(bbptr, xc, yc, rx, ry, rot);
564 }
565 }
566
567
568
569 void
dk4bb_add_bb(dk4_bb_t * pdst,dk4_bb_t const * psrc)570 dk4bb_add_bb(
571 dk4_bb_t *pdst,
572 dk4_bb_t const *psrc
573 )
574 {
575 if ((NULL != pdst) && (NULL != psrc)) {
576 if (have_not != (have_x & (psrc->fl))) {
577 dk4bb_i_add_x(pdst, psrc->xmin);
578 dk4bb_i_add_x(pdst, psrc->xmax);
579 }
580 if (have_not != (have_y & (psrc->fl))) {
581 dk4bb_i_add_y(pdst, psrc->ymin);
582 dk4bb_i_add_y(pdst, psrc->ymax);
583 }
584 }
585 }
586
587
588
589 int
dk4bb_have_x(const dk4_bb_t * bbptr)590 dk4bb_have_x(
591 const dk4_bb_t *bbptr
592 )
593 {
594 #if DK4_USE_ASSERT
595 assert(NULL != bbptr);
596 #endif
597 if (NULL != bbptr) {
598 return ((have_not != (have_x & (bbptr->fl))) ? (1) : (0));
599 }
600 return 0;
601 }
602
603
604
605 int
dk4bb_have_y(const dk4_bb_t * bbptr)606 dk4bb_have_y(
607 const dk4_bb_t *bbptr
608 )
609 {
610 #if DK4_USE_ASSERT
611 assert(NULL != bbptr);
612 #endif
613 if (NULL != bbptr) {
614 return ((have_not != (have_y & (bbptr->fl))) ? (1) : (0));
615 }
616 return 0;
617 }
618
619
620
621 double
dk4bb_get_xmin(const dk4_bb_t * bbptr)622 dk4bb_get_xmin(
623 const dk4_bb_t *bbptr
624 )
625 {
626 #if DK4_USE_ASSERT
627 assert(NULL != bbptr);
628 #endif
629 if (NULL != bbptr) {
630 return bbptr->xmin;
631 }
632 return 0.0;
633 }
634
635
636
637 double
dk4bb_get_xmax(const dk4_bb_t * bbptr)638 dk4bb_get_xmax(
639 const dk4_bb_t *bbptr
640 )
641 {
642 #if DK4_USE_ASSERT
643 assert(NULL != bbptr);
644 #endif
645 if (NULL != bbptr) {
646 return bbptr->xmax;
647 }
648 return 0.0;
649 }
650
651
652
653 double
dk4bb_get_ymin(const dk4_bb_t * bbptr)654 dk4bb_get_ymin(
655 const dk4_bb_t *bbptr
656 )
657 {
658 #if DK4_USE_ASSERT
659 assert(NULL != bbptr);
660 #endif
661 if (NULL != bbptr) {
662 return bbptr->ymin;
663 }
664 return 0.0;
665 }
666
667
668
669 double
dk4bb_get_ymax(const dk4_bb_t * bbptr)670 dk4bb_get_ymax(
671 const dk4_bb_t *bbptr
672 )
673 {
674 #if DK4_USE_ASSERT
675 assert(NULL != bbptr);
676 #endif
677 if (NULL != bbptr) {
678 return bbptr->ymax;
679 }
680 return 0.0;
681 }
682
683
684
685 #if TRACE_DEBUG
686 static
687 void
dk4bb_report_bb(const dk4_bb_t * p)688 dk4bb_report_bb(const dk4_bb_t *p)
689 {
690
691
692 }
693 #endif
694
695
696 int
dk4bb_contains_bb(const dk4_bb_t * pouter,const dk4_bb_t * pinner,int aborder)697 dk4bb_contains_bb(
698 const dk4_bb_t *pouter,
699 const dk4_bb_t *pinner,
700 int aborder
701 )
702 {
703 int back = 0;
704
705
706
707
708
709 if ((NULL != pouter) && (NULL != pinner)) {
710 if (
711 (have_both == (have_both & (pouter->fl)))
712 && (have_both == (have_both & (pinner->fl)))
713 ) {
714 if (0 != aborder) {
715 if (
716 (pinner->xmin >= pouter->xmin)
717 && (pinner->xmax <= pouter->xmax)
718 && (pinner->ymin >= pouter->ymin)
719 && (pinner->ymax <= pouter->ymax)
720 ) {
721 back = 1;
722 }
723 }
724 else {
725 if (
726 (pinner->xmin > pouter->xmin)
727 && (pinner->xmax < pouter->xmax)
728 && (pinner->ymin > pouter->ymin)
729 && (pinner->ymax < pouter->ymax)
730 ) {
731 back = 1;
732 }
733 }
734 }
735 else {
736 }
737 }
738 else {
739 }
740
741 return back;
742 }
743
744
745
746 /* vim: set ai sw=4 ts=4 : */
747
748