%% 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 #endif #endif #ifndef DK4TYPES_H_INCLUDED #if DK4_BUILDING_DKTOOLS4 #include "dk4types.h" #else #include #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 #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 #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 #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 : */