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:

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]	pnts	eight points of oriented bounding box
	points_3d	array of coplanar 3D points
	pnt_cnt	number of points in pnts array