BRL-CAD
Oriented Bounding Rectangles/Rectangular Cuboids
Collaboration diagram for Oriented Bounding Rectangles/Rectangular Cuboids:

Functions

int bg_2d_obr (point2d_t *center, vect2d_t *u, vect2d_t *v, const point2d_t *points_2d, int pnt_cnt)
 Routines for the computation of oriented bounding rectangles 2D and 3D. More...
 
int bg_3d_coplanar_obr (point_t *center, vect_t *v1, vect_t *v2, const point_t *points_3d, int pnt_cnt)
 Uses the Rotating Calipers algorithm to find the minimum oriented bounding rectangle for a set of coplanar 3D points. Returns 0 on success. More...
 
int bg_3d_obb (point_t **pnts, const point_t *points_3d, int pnt_cnt)
 Find the minimum oriented bounding rectangular cuboid for a set of 3D points. Returns 0 on success. More...
 

Detailed Description

Function Documentation

◆ bg_2d_obr()

int bg_2d_obr ( point2d_t center,
vect2d_t u,
vect2d_t v,
const point2d_t points_2d,
int  pnt_cnt 
)

Routines for the computation of oriented bounding rectangles 2D and 3D.

Uses the Rotating Calipers algorithm to find the minimum oriented bounding rectangle for a set of 2D points. Returns 0 on success.

The box will be described by a center point and 2 vectors:

* ----------------------------
* |            ^             |
* |            |             |
* |         v  |             |
* |            |             |
* |            *------------>|
* |         center     u     |
* |                          |
* |                          |
* ----------------------------
* 

Note that the box is oriented, and thus not necessarily axis aligned (u and v are perpendicular, but not necessarily parallel with the coordinate space V=0 and U=0 axis vectors.)

Parameters
[out]centercenter of oriented bounding rectangle
[out]uvector in the direction of obr x with vector length of 0.5 * obr length
[out]vvector in the obr y direction with vector length of 0.5 * obr width
points_2darray of 2D points
pnt_cntnumber of points in pnts array

◆ bg_3d_coplanar_obr()

int bg_3d_coplanar_obr ( point_t center,
vect_t v1,
vect_t v2,
const point_t points_3d,
int  pnt_cnt 
)

Uses the Rotating Calipers algorithm to find the minimum oriented bounding rectangle for a set of coplanar 3D points. Returns 0 on success.

Parameters
[out]centercenter of oriented bounding rectangle
[out]v1vector in the direction of obr x with vector length of 0.5 * obr length
[out]v2vector in the obr y direction with vector length of 0.5 * obr width
points_3darray of coplanar 3D points
pnt_cntnumber of points in pnts array

◆ bg_3d_obb()

int bg_3d_obb ( point_t **  pnts,
const point_t points_3d,
int  pnt_cnt 
)

Find the minimum oriented bounding rectangular cuboid for a set of 3D points. Returns 0 on success.

TODO - the GeometricTools engine has an implementation of the stack needed to do this:

https://github.com/davideberly/GeometricTools/blob/master/GTE/Mathematics/MinimumVolumeBox3.h

The points in the output array are arranged as seen in the figure below, with the integer number at each vertex position corresponding to the pnts array index n-1 (for example, the first point, labeled 1 below, would be pnts[0].)

*            8
*         *  |   *
*      *     |       *
*  4         |           7
*  |    *    |        *  |
*  |         *     *     |
*  |         |  3        |
*  |         |  |        |
*  |         5  |        |
*  |       *    |*       |
*  |   *        |    *   |
*  1            |        6
*      *        |     *
*           *   |  *
*               2
* 
Parameters
[out]pntseight points of oriented bounding box
points_3darray of coplanar 3D points
pnt_cntnumber of points in pnts array