Woolz Image Processing  Version 1.8.3
WlzConvexHull3D.c File Reference

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

WlzConvHullDomain3WlzConvexHullFromVtx3 (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.

Macro Definition Documentation

◆ WLZ_CONVHULL_EPS

#define WLZ_CONVHULL_EPS   (1.0e-06)

Tollerance value for lengths.

Referenced by WlzConvexHullFromVtx3().

Typedef Documentation

◆ WlzConvHullArc

◆ WlzConvHullVtx

◆ WlzConvHullFce

◆ WlzConvHullArcPool

◆ WlzConvHullFcePool

◆ WlzConvHullVtxPool

◆ WlzConvHullHorEdg

◆ WlzConvHullWSp3