diff options
Diffstat (limited to 'support/dktools/dk4bb.ctr')
-rw-r--r-- | support/dktools/dk4bb.ctr | 971 |
1 files changed, 0 insertions, 971 deletions
diff --git a/support/dktools/dk4bb.ctr b/support/dktools/dk4bb.ctr deleted file mode 100644 index ce3815681c..0000000000 --- a/support/dktools/dk4bb.ctr +++ /dev/null @@ -1,971 +0,0 @@ -%% options - -copyright owner = Dirk Krause -copyright year = 2017-xxxx -SPDX-License-Identifier: BSD-3-Clause - - -%% header - -/** @file dk4bb.h Bounding box for drawing operations. -*/ - -#ifndef DK4CONF_H_INCLUDED -#if DK4_BUILDING_DKTOOLS4 -#include "dk4conf.h" -#else -#include <dktools-4/dk4conf.h> -#endif -#endif - -#ifndef DK4TYPES_H_INCLUDED -#if DK4_BUILDING_DKTOOLS4 -#include "dk4types.h" -#else -#include <dktools-4/dk4types.h> -#endif -#endif - - - -/** Bounding box. -*/ -typedef struct { - double xmin; /**< Minimum x value. */ - double xmax; /**< Maximum x value. */ - double ymin; /**< Minimum y value. */ - double ymax; /**< Maximum y value. */ - unsigned char fl; /**< Flags: Have x (bit 0), have y (bit 1). */ -} dk4_bb_t; - -#ifdef __cplusplus -extern "C" { -#endif - - -/** Initialize bounding box. - @param bbptr Bounding box to initialize. -*/ - -void -dk4bb_init( - dk4_bb_t *bbptr -); - - -/** Add x coordinate to bounding box. - @param bbptr Bounding box to modify. - @param x Coordinate value to add. -*/ - -void -dk4bb_add_x( - dk4_bb_t *bbptr, - double x -); - - -/** Add y coordinate to bounding box. - @param bbptr Bounding box to modify. - @param y Coordinate value to add. -*/ - -void -dk4bb_add_y( - dk4_bb_t *bbptr, - double y -); - - -/** Add point to bounding box. - @param bbptr Bounding box to modify. - @param x X coordinate of point. - @param y Y coordinate of point. -*/ - -void -dk4bb_add_point( - dk4_bb_t *bbptr, - double x, - double y -); - - -/** Add Bezier spline segment to bounding box. - @param bbptr Bounding box to modify. - @param x0 Start point, x coordinate. - @param y0 Start point, y coordinate. - @param c0x Control point next to start point, x coordinate. - @param c0y Control point next to start point, y coordinate. - @param c1x Control point next to end point, x coordinate. - @param c1y Control point next to end point, y coordinate. - @param x1 End point, x coordinate. - @param y1 End point, y coordinate. -*/ - -void -dk4bb_add_bezier( - dk4_bb_t *bbptr, - double x0, - double y0, - double c0x, - double c0y, - double c1x, - double c1y, - double x1, - double y1 -); - - -/** Add bounding box for a rotated ellipse. - @param bbptr Bounding box to modify. - @param xc Center point x coordinate. - @param yc Center point y coordinate. - @param rx X radius. - @param ry Y radius. - @param rot Rotation counterclockwise in radians. -*/ - -void -dk4bb_add_rotated_ellipse( - dk4_bb_t *bbptr, - double xc, - double yc, - double rx, - double ry, - double rot -); - - -/** Add one bounding box to another one. - @param pdest Destination bounding box. - @param psrc Source bounding box. -*/ - -void -dk4bb_add_bb( - dk4_bb_t *pdest, - dk4_bb_t const *psrc -); - - -/** Check whether an x value is saved in the bounding box. - @param bbptr Bounding box to query. - @return 1 if x value available, 0 otherwise. -*/ - -int -dk4bb_have_x( - const dk4_bb_t *bbptr -); - - -/** Check whether an y value is saved in the bounding box. - @param bbptr Bounding box to query. - @return 1 if y value available, 0 otherwise. -*/ - -int -dk4bb_have_y( - const dk4_bb_t *bbptr -); - - -/** Retrieve minimum x value. - @param bbptr Bounding box to query. - @return Minimum x value saved in the bounding box. -*/ - -double -dk4bb_get_xmin( - const dk4_bb_t *bbptr -); - - -/** Retrieve maximum x value. - @param bbptr Bounding box to query. - @return Maximum x value saved in the bounding box. -*/ - -double -dk4bb_get_xmax( - const dk4_bb_t *bbptr -); - - -/** Retrieve minimum y value. - @param bbptr Bounding box to query. - @return Minimum y value saved in the bounding box. -*/ - -double -dk4bb_get_ymin( - const dk4_bb_t *bbptr -); - - -/** Retrieve maximum y value. - @param bbptr Bounding box to query. - @return Maximum y value saved in the bounding box. -*/ - -double -dk4bb_get_ymax( - const dk4_bb_t *bbptr -); - - -/** Check whether an outer box contains an inner box candidate. - Both boxes must have both x and y information. - @param pouter Outer box. - @param pinner Inner box candidate. - @param aborder Flag: Allow overlapping borders. - @return 1 if pouter contains pinner, 0 otherwise. -*/ - -int -dk4bb_contains_bb( - const dk4_bb_t *pouter, - const dk4_bb_t *pinner, - int aborder -); - - -#ifdef __cplusplus -} -#endif - -/* vim: set ai sw=4 ts=4 : */ - -%% module - -#include "dk4conf.h" -#include "dk4bb.h" -#if DK4_HAVE_STDLIB_H -#ifndef STDLIB_H_INCLUDED -#include <stdlib.h> -#define STDLIB_H_INCLUDED 1 -#endif -#endif - -#if DK4_HAVE_MATH_H -#ifndef MATH_H_INCLUDED -#if DK4_ON_WINDOWS -#ifndef _USE_MATH_DEFINES -#define _USE_MATH_DEFINES 1 -#endif -#endif -#include <math.h> -#define MATH_H_INCLUDED 1 -#endif -#endif - -#ifndef DK4MEM_H_INCLUDED -#include "dk4mem.h" -#endif - -#ifndef DK4MATH_H_INCLUDED -#include "dk4math.h" -#endif - -#if DK4_HAVE_ASSERT_H -#ifndef ASSERT_H_INCLUDED -#include <assert.h> -#define ASSERT_H_INCLUDED 1 -#endif -#endif - - -$!trace-include - - -/** Flag value to indicate information not present. -*/ -static const unsigned char have_not = ((unsigned char)0U); - -/** Flag value to indicate X information presence. -*/ -static const unsigned char have_x = ((unsigned char)1U); - -/** Flag value to indicate Y information presence. -*/ -static const unsigned char have_y = ((unsigned char)2U); - -/** Flag value to check for information about both directions. -*/ -static const unsigned char have_both = ((unsigned char)3U); - - -/** Internally add an x value to bounding box. - @param bbptr Bounding box to modify. - @param x X value to add. -*/ - -static -void -dk4bb_i_add_x( - dk4_bb_t *bbptr, - double x -) -{ - $? "+ dk4bb_i_add_x %g", x -#if DK4_USE_ASSERT - assert(NULL != bbptr); -#endif - if (have_not != (have_x & (bbptr->fl))) { - $? ". compare against saved values" - if (x < bbptr->xmin) { - bbptr->xmin = x; $? ". save new xmin=%g", x - } - if (x > bbptr->xmax) { - bbptr->xmax = x; $? ". save new xmax=%g", x - } - } - else { $? ". save values" - bbptr->xmin = bbptr->xmax = x; - bbptr->fl |= have_x; - } - $? "- dk4bb_i_add_x" -} - - - -/** Internally add an y value to bounding box. - @param bbptr Bounding box to modify. - @param y Y value to add. -*/ - -static -void -dk4bb_i_add_y( - dk4_bb_t *bbptr, - double y -) -{ - $? "+ dk4bb_i_add_y %g", y -#if DK4_USE_ASSERT - assert(NULL != bbptr); -#endif - if (have_not != (have_y & (bbptr->fl))) { - $? ". compare against saved values" - if (y < bbptr->ymin) { $? ". save new ymin=%g", y - bbptr->ymin = y; - } - if (y > bbptr->ymax) { $? ". save new ymax=%g", y - bbptr->ymax = y; - } - } - else { $? ". save values" - bbptr->ymin = bbptr->ymax = y; - bbptr->fl |= have_y; - } - $? "- dk4bb_i_add_y" -} - - - -/* - The formula to calculate x for a given t in range 0 to 1 is - x(t) = (1-t)^3*x0 + 3*(1-t)^2*t*x0c + 3*(1-t)*t^2*x1c + t^3*x1 - with - x0 Left point coordinate - x0c Left control point coordinate - x1c Right control point coordinate - x1 Right point coordinate. - The ^ operator is used as power here (t^3 is t*t*t). - - The formula for y is similar. -*/ - -/** Calculate coordinate value for a t value, save to minimum and/or - maximum if necessary. - @param pmin Address of bounding box minimum component. - @param pmax Address of bounding box maximum component. - @param pflags Address of bounding box flags component. - @param flval Flag bit for test (1=x, 2=y). - @param x0 Left point value. - @param x0c Left control point value. - @param x1c Right control point value. - @param x1 Right point value. - @param t Variable t value. -*/ - -static -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 -) -{ - double omt; /* 1 - t */ - double x; /* x value */ - $? "+ dk4bb_i_apply_t_bezier %g %g %g %g t=%g", x0, x0c, x1c, x1, t -#if DK4_USE_ASSERT - assert(NULL != pmin); - assert(NULL != pmax); - assert(NULL != pflags); -#endif -#if TRACE_DEBUG - if (isfinite(t)) { $? ". t is finite" - } - else { $? "! t is not finite" - } -#endif - if ( isgreaterequal(t, 0.0) ) { - if ( islessequal(t, 1.0) ) { $? ". valid t" - omt = 1.0 - t; - x = omt * omt * omt * x0 - + 3.0 * omt * omt * t * x0c - + 3.0 * omt * t * t * x1c - + t * t * t * x1; $? ". x=%g", x - if (0 != ((*pflags) & flval)) { $? ". check with existing extrema" - if (isless(x, *pmin)) { $? ". new minimum (former %g)",*pmin - *pmin = x; - } - if (isgreater(x, *pmax)) { $? ". new maximum (forger %g)",*pmax - *pmax = x; - } - } - else { $? ". no existing extrema" - *pmin = x; - *pmax = x; - *pflags |= flval; - } - } -#if TRACE_DEBUG - else { $? ". t=%g out of range", t - } -#endif - } -#if TRACE_DEBUG - else { $? ". t=%g out of range", t - } -#endif - $? "- dk4bb_i_apply_t_bezier" -} - - - -/* - The formula used here was found using wxMaxima, input was - - x: (1-t)^3*x0 + 3*(1-t)^2*t*x0c + 3*(1-t)*t^2*x1c + t^3*x1; - solve([diff(x, t)=0],[t]); - - To find minima and maxima values we derive the Bezier curve - formula and search for zeroes of the derived function. -*/ - -/** Check minimum and maximum coordinate value of a Bezier curve, - save values in bounding box if necessary. - @param pmin Address of bounding box minimum component. - @param pmax Address of bounding box maximum component. - @param pflags Address of bounding box flags component. - @param flval Flag bit for test (1=x, 2=y). - @param x0 Left point value. - @param x0c Left control point value. - @param x1c Right control point value. - @param x1 Right point value. -*/ - -static -void -dk4bb_i_apply_bezier( - double *pmin, - double *pmax, - unsigned char *pflags, - unsigned char flval, - double x0, - double x0c, - double x1c, - double x1 -) -{ - double a; /* Coefficient to third power of t */ - double b; /* Coefficient to second power of t */ - double c; /* Coefficient to t */ - double denom; /* Denominator */ - double sqop; /* Operand to square root */ - double sqv; /* Square root result */ - double t1; /* First extremum */ - double t2; /* Second extremum */ - -#if DK4_USE_ASSERT - assert(NULL != pmin); - assert(NULL != pmax); - assert(NULL != pflags); -#endif - a = x1 - 3.0 * x1c + 3.0 * x0c - x0; - b = 3.0 * x0 - 6.0 * x0c + 3.0 * x1c; - c = 3.0 * (x0c - x0); - denom = 3.0 * a; - sqop = b * b - 3.0 * a * c; - sqv = sqrt(sqop); - t1 = (0.0 - b + sqv) / denom; - t2 = (0.0 - b - sqv) / denom; -#if DK4_HAVE_ISFINITE - if ((isfinite(t1)) && (isfinite(t2))) -#else -#if DK4_HAVE__FINITE - if ((_finite(t1)) && (_finite(t2))) -#else -#error "Neither isfinite() nor _finite() available!" - if(1) -#endif -#endif - { $? ". 3rd degree polynomial" - dk4bb_i_apply_t_bezier(pmin, pmax, pflags, flval, x0, x0c, x1c, x1, t1); - dk4bb_i_apply_t_bezier(pmin, pmax, pflags, flval, x0, x0c, x1c, x1, t2); - } - else { $? ". not a 3rd degree polynomial" - t1 = (0.0 - c) / (2.0 * b); -#if DK4_HAVE_ISFINITE - if (isfinite(t1)) -#else -#if DK4_HAVE__FINITE - if (_finite(t1)) -#else -#error "Neither isfinite() nor _finite() available!" - if(1) -#endif -#endif - { $? ". 2nd degree polynomial" - dk4bb_i_apply_t_bezier(pmin,pmax,pflags,flval,x0,x0c,x1c,x1,t1); - } -#if TRACE_DEBUG - else { $? "! not a polynomial" - } -#endif - } - $? "- dk4bb_i_apply_bezier" -} - - - -/** Internal function to add Bezier spline segment to bounding box. - The bbptr pointer is already checked to be not NULL. - @param bbptr Bounding box to modify. - @param x0 Start point, x coordinate. - @param y0 Start point, y coordinate. - @param c0x Control point next to start point, x coordinate. - @param c0y Control point next to start point, y coordinate. - @param c1x Control point next to end point, x coordinate. - @param c1y Control point next to end point, y coordinate. - @param x1 End point, x coordinate. - @param y1 End point, y coordinate. -*/ - -static -void -dk4bb_i_bezier( - dk4_bb_t *bbptr, - double x0, - double y0, - double c0x, - double c0y, - double c1x, - double c1y, - double x1, - double y1 -) -{ - $? "+ dk4bb_i_bezier %g %g %g %g %g %g %g %g", x0, y0, c0x, c0y, c1x, c1y, x1, y1 -#if DK4_USE_ASSERT - assert(NULL != bbptr); -#endif - dk4bb_i_add_x(bbptr, x0); - dk4bb_i_add_y(bbptr, y0); - dk4bb_i_add_x(bbptr, x1); - dk4bb_i_add_y(bbptr, y1); - dk4bb_i_apply_bezier( - &(bbptr->xmin), &(bbptr->xmax), &(bbptr->fl), have_x, - x0, c0x, c1x, x1 - ); - dk4bb_i_apply_bezier( - &(bbptr->ymin), &(bbptr->ymax), &(bbptr->fl), have_y, - y0, c0y, c1y, y1 - ); - $? "- dk4bb_i_bezier" -} - - - -static -double -dk4bb_sq(double x) -{ - return (x * x); -} - - -static -void -dk4bb_i_add_rotated_ellipse( - dk4_bb_t *bbptr, - double xc, - double yc, - double rx, - double ry, - double rot -) -{ - double th; - double tw; - double xw; - double yw; - double xh; - double yh; - double h; - double w; - double beta; - $? "+ dk4bb_i_add_rotated_ellipse %g %g %g %g %g", xc, yc, rx, ry, rot -#if DK4_USE_ASSERT - assert(NULL != bbptr); -#endif - th = atan2((-1.0 * ry), (rx * tan(M_PI - rot))); - tw = atan2((-1.0 * ry), (rx * tan(M_PI_2 - rot))); - $? ". th=%g tw=%g", th, tw - xh = rx * cos(th); - yh = ry * sin(th); - $? ". xh=%g yh=%g", xh, yh - xw = rx * cos(tw); - yw = ry * sin(tw); - $? ". xw=%g yw=%g", xw, yw - beta = 0.0 - rot; - h = sqrt( - dk4bb_sq(yh - (yh*sin(beta)+xh*cos(beta))*sin(beta)) - + dk4bb_sq(xh - (yh*sin(beta)+xh*cos(beta))*cos(beta)) - ); $? ". h=%g", h - beta += M_PI_2; - w = sqrt( - dk4bb_sq(yw - (yw*sin(beta)+xw*cos(beta))*sin(beta)) - + dk4bb_sq(xw - (yw*sin(beta)+xw*cos(beta))*cos(beta)) - ); $? ". w=%g", w - dk4bb_i_add_x(bbptr, xc + w); - dk4bb_i_add_x(bbptr, xc - w); - dk4bb_i_add_y(bbptr, yc + h); - dk4bb_i_add_y(bbptr, yc - h); - $? "- dk4bb_i_add_rotated_ellipse" -} - - - -void -dk4bb_init( - dk4_bb_t *bbptr -) -{ - $? "+ dk4bb_init" -#if DK4_USE_ASSERT - assert(NULL != bbptr); -#endif - if (NULL != bbptr) { - DK4_MEMRES(bbptr, sizeof(dk4_bb_t)); - bbptr->xmin = bbptr->xmax = bbptr->ymin = bbptr->ymax = 0.0; - bbptr->fl = have_not; - } -#if TRACE_DEBUG - else { $? "! invalid pointer" - } -#endif - $? "- dk4bb_init" -} - - - -void -dk4bb_add_x( - dk4_bb_t *bbptr, - double x -) -{ - $? "+ dk4bb_add_x" -#if DK4_USE_ASSERT - assert(NULL != bbptr); -#endif - if (NULL != bbptr) { - dk4bb_i_add_x(bbptr, x); - } -#if TRACE_DEBUG - else { $? "! invalid pointer" - } -#endif - $? "- dk4bb_add_x" -} - - - -void -dk4bb_add_y( - dk4_bb_t *bbptr, - double y -) -{ - $? "+ dk4bb_add_y" -#if DK4_USE_ASSERT - assert(NULL != bbptr); -#endif - if (NULL != bbptr) { - dk4bb_i_add_y(bbptr, y); - } -#if TRACE_DEBUG - else { $? "! invalid pointer" - } -#endif - $? "- dk4bb_add_y" -} - - - -void -dk4bb_add_point( - dk4_bb_t *bbptr, - double x, - double y -) -{ - $? "+ dk4bb_add_point" -#if DK4_USE_ASSERT - assert(NULL != bbptr); -#endif - if (NULL != bbptr) { - dk4bb_i_add_x(bbptr, x); - dk4bb_i_add_y(bbptr, y); - } -#if TRACE_DEBUG - else { $? "! invalid pointer" - } -#endif - $? "- dk4bb_add_point" -} - - - -void -dk4bb_add_bezier( - dk4_bb_t *bbptr, - double x0, - double y0, - double c0x, - double c0y, - double c1x, - double c1y, - double x1, - double y1 -) -{ -#if DK4_USE_ASSERT - assert(NULL != bbptr); -#endif - if (NULL != bbptr) { - dk4bb_i_bezier(bbptr, x0, y0, c0x, c0y, c1x, c1y, x1, y1); - } -} - - -void -dk4bb_add_rotated_ellipse( - dk4_bb_t *bbptr, - double xc, - double yc, - double rx, - double ry, - double rot -) -{ -#if DK4_USE_ASSERT - assert(NULL != bbptr); -#endif - if (NULL != bbptr) { - dk4bb_i_add_rotated_ellipse(bbptr, xc, yc, rx, ry, rot); - } -} - - - -void -dk4bb_add_bb( - dk4_bb_t *pdst, - dk4_bb_t const *psrc -) -{ - if ((NULL != pdst) && (NULL != psrc)) { - if (have_not != (have_x & (psrc->fl))) { - dk4bb_i_add_x(pdst, psrc->xmin); - dk4bb_i_add_x(pdst, psrc->xmax); - } - if (have_not != (have_y & (psrc->fl))) { - dk4bb_i_add_y(pdst, psrc->ymin); - dk4bb_i_add_y(pdst, psrc->ymax); - } - } -} - - - -int -dk4bb_have_x( - const dk4_bb_t *bbptr -) -{ -#if DK4_USE_ASSERT - assert(NULL != bbptr); -#endif - if (NULL != bbptr) { - return ((have_not != (have_x & (bbptr->fl))) ? (1) : (0)); - } - return 0; -} - - - -int -dk4bb_have_y( - const dk4_bb_t *bbptr -) -{ -#if DK4_USE_ASSERT - assert(NULL != bbptr); -#endif - if (NULL != bbptr) { - return ((have_not != (have_y & (bbptr->fl))) ? (1) : (0)); - } - return 0; -} - - - -double -dk4bb_get_xmin( - const dk4_bb_t *bbptr -) -{ -#if DK4_USE_ASSERT - assert(NULL != bbptr); -#endif - if (NULL != bbptr) { - return bbptr->xmin; - } - return 0.0; -} - - - -double -dk4bb_get_xmax( - const dk4_bb_t *bbptr -) -{ -#if DK4_USE_ASSERT - assert(NULL != bbptr); -#endif - if (NULL != bbptr) { - return bbptr->xmax; - } - return 0.0; -} - - - -double -dk4bb_get_ymin( - const dk4_bb_t *bbptr -) -{ -#if DK4_USE_ASSERT - assert(NULL != bbptr); -#endif - if (NULL != bbptr) { - return bbptr->ymin; - } - return 0.0; -} - - - -double -dk4bb_get_ymax( - const dk4_bb_t *bbptr -) -{ -#if DK4_USE_ASSERT - assert(NULL != bbptr); -#endif - if (NULL != bbptr) { - return bbptr->ymax; - } - return 0.0; -} - - - -#if TRACE_DEBUG -static -void -dk4bb_report_bb(const dk4_bb_t *p) -{ - $? ". xmin=%g xmax=%g ymin=%g ymax=%g", p->xmin, p->xmax, p->ymin, p->ymax - $? ". flags = %u", (unsigned)(p->fl) -} -#endif - - -int -dk4bb_contains_bb( - const dk4_bb_t *pouter, - const dk4_bb_t *pinner, - int aborder -) -{ - int back = 0; - $? "+ dk4bb_contains_bb" - $? ". outer box" - $!trace-code dk4bb_report_bb(pouter); - $? ". inner box" - $!trace-code dk4bb_report_bb(pinner); - if ((NULL != pouter) && (NULL != pinner)) { $? ". boxes ok" - if ( - (have_both == (have_both & (pouter->fl))) - && (have_both == (have_both & (pinner->fl))) - ) { $? ". flags ok" - if (0 != aborder) { $? ". allow border" - if ( - (pinner->xmin >= pouter->xmin) - && (pinner->xmax <= pouter->xmax) - && (pinner->ymin >= pouter->ymin) - && (pinner->ymax <= pouter->ymax) - ) { - back = 1; - } - } - else { $? ". border not allowed" - if ( - (pinner->xmin > pouter->xmin) - && (pinner->xmax < pouter->xmax) - && (pinner->ymin > pouter->ymin) - && (pinner->ymax < pouter->ymax) - ) { - back = 1; - } - } - } - else { $? "! flags" - } - } - else { $? "! boxes" - } - $? "- dk4bb_contains_bb %d", back - return back; -} - - - -/* vim: set ai sw=4 ts=4 : */ - |