#include <DGtal/geometry/tools/QuickHull.h>

Public Member Functions
	Facet ()=default
	Facet (const Facet &)=default
	Facet (Facet &&)=default
Facet &	operator= (Facet &&)=default
Facet &	operator= (const Facet &)=default
	Facet (const HalfSpace &aH, Index b)
void	clear ()
void	addPointOn (Index p)
void	display (std::ostream &out) const
void	addNeighbor (Index n)
void	subNeighbor (Index n)
void	swap (Facet &other)
Size	variableMemory () const

Data Fields
HalfSpace	H
	the facet geometry
IndexRange	neighbors
	neighbor facets
IndexRange	outside_set
	outside set, i.e. points above this facet
IndexRange	on_set
	on set, i.e. points on this facet, sorted
Index	below
	index of point that is below this facet

Detailed Description

template<typename TKernel>
struct DGtal::QuickHull< TKernel >::Facet

A facet is d-1 dimensional convex cell lying on the boundary of a full dimensional convex set. Its supporting hyperplane defines an half-space touching and enclosing the convex set.

Definition at line 160 of file QuickHull.h.

Constructor & Destructor Documentation

◆ Facet() [1/4]

template<typename TKernel>

DGtal::QuickHull< TKernel >::Facet::Facet ( )

default

Referenced by Facet(), Facet(), operator=(), operator=(), and swap().

◆ Facet() [2/4]

template<typename TKernel>

DGtal::QuickHull< TKernel >::Facet::Facet ( const Facet & )

default

References Facet().

◆ Facet() [3/4]

template<typename TKernel>

DGtal::QuickHull< TKernel >::Facet::Facet ( Facet && )

default

References Facet().

◆ Facet() [4/4]

template<typename TKernel>

DGtal::QuickHull< TKernel >::Facet::Facet	(	const HalfSpace &	aH,
		Index	b )

inline

Definition at line 172 of file QuickHull.h.

173 : H( aH ), below( b ) {}

DGtal::QuickHull::Facet::below

Index below

index of point that is below this facet

Definition QuickHull.h:165

DGtal::QuickHull::Facet::H

HalfSpace H

the facet geometry

Definition QuickHull.h:161

DGtal::QuickHull

Aim: Implements the quickhull algorithm by Barber et al. barber1996, a famous arbitrary dimensional c...

Definition QuickHull.h:140

References below, and H.

Member Function Documentation

◆ addNeighbor()

template<typename TKernel>

void DGtal::QuickHull< TKernel >::Facet::addNeighbor ( Index n )

inline

Definition at line 201 of file QuickHull.h.

202 {

203 const auto it = std::find( neighbors.cbegin(), neighbors.cend(), n );

204 if ( it == neighbors.cend() ) neighbors.push_back( n );

205 }

DGtal::QuickHull::Facet::neighbors

IndexRange neighbors

neighbor facets

Definition QuickHull.h:162

References neighbors.

◆ addPointOn()

template<typename TKernel>

void DGtal::QuickHull< TKernel >::Facet::addPointOn ( Index p )

inline

Definition at line 183 of file QuickHull.h.

184 {

185 const auto it = std::find( on_set.cbegin(), on_set.cend(), p );

186 if ( it == on_set.cend() ) on_set.push_back( p );

187 }

DGtal::QuickHull::Facet::on_set

IndexRange on_set

on set, i.e. points on this facet, sorted

Definition QuickHull.h:164

References on_set.

◆ clear()

template<typename TKernel>

void DGtal::QuickHull< TKernel >::Facet::clear ( )

inline

Definition at line 175 of file QuickHull.h.

      {
        H = HalfSpace();
        neighbors.clear();
        outside_set.clear();
        on_set.clear();
        below = UNASSIGNED;
      }

References below, H, neighbors, on_set, outside_set, and DGtal::QuickHull< TKernel >::UNASSIGNED.

◆ display()

template<typename TKernel>

void DGtal::QuickHull< TKernel >::Facet::display ( std::ostream & out ) const

inline

Definition at line 188 of file QuickHull.h.

      {
        const auto N = H.internalNormal(); 
        out << "[Facet iN=(" << N[0];
        for ( Dimension i = 1; i < N.dimension; i++ ) out << "," << N[ i ];
        out << ") c=" << H.internalIntercept() << " b=" << below << " n={";
        for ( auto&& n : neighbors ) out << " " << n;
        out << " } #out=" << outside_set.size();
        out << " on={";
        for ( auto&& n : on_set ) out << " " << n;
        out << " }]" << std::endl;
      }

References below, H, neighbors, on_set, and outside_set.

◆ operator=() [1/2]

template<typename TKernel>

Facet & DGtal::QuickHull< TKernel >::Facet::operator= ( const Facet & )

default

References Facet().

◆ operator=() [2/2]

template<typename TKernel>

Facet & DGtal::QuickHull< TKernel >::Facet::operator= ( Facet && )

default

References Facet().

◆ subNeighbor()

template<typename TKernel>

void DGtal::QuickHull< TKernel >::Facet::subNeighbor ( Index n )

inline

Definition at line 206 of file QuickHull.h.

      {
        auto it = std::find( neighbors.begin(), neighbors.end(), n );
        if ( it != neighbors.end() ) {
          std::swap( *it, neighbors.back() );
          neighbors.pop_back();
        }
      }

References neighbors.

◆ swap()

template<typename TKernel>

void DGtal::QuickHull< TKernel >::Facet::swap ( Facet & other )

inline

Definition at line 214 of file QuickHull.h.

      {
        if ( this != &other ) {
          std::swap( H, other.H );
          neighbors.swap  ( other.neighbors );
          outside_set.swap( other.outside_set );
          on_set.swap     ( other.on_set );
          std::swap( below, other.below );
        }
      }

References below, Facet(), H, neighbors, on_set, and outside_set.

◆ variableMemory()

template<typename TKernel>

Size DGtal::QuickHull< TKernel >::Facet::variableMemory ( ) const

inline

Definition at line 224 of file QuickHull.h.

      {
        Size M;
        M += neighbors.capacity()   * sizeof( Index );
        M += outside_set.capacity() * sizeof( Index );
        M += on_set.capacity()      * sizeof( Index );
        return M;
      }