Collaboration diagram for Polynomials:


This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.

## 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)

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...

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)

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_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)

## 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, b ) (((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, b ) (((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 )

 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)

 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] area The interior area of the polygon [in] npts Number of point_ts, stored in pts [in] pts All 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] cent The centroid of the polygon [in] npts Number of point_ts, stored in pts [in] pts all 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] npts Array, which stores for every face the number of point_ts, added to pts. Needs to be allocated with npts[neqs] already. [out] pts 2D-array which stores the point_ts for every face. The array needs to be allocated with pts[neqs][neqs-1] already. [in] neqs Number of plane_ts, stored in eqs [in] eqs Array, 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] npts Number of points, pts contains pts Array of point_ts, building a convex polygon. Duplicated points aren't allowed. The points in the array will be sorted counter-clockwise. [in] cmp Plane 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.

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.

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 )

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.

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.

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: