HDK
|
Go to the source code of this file.
Classes | |
class | UT_Array< T > |
class | UT_OBBox2DT< T > |
Typedefs | |
typedef UT_OBBox2DT< fpreal > | UT_OBBox2DR |
typedef UT_OBBox2DT< fpreal32 > | UT_OBBox2DF |
typedef UT_OBBox2DT< fpreal64 > | UT_OBBox2DD |
Functions | |
template<typename T > | |
UT_API int | UTconvexHull2D (const UT_Array< UT_Vector2T< T > > &pts, UT_Array< int > &hull, bool exclude_on_edge_pts=true) |
typedef UT_OBBox2DT<fpreal64> UT_OBBox2DD |
Definition at line 221 of file UT_OBBox2D.h.
typedef UT_OBBox2DT<fpreal32> UT_OBBox2DF |
Definition at line 220 of file UT_OBBox2D.h.
typedef UT_OBBox2DT<fpreal> UT_OBBox2DR |
Definition at line 219 of file UT_OBBox2D.h.
UT_API int UTconvexHull2D | ( | const UT_Array< UT_Vector2T< T > > & | pts, |
UT_Array< int > & | 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.