quickhull3D< PT, D > Class Template Reference

Compute the 3D convex hull of points. More...

#include <quickhull3D.h>

Inheritance diagram for quickhull3D< PT, D >:

Collaboration diagram for quickhull3D< PT, D >:

List of all members.

Public Types
typedef halfspaceD3< PT, D >	HS
typedef halfspaceContainer< HS, PT >	HSC
Public Member Functions
	quickhull3D (vector< PT > const &pts_)
	Compute the convex hull of the point pts.
void	reset ()
	Reset the algorithm.
boolc	operator! () const
	Are there any more half-space containers to process?
void	operator++ ()
	Process a half-space container.
Public Attributes
vector< HSC * >	cs
	Stack of half spaces to be processed.
vector< PT > const &	pts
	Global points.
vector< uint >	boundary
	Points on the hull.

---

Detailed Description

template<typename PT, typename D>
class quickhull3D< PT, D >

Compute the 3D convex hull of points.

O(n^2) complexity in time (worst case).

Data structure assumption: pts[0] is not used as 0 index is used to mean that there is no point.

Definition at line 28 of file quickhull3D.h.

---

Member Typedef Documentation

template<typename PT, typename D>

typedef halfspaceD3<PT,D> quickhull3D< PT, D >::HS

Definition at line 32 of file quickhull3D.h.

template<typename PT, typename D>

typedef halfspaceContainer<HS,PT> quickhull3D< PT, D >::HSC

Definition at line 33 of file quickhull3D.h.

---

Constructor & Destructor Documentation

template<typename PT, typename D >

quickhull3D< PT, D >::quickhull3D

(

vector< PT > const &

pts_

)

[inline]

Compute the convex hull of the point pts.

The first element is a dummy value.

Definition at line 234 of file quickhull3D.h.

  : pts(pts_)
{
}

---

Member Function Documentation

template<typename PT, typename D>

boolc quickhull3D< PT, D >::operator!

(

)

const [inline]

Are there any more half-space containers to process?

Definition at line 52 of file quickhull3D.h.

    { return cs.empty()==false; } 

template<typename PT , typename D >

void quickhull3D< PT, D >::operator++

(

)

[inline]

Process a half-space container.

Definition at line 166 of file quickhull3D.h.

References quickhull3D< PT, D >::cs.

{
  assert(cs.size()>0);

  HSC* hc = cs[cs.size()-1];
  cs.pop_back();

  partition(*hc);
  delete hc;
}

template<typename PT , typename D >

void quickhull3D< PT, D >::reset

(

)

[inline]

Reset the algorithm.

Definition at line 178 of file quickhull3D.h.

References quickhull3D< PT, D >::boundary, quickhull3D< PT, D >::cs, halfspaceContainer< HS, PT >::isInsideOrOnBoundary(), and quickhull3D< PT, D >::pts.

Referenced by quickhull3Dtest::keyboard01().

{
  boundary.clear();

  uintc n(pts.size());
  if (n<4)
    return;

  uint x0;
  uint x1;
  uint x2;

  findMinMax(x0,x1,x2);
  boundary.push_back(x0);
  boundary.push_back(x1);
  boundary.push_back(x2);

  assert(x0<n);
  assert(x1<n);
  assert(x2<n);

  list<uint> index;
  for (uint i=1; i<n; ++i)
  {
    if (i==x0)
      continue;
    if (i==x1)
      continue;
    if (i==x2)
      continue;

    index.push_back(i);
  }

  if (cs.empty()==false)
  {
    for ( uint i=0; i<cs.size(); ++i)
      { delete cs[i]; }

    cs.clear();
  } 

  HSC * h1 = 
    new HSC( HS(&pts[0],x0,x1,x2) ,pts );
    //new HSC( HS(pts[x0],pts[x1],pts[x2]) ,pts );
  h1->isInsideOrOnBoundary(index);
  cs.push_back(h1);

  HSC * h2 = 
    new HSC( HS(pts[x2],pts[x1],pts[x0]), pts );
  h2->isInsideOrOnBoundary(index);
  cs.push_back(h2);
}

---

Member Data Documentation

template<typename PT, typename D>

vector< uint > quickhull3D< PT, D >::boundary

Points on the hull.

Definition at line 42 of file quickhull3D.h.

Referenced by quickhull3D< PT, D >::reset().

template<typename PT, typename D>

vector< HSC* > quickhull3D< PT, D >::cs

Stack of half spaces to be processed.

Definition at line 36 of file quickhull3D.h.

Referenced by quickhull3D< pt3, double >::operator!(), quickhull3D< PT, D >::operator++(), and quickhull3D< PT, D >::reset().

template<typename PT, typename D>

vector<PT> const& quickhull3D< PT, D >::pts

Global points.

Definition at line 39 of file quickhull3D.h.

Referenced by quickhull3D< PT, D >::reset().

---

The documentation for this class was generated from the following file:

• quickhull/quickhull3D.h