BRL-CAD
obr.c File Reference
#include "common.h"
#include <stdlib.h>
#include "bu/malloc.h"
#include "bn/chull.h"
#include "bn/obr.h"
#include "bn/plane_calc.h"
#include "bn/tol.h"
#include "./bn_private.h"
Include dependency graph for obr.c:

Go to the source code of this file.

Data Structures

struct  obr_vals
 

Macros

#define F_NONE   -1
 
#define F_BOTTOM   0
 
#define F_RIGHT   1
 
#define F_TOP   2
 
#define F_LEFT   3
 
#define MAXDIST_AB(_minpt, _maxpt)
 

Functions

HIDDEN int pnt2d_array_get_dimension (const point2d_t *pnts, int pnt_cnt, point2d_t *p_center, point2d_t *p1, point2d_t *p2)
 
HIDDEN void UpdateBox (struct obr_vals *obr, point2d_t left_pnt, point2d_t right_pnt, point2d_t bottom_pnt, point2d_t top_pnt, vect2d_t u)
 
HIDDEN int bn_obr_calc (const point2d_t *pnts, int pnt_cnt, struct obr_vals *obr)
 
int bn_2d_obr (point2d_t *center, vect2d_t *u, vect2d_t *v, const point2d_t *pnts, int pnt_cnt)
 Routines for the computation of oriented bounding rectangles 2D and 3D. More...
 
int bn_3d_coplanar_obr (point_t *center, vect_t *v1, vect_t *v2, const point_t *pnts, 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...
 

Detailed Description

This file implements the Rotating Calipers algorithm for finding the minimum oriented bounding rectangle for a convex hull:

Shamos, Michael, "Analysis of the complexity of fundamental geometric algorithms such as area computation, sweep-line algorithms, polygon intersection, Voronoi diagram construction, and minimum spanning tree." Phd Thesis, Yale, 1978.

Godfried T. Toussaint, "Solving geometric problems with the rotating calipers," Proceedings of IEEE MELECON'83, Athens, Greece, May 1983.

This is a translation of the Geometric Tools MinBox2 implementation: http://www.geometrictools.com/LibMathematics/Containment/Wm5ContMinBox2.cpp http://www.geometrictools.com/LibMathematics/Algebra/Wm5Vector2.inl

Definition in file obr.c.

Macro Definition Documentation

#define F_NONE   -1

Definition at line 65 of file obr.c.

Referenced by bn_obr_calc().

#define F_BOTTOM   0

Definition at line 66 of file obr.c.

Referenced by bn_obr_calc().

#define F_RIGHT   1

Definition at line 67 of file obr.c.

Referenced by bn_obr_calc().

#define F_TOP   2

Definition at line 68 of file obr.c.

Referenced by bn_obr_calc().

#define F_LEFT   3

Definition at line 69 of file obr.c.

Referenced by bn_obr_calc().

#define MAXDIST_AB (   _minpt,
  _maxpt 
)
Value:
{ \
fastf_t md_dist = DIST_PT2_PT2(_minpt, _maxpt); \
if (md_dist > dmax) { \
dmax = md_dist; \
V2MOVE(A, _minpt); \
V2MOVE(B, _maxpt); \
} \
}
if(share_geom)
Definition: nmg_mod.c:3829
#define A
Definition: msr.c:51
double fastf_t
Definition: defines.h:300

Referenced by pnt2d_array_get_dimension().

Function Documentation

HIDDEN int pnt2d_array_get_dimension ( const point2d_t *  pnts,
int  pnt_cnt,
point2d_t *  p_center,
point2d_t *  p1,
point2d_t *  p2 
)

Definition at line 72 of file obr.c.

References A, bn_dist_pt2_lseg2(), BN_TOL_DIST, BN_TOL_MAGIC, bn_tol::dist_sq, MAXDIST_AB, NEAR_ZERO, and VSET.

Referenced by bn_obr_calc().

Here is the call graph for this function:

HIDDEN void UpdateBox ( struct obr_vals obr,
point2d_t  left_pnt,
point2d_t  right_pnt,
point2d_t  bottom_pnt,
point2d_t  top_pnt,
vect2d_t  u 
)
HIDDEN int bn_obr_calc ( const point2d_t *  pnts,
int  pnt_cnt,
struct obr_vals obr 
)

Definition at line 201 of file obr.c.

References obr_vals::area, bn_2d_chull(), BN_TOL_DIST, bu_calloc(), bu_free(), obr_vals::center, obr_vals::extent0, obr_vals::extent1, F_BOTTOM, F_LEFT, F_NONE, F_RIGHT, F_TOP, pnt2d_array_get_dimension(), obr_vals::u, OSL::Strings::u, UpdateBox(), and obr_vals::v.

Referenced by bn_2d_obr().

Here is the call graph for this function: