Files
file	WlzConvexHull.c
	Functions for computing the convex hull of objects.

file	WlzConvexHull3D.c
	Functions for computing 3D convex hull domains.

file	WlzConvexHullClarkson.c
	Functions to compute convex hulls using the Clarkson's algorithm.

file	WlzMwrAngle.c
	Computes the minimum width rectangle from a convex hull. This code has been extensively rewritten for the new convex hull domains, so that only the original interface and algorithm remain.

Data Structures
struct	_WlzConvHullDomain2
	A 2D convex hull with counter clockwise ordered vertices and segments implicitly defined by the polygon of the ordered vertices. Typedef: WlzConvHullDomain3. More...

struct	_WlzConvHullDomain3
	A 3D convex hull with coordinate vertices and faces defined by vertex index triples. Typedef: WlzConvHullDomain3. More...

Functions
WlzConvHullDomain2 *	WlzMakeConvexHullDomain2 (int maxVtx, WlzVertexType vtxType, WlzErrorNum *dstErr)
	Allocates a new 2D convex hull domain with space for at least the requested number of vertices. More...

WlzConvHullDomain3 *	WlzMakeConvexHullDomain3 (int maxVtx, int maxFce, WlzVertexType vtxType, WlzErrorNum *dstErr)
	Allocates a new 3D convex hull domain with space for at least the requested number of vertices and faces. More...

WlzErrorNum	WlzFreeConvexHullDomain2 (WlzConvHullDomain2 *cvh)
	Frees the given 2D convex hull domain. More...

WlzErrorNum	WlzFreeConvexHullDomain3 (WlzConvHullDomain3 *cvh)
	Frees the given 3D convex hull domain. More...

WlzConvHullDomain2 *	WlzConvexHullCopy2 (WlzConvHullDomain2 gCVH, WlzVertexType rVtxType, WlzErrorNum dstErr)
	Copies the given 2D convex hull domain which has the minimum required number of vertices, with verticies of the required type. More...

WlzConvHullDomain3 *	WlzConvexHullCopy3 (WlzConvHullDomain3 gCVH, WlzVertexType rVtxType, WlzErrorNum dstErr)
	Copies the given 3D convex hull domain which has the minimum required number of vertices and faces, with verticies of the required type. More...

WlzObject *	WlzConvexHullToObj (WlzObject cObj, WlzObjectType rType, WlzErrorNum dstErr)
	Computes a new object of the requested type enclosing the same region of space as the given convex hull object. More...

WlzObject *	WlzObjToConvexHull (WlzObject gObj, WlzErrorNum dstErr)
	Computes the convex hull of the given object. If a degenerate convex hull is returned then the returned error will be WLZ_ERR_DEGENERATE. More...

WlzObject *	WlzObjToConvexPolygon (WlzObject obj, WlzErrorNum dstErr)
	Construct the minimal convex polygonal cover from interval domain. More...

WlzIVertex2	WlzConvexHullVtxD2ToI2 (WlzDVertex2 d, WlzDVertex2 c)
	Convert the given double vertex to an integer vertex such that it will enclose the given convex hull double vertex. More...

WlzIVertex3	WlzConvexHullVtxD3ToI3 (WlzDVertex3 d, WlzDVertex3 c)
	Convert the given double vertex to an integer vertex such that it will enclose the given convex hull double vertex. More...

WlzConvHullDomain3 *	WlzConvexHullFromVtx3 (WlzVertexType pType, int nPnt, WlzVertexP pnt, WlzErrorNum *dstErr)
	Creates a new 3D convex hull domain which encloses the given vertices using a randomized incremental algorithm based on Clarkson and Shor's algorithm: Kenneth L. Clarkson and PeterW. Shor. "Applications of Random Sampling in Computational Geometry, II", Discrete & Computational Geometry 4(1) 1989. This algorithm is also described in a way more suited for implementation in: Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars. "Computational Geometry: Algorithms and Applications", Springer. The algorithm makes use of randomized insertion, lists, queues and a conflict graph of conflicts between vertices and faces. A vertex and face are said to be in conflict when a vertex does not lie behind the face, where behind means in the half-plane defined by the face and the body of the convex hull. In practice the vertex-behind-face test accounts for the almost all the CPU time. The expected run time for this algorithm is O(n log n). On a 3GHz Intel i7 the computation time is a ~10ms for 10^4 vertices randomly distributed over a cube but ~1s for 10^5 vertices. When given a degenerate set of vertices (all on a single plane, all on a single line or all coincident) this function will still compute a 3D convex hull domain but will set the error code to WLZ_ERR_DEGENERATE to indicate this. More...

WlzConvHullDomain2 *	WlzConvexHullFromVtx2 (WlzVertexType pType, int nPnt, WlzVertexP pnt, WlzErrorNum *dstErr)
	Creates a new 2D convex hull domain which encloses the given vertices using Clarkson's algorithm, see WlzConvHullClarkson2I() and WlzConvHullClarkson2D(). In degenerate cases (less than 3 vertices or all vertices on a single line) a convex hull domain will still be computed but the returned error code will be WLZ_ERR_DEGENERATE. More...

int	WlzConvHullClarkson2I (WlzIVertex2 vtx, int n, int dstIdx, WlzErrorNum dstErr)
	Computes the convex hull of a given array of 2D integer vertices which is returned as an array of indices into the array of vertices. This index array should be freed using AlcFree(). The vertex array is not changed. More...

int	WlzConvHullClarkson2D (WlzDVertex2 vtx, int n, int dstIdx, WlzErrorNum dstErr)
	Computes the convex hull of a given array of 2D double vertices which is returned as an array of indices into the array of vertices. This index array should be freed using AlcFree(). The vertex array is not changed. More...

double	WlzMwrAngle (WlzObject cObj, WlzErrorNum dstErr)
	Given a 2D convex hull object, computes the angle of the minimum width rectangle which encloses the convex hull. Where the angle is in radians and with respect to the x-axis. The minimum width rectangle long side must be parallel to an edge of convex hull and all sides must have at least one vertex of convex hull lying within them. More...

Detailed Description

Function Documentation

WlzConvHullDomain2* WlzMakeConvexHullDomain2	(	int	maxVtx,
		WlzVertexType	vtxType,
		WlzErrorNum *	dstErr
	)

Allocates a new 2D convex hull domain with space for at least the requested number of vertices.

Returns: New 2D convex hull domain.

Parameters

maxVtx	Number of vertices space allocated for.
vtxType	Vertex type, must be either WLZ_VERTEX_2I or WLZ_VERTEX_2D.
dstErr	Desination error pointer, may be NULL.

References AlcCalloc(), AlcFree(), AlcMalloc(), _WlzConvHullDomain2::maxVertices, _WlzConvHullDomain2::type, _WlzVertexP::v, _WlzConvHullDomain2::vertices, _WlzConvHullDomain2::vtxType, WLZ_CONVHULL_DOMAIN_2D, WLZ_ERR_MEM_ALLOC, WLZ_ERR_NONE, WLZ_ERR_PARAM_TYPE, WLZ_VERTEX_D2, and WLZ_VERTEX_I2.

Referenced by WlzConvexHullCopy2(), WlzConvexHullFromVtx2(), and WlzReadMeshTransform3D().

WlzConvHullDomain3* WlzMakeConvexHullDomain3	(	int	maxVtx,
		int	maxFce,
		WlzVertexType	vtxType,
		WlzErrorNum *	dstErr
	)

Allocates a new 3D convex hull domain with space for at least the requested number of vertices and faces.

Returns: New 3D convex hull domain.

Parameters

maxVtx	Number of vertices space allocated for.
maxFce	Number of faces space allocated for.
vtxType	Vertex type, must be either WLZ_VERTEX_3I or WLZ_VERTEX_3D.
dstErr	Desination error pointer, may be NULL.

References AlcCalloc(), AlcFree(), AlcMalloc(), _WlzConvHullDomain3::faces, _WlzConvHullDomain3::maxFaces, _WlzConvHullDomain3::maxVertices, _WlzConvHullDomain3::type, _WlzVertexP::v, _WlzConvHullDomain3::vertices, _WlzConvHullDomain3::vtxType, WLZ_CONVHULL_DOMAIN_3D, WLZ_ERR_MEM_ALLOC, WLZ_ERR_NONE, WLZ_ERR_PARAM_TYPE, WLZ_VERTEX_D3, and WLZ_VERTEX_I3.

Referenced by WlzConvexHullCopy3(), and WlzReadMeshTransform3D().

WlzErrorNum WlzFreeConvexHullDomain2 ( WlzConvHullDomain2 * cvh )

Frees the given 2D convex hull domain.

Returns: Woolz error code.

Parameters

cvh	Given 2D convex hull domain.

References AlcFree(), _WlzConvHullDomain2::linkcount, _WlzConvHullDomain2::type, _WlzVertexP::v, _WlzConvHullDomain2::vertices, WLZ_CONVHULL_DOMAIN_2D, WLZ_ERR_DOMAIN_NULL, WLZ_ERR_DOMAIN_TYPE, WLZ_ERR_NONE, and WlzUnlink().

Referenced by WlzConvexHullFromVtx2(), WlzConvexHullVtxD3ToI3(), WlzFreeObj(), WlzObjToConvexHull(), and WlzReadMeshTransform3D().

WlzErrorNum WlzFreeConvexHullDomain3 ( WlzConvHullDomain3 * cvh )

Frees the given 3D convex hull domain.

Returns: Woolz error code.

Parameters

cvh	Given 3D convex hull domain.

References AlcFree(), _WlzConvHullDomain3::faces, _WlzConvHullDomain3::linkcount, _WlzConvHullDomain3::type, _WlzVertexP::v, _WlzConvHullDomain3::vertices, WLZ_CONVHULL_DOMAIN_3D, WLZ_ERR_DOMAIN_NULL, WLZ_ERR_DOMAIN_TYPE, WLZ_ERR_NONE, and WlzUnlink().

Referenced by WlzFreeObj(), WlzObjToConvexHull(), and WlzReadMeshTransform3D().

WlzConvHullDomain2* WlzConvexHullCopy2	(	WlzConvHullDomain2 *	gCVH,
		WlzVertexType	rVtxType,
		WlzErrorNum *	dstErr
	)

Copies the given 2D convex hull domain which has the minimum required number of vertices, with verticies of the required type.

Returns: New 2D convex hull domain.

Parameters

gCVH	Given convex hull domain.
rVtxType	Required vertex type, must be either WLZ_VERTEX_I2 or WLZ_VERTEX_D2.
dstErr	Destination error pointer, may be NULL.

References _WlzVertexP::d2, _WlzVertexP::i2, _WlzConvHullDomain2::nVertices, _WlzConvHullDomain2::type, _WlzVertexP::v, _WlzConvHullDomain2::vertices, _WlzConvHullDomain2::vtxType, WLZ_CONVHULL_DOMAIN_2D, WLZ_ERR_DOMAIN_NULL, WLZ_ERR_DOMAIN_TYPE, WLZ_ERR_NONE, WLZ_ERR_PARAM_TYPE, WLZ_VERTEX_D2, WLZ_VERTEX_I2, WlzMakeConvexHullDomain2(), WlzValueCopyDVertexToIVertex(), and WlzValueCopyIVertexToDVertex().

Referenced by WlzCopyDomain().

WlzConvHullDomain3* WlzConvexHullCopy3	(	WlzConvHullDomain3 *	gCVH,
		WlzVertexType	rVtxType,
		WlzErrorNum *	dstErr
	)

Copies the given 3D convex hull domain which has the minimum required number of vertices and faces, with verticies of the required type.

Returns: New 3D convex hull domain.

Parameters

gCVH	Given convex hull domain.
rVtxType	Required vertex type, must be either WLZ_VERTEX_I3 or WLZ_VERTEX_D3.
dstErr	Destination error pointer, may be NULL.

References _WlzVertexP::d3, _WlzConvHullDomain3::faces, _WlzVertexP::i3, _WlzConvHullDomain3::nFaces, _WlzConvHullDomain3::nVertices, _WlzConvHullDomain3::type, _WlzVertexP::v, _WlzConvHullDomain3::vertices, _WlzConvHullDomain3::vtxType, WLZ_CONVHULL_DOMAIN_3D, WLZ_ERR_DOMAIN_NULL, WLZ_ERR_DOMAIN_TYPE, WLZ_ERR_NONE, WLZ_ERR_PARAM_TYPE, WLZ_VERTEX_D3, WLZ_VERTEX_I3, WlzMakeConvexHullDomain3(), WlzValueCopyDVertexToIVertex3(), and WlzValueCopyIVertexToDVertex3().

Referenced by WlzCopyDomain().

WlzObject* WlzConvexHullToObj	(	WlzObject *	cObj,
		WlzObjectType	rType,
		WlzErrorNum *	dstErr
	)

Computes a new object of the requested type enclosing the same region of space as the given convex hull object.

Returns: New object or NULL on error.

Parameters

cObj	Given object.
rType	Requested object types. Valid types for a 2D convex hull are: WLZ_2D_DOMAINOBJ and WLZ_CONTOUR. Valid types for a 3D convex hull are: WLZ_3D_DOMAINOBJ and WLZ_CONTOUR.
dstErr	Destination error pointer, may be NULL.

References _WlzDomain::core, _WlzDomain::cvh2, _WlzDomain::cvh3, _WlzObject::domain, _WlzObject::type, _WlzCoreDomain::type, _WlzConvHullDomain2::vtxType, _WlzConvHullDomain3::vtxType, WLZ_2D_DOMAINOBJ, WLZ_3D_DOMAINOBJ, WLZ_CONTOUR, WLZ_CONV_HULL, WLZ_CONVHULL_DOMAIN_2D, WLZ_CONVHULL_DOMAIN_3D, WLZ_ERR_DOMAIN_NULL, WLZ_ERR_DOMAIN_TYPE, WLZ_ERR_OBJECT_NULL, WLZ_ERR_OBJECT_TYPE, WLZ_ERR_PARAM_TYPE, WLZ_ERR_UNIMPLEMENTED, WLZ_VERTEX_D2, WLZ_VERTEX_D3, WLZ_VERTEX_I2, and WLZ_VERTEX_I3.

Referenced by WlzOffsetDist(), and WlzRegConCalcRCC().

WlzObject* WlzObjToConvexHull	(	WlzObject *	gObj,
		WlzErrorNum *	dstErr
	)

Computes the convex hull of the given object. If a degenerate convex hull is returned then the returned error will be WLZ_ERR_DEGENERATE.

Returns: Convex hull object, NULL on error.

Parameters

gObj	Given object.
dstErr	Destination error pointer, may be NULL.

References AlcCalloc(), AlcFree(), AlcMalloc(), _WlzDomain::b, _WlzValues::core, _WlzDomain::core, _WlzDomain::cvh2, _WlzDomain::cvh3, _WlzVertexP::d2, _WlzObject::domain, _WlzPlaneDomain::domains, _WlzVertexP::i2, _WlzVertexP::i3, _WlzPlaneDomain::lastpl, _WlzBoundList::next, _WlzPolygonDomain::nvertices, _WlzConvHullDomain2::nVertices, _WlzDomain::p, _WlzPlaneDomain::plane1, _WlzDomain::poly, _WlzBoundList::poly, _WlzObject::type, _WlzCoreDomain::type, _WlzPolygonDomain::type, _WlzVertexP::v, _WlzConvHullDomain2::vertices, _WlzIVertex2::vtX, _WlzPolygonDomain::vtx, _WlzIVertex2::vtY, WLZ_2D_DOMAINOBJ, WLZ_2D_POLYGON, WLZ_3D_DOMAINOBJ, WLZ_BOUNDLIST, WLZ_CMESH_2D, WLZ_CMESH_2D5, WLZ_CMESH_3D, WLZ_CONTOUR, WLZ_CONV_HULL, WLZ_CONVHULL_DOMAIN_2D, WLZ_CONVHULL_DOMAIN_3D, WLZ_ERR_DEGENERATE, WLZ_ERR_DOMAIN_DATA, WLZ_ERR_DOMAIN_NULL, WLZ_ERR_DOMAIN_TYPE, WLZ_ERR_MEM_ALLOC, WLZ_ERR_NONE, WLZ_ERR_OBJECT_NULL, WLZ_ERR_OBJECT_TYPE, WLZ_POLYGON_DOUBLE, WLZ_POLYGON_INT, WLZ_VERTEX_D2, WLZ_VERTEX_D3, WLZ_VERTEX_I2, WLZ_VERTEX_I3, WLZ_VTX_3_SET, WlzAssignObject(), WlzConvexHullFromVtx2(), WlzConvexHullFromVtx3(), WlzFreeConvexHullDomain2(), WlzFreeConvexHullDomain3(), WlzFreeObj(), WlzMakeMain(), WlzObjToBoundary(), and WlzVerticesFromObj().

Referenced by WlzOffsetDist(), and WlzRegConCalcRCC().

WlzObject* WlzObjToConvexPolygon	(	WlzObject *	obj,
		WlzErrorNum *	dstErr
	)

Construct the minimal convex polygonal cover from interval domain.

Returns: Convex hull object.

Parameters

obj	Given object.
dstErr	Destination error pointer, may be NULL.

References AlcFree(), AlcMalloc(), _WlzConvHullDomain2::centroid, _WlzValues::core, _WlzDomain::core, _WlzDomain::ctr, _WlzVertexP::d2, _WlzVertex::d2, _WlzVertexP::d3, _WlzObject::domain, _WlzConvHullDomain3::faces, _WlzDomain::i, _WlzVertexP::i2, _WlzVertexP::i3, _WlzIntervalWSpace::intrmn, _WlzIntervalDomain::lastln, _WlzIntervalWSpace::lftpos, _WlzIntervalDomain::line1, _WlzIntervalWSpace::linpos, _WlzContour::model, _WlzConvHullDomain3::nFaces, _WlzPolygonDomain::nvertices, _WlzConvHullDomain2::nVertices, _WlzConvHullDomain3::nVertices, _WlzIntervalWSpace::nwlpos, _WlzValues::obj, _WlzDomain::p, _WlzDomain::poly, _WlzIntervalWSpace::rgtpos, _WlzObject::type, _WlzPlaneDomain::type, _WlzObject::values, _WlzConvHullDomain2::vertices, _WlzConvHullDomain3::vertices, _WlzIVertex2::vtX, _WlzDVertex2::vtX, _WlzIVertex3::vtX, _WlzDVertex3::vtX, _WlzPolygonDomain::vtx, _WlzConvHullDomain2::vtxType, _WlzConvHullDomain3::vtxType, _WlzIVertex2::vtY, _WlzDVertex2::vtY, _WlzIVertex3::vtY, _WlzDVertex3::vtY, _WlzIVertex3::vtZ, _WlzDVertex3::vtZ, WLZ_2D_DOMAINOBJ, WLZ_2D_POLYGON, WLZ_3D_DOMAINOBJ, WLZ_CONTOUR, WLZ_EMPTY_OBJ, WLZ_ERR_DOMAIN_NULL, WLZ_ERR_DOMAIN_TYPE, WLZ_ERR_EOO, WLZ_ERR_MEM_ALLOC, WLZ_ERR_NONE, WLZ_ERR_OBJECT_NULL, WLZ_ERR_OBJECT_TYPE, WLZ_ERR_UNIMPLEMENTED, WLZ_GMMOD_2D, WLZ_GMMOD_2I, WLZ_GMMOD_3D, WLZ_PLANEDOMAIN_DOMAIN, WLZ_POLYGON_INT, WLZ_RASTERDIR_DLDC, WLZ_RASTERDIR_ILIC, WLZ_TRANS_OBJ, WLZ_VERTEX_I2, WLZ_VERTEX_I3, WlzAssignGMModel(), WlzConvexHullVtxD2ToI2(), WlzFreeContour(), WlzFreeIntervalDomain(), WlzGMModelConstructSimplex2D(), WlzGMModelConstructSimplex3D(), WlzGMModelFree(), WlzGMModelNew(), WlzInitRasterScan(), WlzMakeContour(), WlzMakeEmpty(), WlzMakeMain(), WlzMakePolygonDomain(), and WlzNextInterval().

Referenced by WlzConvexHullVtxD3ToI3(), and WlzMeshFromObjBox().

WlzIVertex2 WlzConvexHullVtxD2ToI2	(	WlzDVertex2	d,
		WlzDVertex2	c
	)

Convert the given double vertex to an integer vertex such that it will enclose the given convex hull double vertex.

Returns: Integral vertex.

Parameters

d	Given convex hull double vertex.
c	Centroid of the convex hull.

References _WlzIVertex2::vtX, _WlzDVertex2::vtX, _WlzIVertex2::vtY, and _WlzDVertex2::vtY.

Referenced by WlzObjToConvexPolygon().

WlzIVertex3 WlzConvexHullVtxD3ToI3	(	WlzDVertex3	d,
		WlzDVertex3	c
	)

Convert the given double vertex to an integer vertex such that it will enclose the given convex hull double vertex.

Returns: Integral vertex.

Parameters

d	Given convex hull double vertex.
c	Centroid of the convex hull.

References AlcFree(), AlcFreeStackPush(), AlcMalloc(), AlcRealloc(), ALG_MAX, AlgHeapSortCmpIdxIFn(), AlgHeapSortIdx(), _WlzConvHullDomain3::centroid, _WlzValues::core, _WlzDomain::core, _WlzVertexP::d2, _WlzVertexP::d3, _WlzVertex::d3, _WlzObject::domain, _WlzPlaneDomain::domains, _WlzConvHullDomain3::faces, _WlzIntervalDomain::freeptr, _WlzVertexP::i3, _WlzInterval::ileft, _WlzInterval::iright, _WlzPlaneDomain::kol1, _WlzPlaneDomain::lastkl, _WlzPlaneDomain::lastln, _WlzPlaneDomain::lastpl, _WlzPlaneDomain::line1, _WlzConvHullDomain3::nFaces, _WlzConvHullDomain3::nVertices, _WlzDomain::p, _WlzPlaneDomain::plane1, _WlzConvHullDomain3::vertices, _WlzPlaneDomain::voxel_size, _WlzIVertex2::vtX, _WlzDVertex2::vtX, _WlzIVertex3::vtX, _WlzDVertex3::vtX, _WlzConvHullDomain3::vtxType, _WlzIVertex2::vtY, _WlzDVertex2::vtY, _WlzIVertex3::vtY, _WlzDVertex3::vtY, _WlzIVertex3::vtZ, _WlzDVertex3::vtZ, WLZ_2D_DOMAINOBJ, WLZ_3D_DOMAINOBJ, WLZ_ERR_DEGENERATE, WLZ_ERR_MEM_ALLOC, WLZ_ERR_NONE, WLZ_ERR_UNIMPLEMENTED, WLZ_INTERVALDOMAIN_INTVL, WLZ_PLANEDOMAIN_DOMAIN, WLZ_PLANEDOMAIN_POLYGON, WLZ_VERTEX_D2, WLZ_VERTEX_I3, WLZ_VTX_2_ABS, WLZ_VTX_2_SUB, WlzAssignDomain(), WlzConvexHullFromVtx2(), WlzFreeConvexHullDomain2(), WlzFreeIntervalDomain(), WlzFreeObj(), WlzFreePlaneDomain(), WlzMakeInterval(), WlzMakeIntervalDomain(), WlzMakeMain(), WlzMakePlaneDomain(), and WlzObjToConvexPolygon().

WlzConvHullDomain3* WlzConvexHullFromVtx3	(	WlzVertexType	pType,
		int	nPnt,
		WlzVertexP	pnt,
		WlzErrorNum *	dstErr
	)

Creates a new 3D convex hull domain which encloses the given vertices using a randomized incremental algorithm based on Clarkson and Shor's algorithm: Kenneth L. Clarkson and PeterW. Shor. "Applications of Random Sampling in Computational Geometry, II", Discrete & Computational Geometry 4(1) 1989. This algorithm is also described in a way more suited for implementation in: Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars. "Computational Geometry: Algorithms and Applications", Springer. The algorithm makes use of randomized insertion, lists, queues and a conflict graph of conflicts between vertices and faces. A vertex and face are said to be in conflict when a vertex does not lie behind the face, where behind means in the half-plane defined by the face and the body of the convex hull. In practice the vertex-behind-face test accounts for the almost all the CPU time. The expected run time for this algorithm is O(n log n). On a 3GHz Intel i7 the computation time is a ~10ms for 10^4 vertices randomly distributed over a cube but ~1s for 10^5 vertices. When given a degenerate set of vertices (all on a single plane, all on a single line or all coincident) this function will still compute a 3D convex hull domain but will set the error code to WLZ_ERR_DEGENERATE to indicate this.

Returns: New 3D convex hull domain.

Parameters

pType	Type of vertex given, must be either WLZ_VERTEX_I3 or WLZ_VERTEX_D3.
nPnt	Number of given vertices.
pnt	The given vertices.
dstErr	Destination error pointer, may be NULL. If the volume of the tetrahedron with maximum/minimum z coordinate and minimum x and y coordiantes is zero the erro code will be WLZ_ERR_DEGENERATE.

Referenced by WlzObjToConvexHull().

WlzConvHullDomain2* WlzConvexHullFromVtx2	(	WlzVertexType	pType,
		int	nPnt,
		WlzVertexP	pnt,
		WlzErrorNum *	dstErr
	)

Creates a new 2D convex hull domain which encloses the given vertices using Clarkson's algorithm, see WlzConvHullClarkson2I() and WlzConvHullClarkson2D(). In degenerate cases (less than 3 vertices or all vertices on a single line) a convex hull domain will still be computed but the returned error code will be WLZ_ERR_DEGENERATE.

Returns: New 2D convex hull domain.

Parameters

pType	Type of vertex given, must be either WLZ_VERTEX_I3 or WLZ_VERTEX_D3.
nPnt	Number of given vertices.
pnt	The given vertices.
dstErr	Destination error pointer, may be NULL. If the error code WLZ_ERR_DEGENERATE may be returned, see above.

References AlcFree(), _WlzConvHullDomain2::centroid, _WlzVertexP::d2, _WlzVertex::d2, _WlzVertexP::i2, _WlzVertex::i2, _WlzConvHullDomain2::nVertices, _WlzVertexP::v, _WlzConvHullDomain2::vertices, _WlzIVertex2::vtX, _WlzDVertex2::vtX, _WlzIVertex2::vtY, _WlzDVertex2::vtY, WLZ_ERR_DEGENERATE, WLZ_ERR_NONE, WLZ_ERR_PARAM_DATA, WLZ_ERR_PARAM_NULL, WLZ_ERR_PARAM_TYPE, WLZ_VERTEX_D2, WLZ_VERTEX_I2, WLZ_VTX_2_ADD, WLZ_VTX_2_EQUAL, WLZ_VTX_2_NINT, WLZ_VTX_2_SCALE, WLZ_VTX_2_ZERO, WlzConvHullClarkson2D(), WlzConvHullClarkson2I(), WlzFreeConvexHullDomain2(), and WlzMakeConvexHullDomain2().

Referenced by WlzConvexHullVtxD3ToI3(), and WlzObjToConvexHull().

int WlzConvHullClarkson2I	(	WlzIVertex2 *	vtx,
		int	n,
		int **	dstIdx,
		WlzErrorNum *	dstErr
	)

Computes the convex hull of a given array of 2D integer vertices which is returned as an array of indices into the array of vertices. This index array should be freed using AlcFree(). The vertex array is not changed.

Returns: Number of vertices in the convex hull or zero on error.

Parameters

vtx	Given array of vertices.
n	Number of vertices in the given array.
dstIdx	Destination pointer for array of indices to the convex hull vertices. The convex hull vertices are ordered counter-clockwise.
dstErr	Destination error pointer, may be NULL.

References AlcFree(), AlcMalloc(), WLZ_CONVHULL_CLARKSON_SM_2D, WLZ_ERR_MEM_ALLOC, WLZ_ERR_NONE, WLZ_ERR_PARAM_DATA, and WLZ_ERR_PARAM_NULL.

Referenced by WlzConvexHullFromVtx2().

int WlzConvHullClarkson2D	(	WlzDVertex2 *	vtx,
		int	n,
		int **	dstIdx,
		WlzErrorNum *	dstErr
	)

Computes the convex hull of a given array of 2D double vertices which is returned as an array of indices into the array of vertices. This index array should be freed using AlcFree(). The vertex array is not changed.

Returns: Number of vertices in the convex hull or zero on error.

Parameters

vtx	Given array of vertices.
n	Number of vertices in the given array.
dstIdx	Destination pointer for array of indices to the convex hull vertices. The convex hull vertices are ordered counter-clockwise.
dstErr	Destination error pointer, may be NULL.

References AlcFree(), AlcMalloc(), AlgSort(), _WlzIVertex2::vtX, _WlzDVertex2::vtX, _WlzIVertex2::vtY, _WlzDVertex2::vtY, WLZ_CONVHULL_CLARKSON_SM_2D, WLZ_ERR_MEM_ALLOC, WLZ_ERR_NONE, WLZ_ERR_PARAM_DATA, and WLZ_ERR_PARAM_NULL.

Referenced by WlzConvexHullFromVtx2(), and WlzGeomInterpolatePoly2D().

double WlzMwrAngle	(	WlzObject *	cObj,
		WlzErrorNum *	dstErr
	)

Given a 2D convex hull object, computes the angle of the minimum width rectangle which encloses the convex hull. Where the angle is in radians and with respect to the x-axis. The minimum width rectangle long side must be parallel to an edge of convex hull and all sides must have at least one vertex of convex hull lying within them.

Returns: Angle of the minimum width rectangles longest side with ` respect to the x-axis.

Parameters

cObj	Given object with a 2D convex hull domain.
dstErr	Destination error pointer, may be NULL.

References _WlzDomain::cvh2, _WlzVertexP::d2, _WlzObject::domain, _WlzVertexP::i2, _WlzConvHullDomain2::nVertices, _WlzObject::type, _WlzConvHullDomain2::type, _WlzConvHullDomain2::vertices, _WlzIVertex2::vtX, _WlzDVertex2::vtX, _WlzConvHullDomain2::vtxType, _WlzIVertex2::vtY, _WlzDVertex2::vtY, WLZ_CONV_HULL, WLZ_CONVHULL_DOMAIN_2D, WLZ_ERR_DOMAIN_DATA, WLZ_ERR_DOMAIN_NULL, WLZ_ERR_DOMAIN_TYPE, WLZ_ERR_NONE, WLZ_ERR_OBJECT_NULL, WLZ_ERR_OBJECT_TYPE, WLZ_VERTEX_D2, WLZ_VERTEX_I2, WLZ_VTX_2_DOT, WLZ_VTX_2_LENGTH, WLZ_VTX_2_SET, and WLZ_VTX_2_SUB.

Files

Data Structures

Functions

Detailed Description

Function Documentation