All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_OBBox2D.h File Reference
#include "UT_API.h"
#include "UT_Matrix2.h"
#include "UT_Vector2.h"
+ Include dependency graph for UT_OBBox2D.h:
+ This graph shows which files directly or indirectly include this file:

Go to the source code of this file.


class  UT_Array< T >
class  UT_OBBox2DT< T >


typedef UT_OBBox2DT< fprealUT_OBBox2DR
typedef UT_OBBox2DT< fpreal32UT_OBBox2DF
typedef UT_OBBox2DT< fpreal64UT_OBBox2DD


template<typename T >
UT_API int UTconvexHull2D (const UT_Array< UT_Vector2T< T > > &pts, UT_IntArray &hull, bool exclude_on_edge_pts=true)

Typedef Documentation

Definition at line 221 of file UT_OBBox2D.h.

Definition at line 220 of file UT_OBBox2D.h.

Definition at line 219 of file UT_OBBox2D.h.

Function Documentation

template<typename T >
UT_API int UTconvexHull2D ( const UT_Array< UT_Vector2T< T > > &  pts,
UT_IntArray hull,
bool  exclude_on_edge_pts = true 

Auxiliary function to compute the convex hull of a set of points in 2D. Unlike the implementation in UT_QuickHull, this is a robust implementation of Fortune's algorithm using exact predicates. Robustness implies that the resulting convex hull passes the counter-clockwise test with infinite precision for any edge of the convex hull and a third point in the input set.

The output of the algorithm is the indices of the points that appear on the boundary of the convex hull in the order they do.

If set to false, the optional parameter 'exclude_on_edge_pts' makes the algorithm return points that lie along the interior of convex hull edges in the output sequence. Otherwise, only strict convex hull vertices are returned, i.e. those that cannot be written as nontrivial convex combinations of other points.

The return value is the index of a convex hull point p1 which together with the first point p0 in the generated convex hull, have the property that the entire convex hull projects to the line p0p1 between p0 and p1.