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]	center	center of oriented bounding rectangle
[out]	u	vector in the direction of obr x with vector length of 0.5 * obr length
[out]	v	vector in the obr y direction with vector length of 0.5 * obr width
	points_2d	array of 2D points
	pnt_cnt	number 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]	center	center of oriented bounding rectangle
[out]	v1	vector in the direction of obr x with vector length of 0.5 * obr length
[out]	v2	vector in the obr y direction with vector length of 0.5 * obr width
	points_3d	array of coplanar 3D points
	pnt_cnt	number 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 - want to look not only at their MinimumVolumeBox3 implementation but the supporting convex hull 3d routines to see if they're an improvement on the Clarkson implementation. Also want to check their obb/obb intersection test (GteIntrOrientedBox3OrientedBox3.h)

http://www.geometrictools.com/GTEngine/Include/GteMinimumVolumeBox3.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]	pnts	eight points of oriented bounding box
	points_3d	array of coplanar 3D points
	pnt_cnt	number of points in pnts array