quickhull2D< PT, D > Class Template Reference

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

#include <quickhull2D.h>

Collaboration diagram for quickhull2D< PT, D >:

List of all members.

Public Member Functions
	quickhull2D (vector< PT > const &_pts)
	Compute the convex hull of the point pts.
Public Attributes
vector< PT > const &	pts
	Global points.
vector< uint >	boundary
	Points on the hull.

---

Detailed Description

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

Compute the 2D convex hull of points.

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

Definition at line 21 of file quickhull2D.h.

---

Constructor & Destructor Documentation

template<typename PT , typename D >

quickhull2D< PT, D >::quickhull2D

(

vector< PT > const &

_pts

)

[inline]

Compute the convex hull of the point pts.

Definition at line 110 of file quickhull2D.h.

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

  : pts(pts_)
{
  uintc n(pts.size());
  if (n<3)
    return;

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

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

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

     index.push_back(i);
  }

  HSC * h1 = 
    new HSC( HS(pts[x0],pts[x1]) ,pts );
  h1->isInsideOrOnBoundary(index);

  HSC * h2 = 
    new HSC( HS(pts[x1],pts[x0]), pts );
  h2->isInsideOrOnBoundary(index);

  cs.push_back(h1);
  cs.push_back(h2);

  process();
}

---

Member Data Documentation

template<typename PT, typename D>

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

Points on the hull.

Definition at line 49 of file quickhull2D.h.

Referenced by quickhull2D< PT, D >::quickhull2D(), quickhull2Drandomized< PT, D >::quickhull2Drandomized(), and quickhull2Dtest::test05().

template<typename PT, typename D>

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

Global points.

Definition at line 46 of file quickhull2D.h.

Referenced by quickhull2D< PT, D >::quickhull2D().

---

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

• quickhull/quickhull2D.h