Functions for computing 3D convex hull domains. More...

Data Structures
struct	_WlzConvHullArc
	A conflict arc connecting a face and a vertex these form circular doubly linked lists for the faces and vertices. Typedef: WlzConvHullArc. More...

struct	_WlzConvHullVtx
	A vertex of the convex hull for use in a convex hull workspace. Typedef: WlzConvHullVtx. More...

struct	_WlzConvHullFce
	A face of the convex hull for use in a convex hull workspace. Typedef: WlzConvHullFce. More...

struct	_WlzConvHullArcPool
	A pool of conflict arcs. Typedef: WlzConvHullArcPool. More...

struct	_WlzConvHullFcePool
	A pool of faces. Typedef: WlzConvHullFcePool. More...

struct	_WlzConvHullVtxPool
	A pool of vertices. Typedef: WlzConvHullVtxPool. More...

struct	_WlzConvHullHorEdg
	A horizon edge as seen from an external vertex. Typedef: WlzConvHullHorEdg. More...

struct	_WlzConvHullWSp3
	A workspace for computing the 3D convex hull of vertices with integral coordinates. Typedef: WlzConvHullWSp3. More...

Macros
#define	WLZ_CONVHULL_EPS (1.0e-06)
	Tollerance value for lengths. More...

Typedefs
typedef struct _WlzConvHullArc	WlzConvHullArc

typedef struct _WlzConvHullVtx	WlzConvHullVtx

typedef struct _WlzConvHullFce	WlzConvHullFce

typedef struct _WlzConvHullArcPool	WlzConvHullArcPool

typedef struct _WlzConvHullFcePool	WlzConvHullFcePool

typedef struct _WlzConvHullVtxPool	WlzConvHullVtxPool

typedef struct _WlzConvHullHorEdg	WlzConvHullHorEdg

typedef struct _WlzConvHullWSp3	WlzConvHullWSp3

Functions
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...

Detailed Description

Functions for computing 3D convex hull domains.

Author: Bill Hill

Date: April 2014

Version

Id: 81d126ec88fdb8d5d588dfaaddd1d22c2024a797

: Address: MRC Human Genetics Unit, MRC Institute of Genetics and Molecular Medicine, University of Edinburgh, Western General Hospital, Edinburgh, EH4 2XU, UK.

: Copyright (C), [2014], The University Court of the University of Edinburgh, Old College, Edinburgh, UK.

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.