BRL-CAD
Collaboration diagram for Polynomials:

Files

file  multipoly.c
 
file  poly.c
 

Data Structures

struct  bn_multipoly
 Polynomial data type. More...
 
struct  bn_poly
 

Macros

#define BN_MAX_POLY_DEGREE   6 /* Maximum Poly Order */
 Library for dealing with polynomials. More...
 
#define BN_CK_POLY(_p)   BU_CKMAG(_p, BN_POLY_MAGIC, "struct bn_poly")
 
#define BN_POLY_NULL   ((struct bn_poly *)NULL)
 
#define BN_POLY_INIT_ZERO   { BN_POLY_MAGIC, 0, {0.0} }
 
#define FAILSTR   "failure in multipoly.c"
 
#define Max(a, b)   (((a) > (b)) ? (a) : (b))
 
#define Min(a, b)   (((a) > (b)) ? (a) : (b))
 
#define CUBEROOT(a)   (((a) > 0.0) ? pow(a, THIRD) : -pow(-(a), THIRD))
 

Typedefs

typedef struct bn_multipoly bn_multipoly_t
 Polynomial data type. More...
 
typedef struct bn_poly bn_poly_t
 

Functions

struct bn_polybn_poly_mul (struct bn_poly *product, const struct bn_poly *m1, const struct bn_poly *m2)
 multiply two polynomials More...
 
struct bn_polybn_poly_scale (struct bn_poly *eqn, double factor)
 scale a polynomial More...
 
struct bn_polybn_poly_add (struct bn_poly *sum, const struct bn_poly *poly1, const struct bn_poly *poly2)
 add two polynomials More...
 
struct bn_polybn_poly_sub (struct bn_poly *diff, const struct bn_poly *poly1, const struct bn_poly *poly2)
 subtract two polynomials More...
 
void bn_poly_synthetic_division (struct bn_poly *quo, struct bn_poly *rem, const struct bn_poly *dvdend, const struct bn_poly *dvsor)
 Divides any polynomial into any other polynomial using synthetic division. Both polynomials must have real coefficients. More...
 
int bn_poly_quadratic_roots (struct bn_complex roots[], const struct bn_poly *quadrat)
 Uses the quadratic formula to find the roots (in `complex' form) of any quadratic equation with real coefficients. More...
 
int bn_poly_cubic_roots (struct bn_complex roots[], const struct bn_poly *eqn)
 Uses the cubic formula to find the roots (in `complex' form) of any cubic equation with real coefficients. More...
 
int bn_poly_quartic_roots (struct bn_complex roots[], const struct bn_poly *eqn)
 Uses the quartic formula to find the roots (in `complex' form) of any quartic equation with real coefficients. More...
 
int bn_poly_findroot (bn_poly_t *eqn, bn_complex_t *nxZ, const char *str)
 
void bn_poly_eval_w_2derivatives (bn_complex_t *cZ, bn_poly_t *eqn, bn_complex_t *b, bn_complex_t *c, bn_complex_t *d)
 
int bn_poly_checkroots (bn_poly_t *eqn, bn_complex_t *roots, int nroots)
 
void bn_poly_deflate (bn_poly_t *oldP, bn_complex_t *root)
 
int bn_poly_roots (bn_poly_t *eqn, bn_complex_t roots[], const char *name)
 
void bn_pr_poly (const char *title, const struct bn_poly *eqn)
 
void bn_pr_roots (const char *title, const struct bn_complex roots[], int n)
 
int bn_polygon_area (fastf_t *area, size_t npts, const point_t *pts)
 Functions for working with polygons. More...
 
int bn_polygon_centroid (point_t *cent, size_t npts, const point_t *pts)
 Calculate the centroid of a non self-intersecting polygon. More...
 
int bn_polygon_mk_pts_planes (size_t *npts, point_t **pts, size_t neqs, const plane_t *eqs)
 Calculate for an array of plane_eqs, which build a polyhedron, the point_t's for each face. More...
 
int bn_polygon_sort_ccw (size_t npts, point_t *pts, plane_t cmp)
 Sort an array of point_ts, building a convex polygon, counter-clockwise. More...
 
struct bn_multipolybn_multipoly_new (int dgrs, int dgrt)
 create new multipoly of a given size with coefficients set to 0 More...
 
struct bn_multipolybn_multipoly_grow (register struct bn_multipoly *P, int dgrs, int dgrt)
 grow the cf array to be at least [dgrx][dgry], sets new entries to 0 More...
 
struct bn_multipolybn_multipoly_set (register struct bn_multipoly *P, int s, int t, double val)
 set a coefficient growing cf array if needed More...
 
struct bn_multipolybn_multipoly_add (register struct bn_multipoly *p1, register struct bn_multipoly *p2)
 add two polynomials More...
 
struct bn_multipolybn_multipoly_mul (register struct bn_multipoly *p1, register struct bn_multipoly *p2)
 multiply two polynomials More...
 
struct bn_polybn_poly_mul (register struct bn_poly *product, register const struct bn_poly *m1, register const struct bn_poly *m2)
 
struct bn_polybn_poly_scale (register struct bn_poly *eqn, double factor)
 
struct bn_polybn_poly_add (register struct bn_poly *sum, register const struct bn_poly *poly1, register const struct bn_poly *poly2)
 
struct bn_polybn_poly_sub (register struct bn_poly *diff, register const struct bn_poly *poly1, register const struct bn_poly *poly2)
 
void bn_poly_synthetic_division (register struct bn_poly *quo, register struct bn_poly *rem, register const struct bn_poly *dvdend, register const struct bn_poly *dvsor)
 
int bn_poly_quadratic_roots (register struct bn_complex *roots, register const struct bn_poly *quadrat)
 
int bn_poly_cubic_roots (register struct bn_complex *roots, register const struct bn_poly *eqn)
 
int bn_poly_quartic_roots (register struct bn_complex *roots, register const struct bn_poly *eqn)
 
void bn_pr_poly (const char *title, register const struct bn_poly *eqn)
 
void bn_pr_roots (const char *title, const struct bn_complex *roots, int n)
 

Detailed Description

Macro Definition Documentation

#define BN_MAX_POLY_DEGREE   6 /* Maximum Poly Order */

Library for dealing with polynomials.

Definition at line 41 of file poly.h.

Referenced by bn_poly_mul().

#define BN_CK_POLY (   _p)    BU_CKMAG(_p, BN_POLY_MAGIC, "struct bn_poly")

Definition at line 53 of file poly.h.

#define BN_POLY_NULL   ((struct bn_poly *)NULL)

Definition at line 54 of file poly.h.

Referenced by bn_poly_mul().

#define BN_POLY_INIT_ZERO   { BN_POLY_MAGIC, 0, {0.0} }

Definition at line 55 of file poly.h.

Referenced by test_bn_poly_syn_div().

#define FAILSTR   "failure in multipoly.c"

Definition at line 40 of file multipoly.c.

Referenced by bn_multipoly_grow(), and bn_multipoly_new().

#define Max (   a,
 
)    (((a) > (b)) ? (a) : (b))

Definition at line 43 of file multipoly.c.

Referenced by bn_multipoly_add(), bn_multipoly_grow(), BuildTree(), and FindMedian().

#define Min (   a,
 
)    (((a) > (b)) ? (a) : (b))

Definition at line 44 of file multipoly.c.

Referenced by BuildTree(), and FindMedian().

#define CUBEROOT (   a)    (((a) > 0.0) ? pow(a, THIRD) : -pow(-(a), THIRD))

Definition at line 41 of file poly.c.

Referenced by bn_poly_cubic_roots().

Typedef Documentation

typedef struct bn_multipoly bn_multipoly_t

Polynomial data type.

typedef struct bn_poly bn_poly_t

Polynomial data type bn_poly->cf[n] corresponds to X^n

Function Documentation

struct bn_poly* bn_poly_mul ( struct bn_poly product,
const struct bn_poly m1,
const struct bn_poly m2 
)

multiply two polynomials

bn_poly_mul

Referenced by rt_revolve_shot(), and test_bn_poly().

struct bn_poly* bn_poly_scale ( struct bn_poly eqn,
double  factor 
)

scale a polynomial

bn_poly_scale

Referenced by rt_poly_roots(), rt_revolve_shot(), and test_bn_poly_scale().

struct bn_poly* bn_poly_add ( struct bn_poly sum,
const struct bn_poly poly1,
const struct bn_poly poly2 
)

add two polynomials

bn_poly_add

Referenced by rt_revolve_shot(), and test_bn_poly_add().

struct bn_poly* bn_poly_sub ( struct bn_poly diff,
const struct bn_poly poly1,
const struct bn_poly poly2 
)

subtract two polynomials

bn_poly_sub

Referenced by rt_revolve_shot(), and test_bn_poly_sub().

void bn_poly_synthetic_division ( struct bn_poly quo,
struct bn_poly rem,
const struct bn_poly dvdend,
const struct bn_poly dvsor 
)

Divides any polynomial into any other polynomial using synthetic division. Both polynomials must have real coefficients.

Referenced by rt_poly_deflate(), and test_bn_poly_syn_div().

int bn_poly_quadratic_roots ( struct bn_complex  roots[],
const struct bn_poly quadrat 
)

Uses the quadratic formula to find the roots (in `complex' form) of any quadratic equation with real coefficients.

Returns
1 for success
0 for fail.

Referenced by rt_poly_roots().

int bn_poly_cubic_roots ( struct bn_complex  roots[],
const struct bn_poly eqn 
)

Uses the cubic formula to find the roots (in `complex' form) of any cubic equation with real coefficients.

to solve a polynomial of the form:

X**3 + c1*X**2 + c2*X + c3 = 0,

first reduce it to the form:

Y**3 + a*Y + b = 0,

where Y = X + c1/3, and a = c2 - c1**2/3, b = (2*c1**3 - 9*c1*c2 + 27*c3)/27.

Then we define the value delta, D = b**2/4 + a**3/27.

If D > 0, there will be one real root and two conjugate complex roots. If D = 0, there will be three real roots at least two of which are equal. If D < 0, there will be three unequal real roots.

Returns 1 for success, 0 for fail.

Referenced by rt_poly_roots(), and test_bn_poly_cubic_rts().

int bn_poly_quartic_roots ( struct bn_complex  roots[],
const struct bn_poly eqn 
)

Uses the quartic formula to find the roots (in `complex' form) of any quartic equation with real coefficients.

Returns
1 for success
0 for fail.

Referenced by rt_poly_roots(), and test_bn_poly_qua_rts().

int bn_poly_findroot ( bn_poly_t eqn,
bn_complex_t nxZ,
const char *  str 
)
void bn_poly_eval_w_2derivatives ( bn_complex_t cZ,
bn_poly_t eqn,
bn_complex_t b,
bn_complex_t c,
bn_complex_t d 
)
int bn_poly_checkroots ( bn_poly_t eqn,
bn_complex_t roots,
int  nroots 
)
void bn_poly_deflate ( bn_poly_t oldP,
bn_complex_t root 
)
int bn_poly_roots ( bn_poly_t eqn,
bn_complex_t  roots[],
const char *  name 
)
void bn_pr_poly ( const char *  title,
const struct bn_poly eqn 
)

Print out the polynomial.

void bn_pr_roots ( const char *  title,
const struct bn_complex  roots[],
int  n 
)

Print out the roots of a given polynomial (complex numbers)

Referenced by bend_pipe_shot(), rt_eto_shot(), rt_hrt_shot(), rt_hrt_vshot(), rt_revolve_shot(), rt_superell_shot(), rt_tgc_shot(), rt_tgc_vshot(), rt_tor_shot(), and rt_tor_vshot().

int bn_polygon_area ( fastf_t area,
size_t  npts,
const point_t *  pts 
)

Functions for working with polygons.

Calculate the interior area of a polygon.

If npts > 4, Greens Theorem is used. The polygon mustn't be self-intersecting.

Parameters
[out]areaThe interior area of the polygon
[in]nptsNumber of point_ts, stored in pts
[in]ptsAll points of the polygon, sorted counter-clockwise. The array mustn't contain duplicated points.
Returns
0 if calculation was successful
1 if calculation failed, e.g. because one parameter is a NULL-pointer

Definition at line 28 of file polygon.c.

References bn_mk_plane_3pts(), BN_TOL_DIST, BN_TOL_INIT, and bn_tol::dist_sq.

Referenced by analyze_poly_face(), and rt_bot_volume().

Here is the call graph for this function:

int bn_polygon_centroid ( point_t *  cent,
size_t  npts,
const point_t *  pts 
)

Calculate the centroid of a non self-intersecting polygon.

Parameters
[out]centThe centroid of the polygon
[in]nptsNumber of point_ts, stored in pts
[in]ptsall points of the polygon, sorted counter-clockwise. The array mustn't contain duplicated points.
Returns
0 if calculation was successful
1 if calculation failed, e.g. because one in-parameter is a NULL-pointer

Definition at line 72 of file polygon.c.

Referenced by rt_arbn_centroid(), and rt_nmg_centroid().

int bn_polygon_mk_pts_planes ( size_t *  npts,
point_t **  pts,
size_t  neqs,
const plane_t *  eqs 
)

Calculate for an array of plane_eqs, which build a polyhedron, the point_t's for each face.

Parameters
[out]nptsArray, which stores for every face the number of point_ts, added to pts. Needs to be allocated with npts[neqs] already.
[out]pts2D-array which stores the point_ts for every face. The array needs to be allocated with pts[neqs][neqs-1] already.
[in]neqsNumber of plane_ts, stored in eqs
[in]eqsArray, that contains the plane equations, which build the polyhedron
Returns
0 if calculation was successful
1 if calculation failed, e.g. because one parameter is a NULL-Pointer

Definition at line 137 of file polygon.c.

References bn_mkpoint_3planes(), and BN_TOL_DIST.

Referenced by analyze_arbn().

Here is the call graph for this function:

int bn_polygon_sort_ccw ( size_t  npts,
point_t *  pts,
plane_t  cmp 
)

Sort an array of point_ts, building a convex polygon, counter-clockwise.

Parameters
[in]nptsNumber of points, pts contains
ptsArray of point_ts, building a convex polygon. Duplicated points aren't allowed. The points in the array will be sorted counter-clockwise.
[in]cmpPlane equation of the polygon
Returns
0 if calculation was successful
1 if calculation failed, e.g. because pts is a NULL-pointer

Definition at line 182 of file polygon.c.

References bu_sort(), and sort_ccw().

Referenced by analyze_poly_face(), and rt_bot_volume().

Here is the call graph for this function:

struct bn_multipoly* bn_multipoly_new ( int  dgrs,
int  dgrt 
)

create new multipoly of a given size with coefficients set to 0

bn_multipoly_new

Definition at line 52 of file multipoly.c.

References BU_ALLOC, bu_malloc(), bn_multipoly::cf, bn_multipoly::dgrs, bn_multipoly::dgrt, FAILSTR, and s.

Referenced by bn_multipoly_add(), and bn_multipoly_mul().

Here is the call graph for this function:

struct bn_multipoly* bn_multipoly_grow ( register struct bn_multipoly P,
int  dgrs,
int  dgrt 
)

grow the cf array to be at least [dgrx][dgry], sets new entries to 0

bn_multipoly_grow

Definition at line 80 of file multipoly.c.

References bu_malloc(), bu_realloc(), bn_multipoly::cf, bn_multipoly::dgrs, bn_multipoly::dgrt, FAILSTR, Max, and OSL::Strings::P.

Referenced by bn_multipoly_set().

Here is the call graph for this function:

struct bn_multipoly* bn_multipoly_set ( register struct bn_multipoly P,
int  s,
int  t,
double  val 
)

set a coefficient growing cf array if needed

bn_multipoly_set

Definition at line 109 of file multipoly.c.

References bn_multipoly_grow(), bn_multipoly::cf, OSL::Strings::P, and s.

Here is the call graph for this function:

struct bn_multipoly* bn_multipoly_add ( register struct bn_multipoly p1,
register struct bn_multipoly p2 
)

add two polynomials

bn_multipoly_add

Definition at line 122 of file multipoly.c.

References bn_multipoly_new(), bn_multipoly::cf, bn_multipoly::dgrs, bn_multipoly::dgrt, Max, and s.

Here is the call graph for this function:

struct bn_multipoly* bn_multipoly_mul ( register struct bn_multipoly p1,
register struct bn_multipoly p2 
)

multiply two polynomials

bn_multipoly_mul

Definition at line 141 of file multipoly.c.

References bn_multipoly_new(), bn_multipoly::cf, bn_multipoly::dgrs, and bn_multipoly::dgrt.

Here is the call graph for this function:

struct bn_poly* bn_poly_mul ( register struct bn_poly product,
register const struct bn_poly m1,
register const struct bn_poly m2 
)

Definition at line 50 of file poly.c.

References BN_MAX_POLY_DEGREE, BN_POLY_NULL, bn_poly::cf, and bn_poly::dgr.

struct bn_poly* bn_poly_scale ( register struct bn_poly eqn,
double  factor 
)

Definition at line 99 of file poly.c.

References bn_poly::cf, and bn_poly::dgr.

struct bn_poly* bn_poly_add ( register struct bn_poly sum,
register const struct bn_poly poly1,
register const struct bn_poly poly2 
)

Definition at line 111 of file poly.c.

References bn_poly::cf, and bn_poly::dgr.

struct bn_poly* bn_poly_sub ( register struct bn_poly diff,
register const struct bn_poly poly1,
register const struct bn_poly poly2 
)

Definition at line 140 of file poly.c.

References bn_poly::cf, and bn_poly::dgr.

void bn_poly_synthetic_division ( register struct bn_poly quo,
register struct bn_poly rem,
register const struct bn_poly dvdend,
register const struct bn_poly dvsor 
)

Definition at line 171 of file poly.c.

References bn_poly::cf, and bn_poly::dgr.

int bn_poly_quadratic_roots ( register struct bn_complex roots,
register const struct bn_poly quadrat 
)

Definition at line 201 of file poly.c.

References bn_poly::cf, bn_complex::im, NEAR_ZERO, bn_complex::re, and SMALL_FASTF.

Referenced by bn_poly_quartic_roots().

int bn_poly_cubic_roots ( register struct bn_complex roots,
register const struct bn_poly eqn 
)

Definition at line 261 of file poly.c.

References A, bn_poly::cf, CUBEROOT, delta, bn_complex::im, bn_complex::re, SQRT_MAX_FASTF, and ZERO.

Referenced by bn_poly_quartic_roots().

int bn_poly_quartic_roots ( register struct bn_complex roots,
register const struct bn_poly eqn 
)

Definition at line 339 of file poly.c.

References bn_poly_cubic_roots(), bn_poly_quadratic_roots(), bn_poly::cf, bn_poly::dgr, Max3, NEAR_ZERO, OSL::Strings::u, and ZERO.

Here is the call graph for this function:

void bn_pr_poly ( const char *  title,
register const struct bn_poly eqn 
)

Definition at line 418 of file poly.c.

References bu_log(), bu_vls_addr(), bu_vls_extend(), bu_vls_free(), BU_VLS_INIT_ZERO, bu_vls_printf(), bu_vls_strcat(), bn_poly::cf, and bn_poly::dgr.

Here is the call graph for this function:

void bn_pr_roots ( const char *  title,
const struct bn_complex roots,
int  n 
)

Definition at line 458 of file poly.c.

References bu_log().

Here is the call graph for this function: