DGtal  1.3.beta
geometry/tools/exampleAlphaShape.cpp

Computation of the alpha shape of the border of a digital shape.

See also
Convex hull and alpha-shape in the plane
#include <iostream>
#include "DGtal/base/Common.h"
#include "DGtal/base/IteratorCirculatorTraits.h"
#include "DGtal/helpers/StdDefs.h"
#include "DGtal/geometry/tools/Hull2DHelpers.h"
#include "DGtal/geometry/tools/PolarPointComparatorBy2x2DetComputer.h"
#include "DGtal/geometry/tools/determinant/AvnaimEtAl2x2DetSignComputer.h"
#include "DGtal/geometry/tools/determinant/InHalfPlaneBySimple3x3Matrix.h"
#include "DGtal/geometry/tools/determinant/InGeneralizedDiskOfGivenRadius.h"
#include "DGtal/shapes/ShapeFactory.h"
#include "DGtal/shapes/Shapes.h"
#include "DGtal/topology/DigitalSetBoundary.h"
#include "DGtal/topology/DigitalSurface.h"
#include "DGtal/graph/DepthFirstVisitor.h"
#include "DGtal/io/boards/Board2D.h"
using namespace std;
using namespace DGtal;
/*
* @brief Procedure that draws on a board a polygon given by a range of vertices.
* @param itb begin iterator
* @param ite end iterator
* @param aBoard any board
* @param isClosed bool equal to 'true' for closed polygon, 'false' otherwise.
* @tparam ForwardIterator at least a readable and forward iterator
* @tparam Board equivalent to Board2D
*/
template <typename ForwardIterator, typename Board>
void drawPolygon(const ForwardIterator& itb, const ForwardIterator& ite,
Board& aBoard, bool isClosed = true)
{
ForwardIterator it = itb;
if (it != ite)
{//for the first point
Point p1 = *it;
Point p = p1;
//display
aBoard << SetMode( p.className(), "Grid" )
<< CustomStyle( p.className()+"/Grid", new CustomPenColor( Color::Red ) )
<< p
<< CustomStyle( p.className()+"/Grid", new CustomPenColor( Color::Black ) );
Point prev = p;
for (++it; it != ite; ++it, prev = p)
{//for all other points
//conversion
p = *it;
//display
aBoard << p;
if (prev != p)
aBoard.drawArrow(prev[0], prev[1], p[0], p[1]);
}
//display the last edge too
if (isClosed)
{
if (prev != p1)
aBoard.drawArrow(prev[0], prev[1], p1[0], p1[1]);
}
}
}
void alphaShape()
{
//Digitization of a disk of radius 8
Z2i::Domain domain(ball.getLowerBound(), ball.getUpperBound());
Z2i::DigitalSet digitalSet(domain);
//Contour of the digital set
Z2i::KSpace kspace;
kspace.init(domain.lowerBound()-Z2i::Point(1,1), domain.upperBound()+Z2i::Point(1,1), true);
typedef DigitalSetBoundary<Z2i::KSpace, Z2i::DigitalSet> DigitalSurfaceContainer;
typedef DigitalSurface<DigitalSurfaceContainer> CustomDigitalSurface;
DigitalSurfaceContainer digitalSurfaceContainer( kspace, digitalSet );
CustomDigitalSurface digitalSurface( digitalSurfaceContainer );
//Grid curve
Z2i::Curve gridCurve;
CustomVisitor visitor( digitalSurface, *digitalSurface.begin() );
while ( ! visitor.finished() )
{
gridCurve.pushBack( visitor.current().first );
visitor.expand();
}
//Point set defined as the set of (not duplicated) inner points
typedef Z2i::Curve::InnerPointsRange PointRange;
PointRange pointsRange = gridCurve.getInnerPointsRange();
vector<Z2i::Point> border;
unique_copy( pointsRange.begin(), pointsRange.end(), back_inserter( border ) );
//namespace for hull functions
using namespace functions::Hull2D;
{ //alpha = 0
trace.info() << " alpha == 0 " << endl;
vector<Z2i::Point> res;
Functor functor(true, 1, 0); //alpha = 0; 1/alpha -> +inf
Predicate predicate( functor );
closedGrahamScanFromAnyPoint( border.begin(), border.end(), back_inserter( res ), predicate );
//display
Board2D board;
drawPolygon( res.begin(), res.end(), board );
board.saveSVG( "AlphaShape0.svg" );
#ifdef WITH_CAIRO
board.saveCairo("AlphaShape0.png", Board2D::CairoPNG);
#endif
}
{ //alpha = 0
trace.info() << " alpha == 0 " << endl;
vector<Z2i::Point> res;
//comparator and functor
Functor functor;
Predicate predicate( functor );
closedGrahamScanFromAnyPoint( border.begin(), border.end(), back_inserter( res ), predicate );
//display
Board2D board;
drawPolygon( res.begin(), res.end(), board );
board.saveSVG( "AlphaShape0bis.svg" );
#ifdef WITH_CAIRO
board.saveCairo("AlphaShape0bis.png", Board2D::CairoPNG);
#endif
}
//negative alpha shape
{ //alpha = -1
trace.info() << " alpha == -1 " << endl;
vector<Z2i::Point> res;
Functor functor(false, 1, 1); //1/alpha = -sqrt(1/1) = -1
Predicate predicate( functor );
closedGrahamScanFromAnyPoint( border.begin(), border.end(), back_inserter( res ), predicate );
//display
Board2D board;
drawPolygon( res.begin(), res.end(), board );
board.saveSVG( "AlphaShapeM1.svg" );
#ifdef WITH_CAIRO
board.saveCairo("AlphaShapeM1.png", Board2D::CairoPNG);
#endif
}
{ //alpha = -sqrt(5)
trace.info() << " alpha == -sqrt(5) " << endl;
vector<Z2i::Point> res;
Functor functor(false, 5, 1); //1/alpha = -sqrt(5)
Predicate predicate( functor );
closedGrahamScanFromAnyPoint( border.begin(), border.end(), back_inserter( res ), predicate );
//display
Board2D board;
drawPolygon( res.begin(), res.end(), board );
board.saveSVG( "AlphaShapeMSqrt5.svg" );
#ifdef WITH_CAIRO
board.saveCairo("AlphaShapeMSqrt5.png", Board2D::CairoPNG);
#endif
}
{ //alpha = -5
trace.info() << " alpha == -5 " << endl;
vector<Z2i::Point> res;
Functor functor(false, 25, 1); //1/alpha = -sqrt(25/1) = -5
Predicate predicate( functor );
closedGrahamScanFromAnyPoint( border.begin(), border.end(), back_inserter( res ), predicate );
//display
Board2D board;
drawPolygon( res.begin(), res.end(), board );
board.saveSVG( "AlphaShapeM5.svg" );
#ifdef WITH_CAIRO
board.saveCairo("AlphaShapeM5.png", Board2D::CairoPNG);
#endif
}
//positive alpha shape
{
trace.info() << " alpha == 8 " << endl;
vector<Z2i::Point> res;
Functor functor(true, 64, 1); //1/alpha = sqrt(64/1) = 8
Predicate predicate( functor );
closedGrahamScanFromAnyPoint( border.begin(), border.end(), back_inserter( res ), predicate );
//display
Board2D board;
drawPolygon( res.begin(), res.end(), board );
board.saveSVG( "AlphaShapeP8.svg" );
#ifdef WITH_CAIRO
board.saveCairo("AlphaShapeP8.png", Board2D::CairoPNG);
#endif
}
//positive alpha shape
{
trace.info() << " alpha == 9 " << endl;
vector<Z2i::Point> res;
Functor functor(true, 81, 1); //1/alpha = sqrt(81/1) = 9
Predicate predicate( functor );
closedGrahamScanFromAnyPoint( border.begin(), border.end(), back_inserter( res ), predicate );
//display
Board2D board;
drawPolygon( res.begin(), res.end(), board );
board.saveSVG( "AlphaShapeP9.svg" );
#ifdef WITH_CAIRO
board.saveCairo("AlphaShapeP9.png", Board2D::CairoPNG);
#endif
}
}
int main( int argc, char** argv )
{
trace.beginBlock ( "Example exampleAlphaShape" );
trace.info() << "Args:";
for ( int i = 0; i < argc; ++i )
trace.info() << " " << argv[ i ];
trace.info() << endl;
return 0;
}
// //
DGtal::HyperRectDomain< Space >
DGtal::Trace::endBlock
double endBlock()
DGtal::ConstRangeAdapter
Aim: model of CConstBidirectionalRange that adapts any range of elements bounded by two iterators [it...
Definition: ConstRangeAdapter.h:86
drawPolygon
void drawPolygon(const ForwardIterator &itb, const ForwardIterator &ite, Board &aBoard, bool isClosed=true)
Definition: exampleAlphaShape.cpp:79
DGtal::DigitalSurface
Aim: Represents a set of n-1-cells in a nD space, together with adjacency relation between these cell...
Definition: DigitalSurface.h:139
DGtal::HyperRectDomain::upperBound
const Point & upperBound() const
DGtal::KhalimskySpaceND::init
bool init(const Point &lower, const Point &upper, bool isClosed)
Specifies the upper and lower bounds for the maximal cells in this space.
LibBoard::Board::saveCairo
void saveCairo(const char *filename, CairoType type=CairoPNG, PageSize size=Board::BoundingBox, double margin=10.0) const
Definition: Board.cpp:1139
DGtal::trace
Trace trace
Definition: Common.h:154
DGtal::DigitalSetBoundary
Aim: A model of CDigitalSurfaceContainer which defines the digital surface as the boundary of a given...
Definition: DigitalSetBoundary.h:69
alphaShape
void alphaShape()
Definition: exampleAlphaShape.cpp:123
DGtal::GridCurve
Aim: describes, in a cellular space of dimension n, a closed or open sequence of signed d-cells (or d...
Definition: GridCurve.h:172
DGtal::Trace::beginBlock
void beginBlock(const std::string &keyword="")
Functor
InHalfPlaneBySimple3x3Matrix< Point, double > Functor
Definition: testConvexHull2DReverse.cpp:51
DGtal::functions::Hull2D::closedGrahamScanFromAnyPoint
void closedGrahamScanFromAnyPoint(const ForwardIterator &itb, const ForwardIterator &ite, OutputIterator res, const Predicate &aPredicate)
Procedure that retrieves the vertices of the convex hull of a weakly externally visible polygon (WEVP...
DGtal::InGeneralizedDiskOfGivenRadius
Aim: This class implements an orientation functor that provides a way to determine the position of ...
Definition: InGeneralizedDiskOfGivenRadius.h:126
DGtal::GridCurve::pushBack
void pushBack(const SCell &aSCell)
DGtal::Ball2D
Aim: Model of the concept StarShaped represents any circle in the plane.
Definition: Ball2D.h:60
DGtal::CustomStyle
Definition: Board2D.h:217
DGtal::Trace::info
std::ostream & info()
boost_concepts::ForwardTraversalConcept
Go to http://www.boost.org/doc/libs/1_52_0/libs/iterator/doc/ForwardTraversal.html.
Definition: BoostConcepts.dox:47
DGtal
DGtal is the top-level namespace which contains all DGtal functions and types.
DGtal::GridCurve::getInnerPointsRange
InnerPointsRange getInnerPointsRange() const
Definition: GridCurve.h:462
DGtal::InHalfPlaneBySimple3x3Matrix
Aim: Class that implements an orientation functor, ie. it provides a way to compute the orientation o...
Definition: InHalfPlaneBySimple3x3Matrix.h:91
DGtal::AvnaimEtAl2x2DetSignComputer
Aim: Class that provides a way of computing the sign of the determinant of a 2x2 matrix from its four...
Definition: AvnaimEtAl2x2DetSignComputer.h:144
LibBoard::Board::saveSVG
void saveSVG(const char *filename, PageSize size=Board::BoundingBox, double margin=10.0) const
Definition: Board.cpp:1012
main
int main(int argc, char **argv)
Definition: testArithmeticDSS-benchmark.cpp:147
DGtal::Board2D
Aim: This class specializes a 'Board' class so as to display DGtal objects more naturally (with <<)....
Definition: Board2D.h:70
DGtal::Shapes
Aim: A utility class for constructing different shapes (balls, diamonds, and others).
Definition: DGtal/shapes/Shapes.h:71
domain
Domain domain
Definition: testProjection.cpp:88
DGtal::PointVector< dim, Integer >
DGtal::PredicateFromOrientationFunctor2
Aim: Small adapter to models of COrientationFunctor2. It is a model of concepts::CPointPredicate....
Definition: PredicateFromOrientationFunctor2.h:81
DGtal::DepthFirstVisitor
Aim: This class is useful to perform a depth-first exploration of a graph given a starting point or s...
Definition: DepthFirstVisitor.h:95
DGtal::SetMode
Modifier class in a Board2D stream. Useful to choose your own mode for a given class....
Definition: Board2D.h:247
boost_concepts::ReadableIteratorConcept
Go to http://www.boost.org/doc/libs/1_52_0/libs/iterator/doc/ReadableIterator.html.
Definition: BoostConcepts.dox:29
Point
MyPointD Point
Definition: testClone2.cpp:383
DGtal::CustomPenColor
Custom style class redefining the pen color. You may use Board2D::Color::None for transparent color.
Definition: Board2D.h:312
DGtal::IteratorCirculatorTraits::Value
IC::value_type Value
Definition: IteratorCirculatorTraits.h:303
DGtal::HyperRectDomain::lowerBound
const Point & lowerBound() const
DGtal::DigitalSetByAssociativeContainer
Aim: A wrapper class around a STL associative container for storing sets of digital points within som...
Definition: DigitalSetByAssociativeContainer.h:89
DGtal::KhalimskySpaceND
Aim: This class is a model of CCellularGridSpaceND. It represents the cubical grid as a cell complex,...
Definition: KhalimskySpaceND.h:64