exampleConvexHull2D.cpp File Reference

#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/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"

Include dependency graph for exampleConvexHull2D.cpp:

Go to the source code of this file.

Functions
template<typename ForwardIterator , typename Board >
void	drawPolygon (const ForwardIterator &itb, const ForwardIterator &ite, Board &aBoard, bool isClosed=true)
void	convexHull ()
int	main (int argc, char **argv)

Detailed Description

This program is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation, either version 3 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, see http://www.gnu.org/licenses/.

Author

Tristan Roussillon (trist.nosp@m.an.r.nosp@m.oussi.nosp@m.llon.nosp@m.@liri.nosp@m.s.cn.nosp@m.rs.fr ) Laboratoire d'InfoRmatique en Image et Systèmes d'information - LIRIS (CNRS, UMR 5205), CNRS, France

Date

2013/12/17

An example file named exampleConvexHull2D.

This file is part of the DGtal library.

Definition in file exampleConvexHull2D.cpp.

Function Documentation

convexHull()

void convexHull

(

)

Algorithms that computes the convex hull of a point set

[Hull2D-Namespace]

[Hull2D-Namespace]

[Hull2D-Functor]

[Hull2D-Functor]

[Hull2D-StrictPredicateCCW]

[Hull2D-StrictPredicateCCW]

[Hull2D-AndrewAlgo]

[Hull2D-AndrewAlgo] [Hull2D-Caliper-computeBasic]

[Hull2D-Caliper-computeBasic]

[Hull2D-Caliper-computeAnti]

[Hull2D-Caliper-computeAnti]

[Hull2D-Caliper-display]

[Hull2D-Caliper-display]

[Hull2D-LargePredicateCCW]

[Hull2D-LargePredicateCCW]

[Hull2D-StrictPredicateCW]

[Hull2D-StrictPredicateCW]

[Hull2D-GrahamAlgo]

[Hull2D-GrahamAlgo]

[Hull2D-OnLineMelkmanAlgo]

[Hull2D-OnLineMelkmanAlgo]

[Hull2D-OffLineMelkmanAlgo]

[Hull2D-OffLineMelkmanAlgo]

Examples

geometry/tools/exampleConvexHull2D.cpp.

Definition at line 122 of file exampleConvexHull2D.cpp.

{
  //Digitization of a disk of radius 6
  Ball2D<Z2i::Space> ball(Z2i::Point(0,0), 6);
  Z2i::Domain domain(ball.getLowerBound(), ball.getUpperBound());
  Z2i::DigitalSet pointSet(domain);   
  Shapes<Z2i::Domain>::euclideanShaper(pointSet, ball);
 
  using namespace functions::Hull2D; 
 
  typedef InHalfPlaneBySimple3x3Matrix<Z2i::Point, DGtal::int64_t> Functor;  
  Functor functor; 
 
  { //convex hull in counter-clockwise order
    vector<Z2i::Point> res; 
 
    typedef PredicateFromOrientationFunctor2<Functor, false, false> StrictPredicate; 
    StrictPredicate predicate( functor ); 
    //according to the last two template arguments, neither strictly negative values, nor zeros are accepted: 
    //the predicate returns 'true' only for strictly positive values returned by the underlying functor. 
 
    andrewConvexHullAlgorithm( pointSet.begin(), pointSet.end(), back_inserter( res ), predicate );   
    double th = DGtal::functions::Hull2D::computeHullThickness(res.begin(), res.end(), DGtal::functions::Hull2D::HorizontalVerticalThickness);
 
    Z2i::Point antipodalP, antipodalQ, antipodalS;
    th = DGtal::functions::Hull2D::computeHullThickness(res.begin(), res.end(), DGtal::functions::Hull2D::HorizontalVerticalThickness, antipodalP, antipodalQ, antipodalS);
 
    
    trace.info() <<" ConvexHull HV thickness: " << th << std::endl;
    //display
    Board2D board;
    drawPolygon( res.begin(), res.end(), board ); 
    board.setPenColor(DGtal::Color::Red);
    board.drawCircle( antipodalS[0], antipodalS[1], 0.2) ;
    board.setPenColor(DGtal::Color::Blue);
    board.drawCircle(antipodalP[0], antipodalP[1], 0.2);
    board.drawCircle(antipodalQ[0], antipodalQ[1], 0.2);
    board.drawLine(antipodalP[0], antipodalP[1], antipodalQ[0], antipodalQ[1]);
    
    board.saveSVG( "ConvexHullCCW.svg" );  
#ifdef WITH_CAIRO
    board.saveCairo("ConvexHullCCW.png", Board2D::CairoPNG);
#endif
  }
 
  { //convex hull in counter-clockwise order with all the points lying on the edges
    vector<Z2i::Point> res; 
 
    typedef PredicateFromOrientationFunctor2<Functor, false, true> LargePredicate; 
    LargePredicate predicate( functor ); 
    //according to the last template argument, zeros are accepted so that  
    //the predicate returns 'true' for all the positive values returned by the underlying functor. 
 
    //andrew algorithm
    andrewConvexHullAlgorithm( pointSet.begin(), pointSet.end(), back_inserter( res ), predicate );   
 
    //display
    Board2D board;
    drawPolygon( res.begin(), res.end(), board ); 
    board.saveSVG( "ConvexHullCCWWithPointsOnEdges.svg" );  
#ifdef WITH_CAIRO
    board.saveCairo("ConvexHullCCWWithPointsOnEdges.png", Board2D::CairoPNG);
#endif
 
  }
 
  { //convex hull in clockwise order
    vector<Z2i::Point> res; 
 
    typedef PredicateFromOrientationFunctor2<Functor, true, false> StrictPredicate; 
    StrictPredicate predicate( functor );
    //according to the last two argument template, 
    //the predicate returns 'true' only for strictly negative values returned by the underlying functor. 
 
    //andrew algorithm
    andrewConvexHullAlgorithm( pointSet.begin(), pointSet.end(), back_inserter( res ), predicate );   
 
    //display
    Board2D board;
    drawPolygon( res.begin(), res.end(), board ); 
    board.saveSVG( "ConvexHullCW.svg" );  
#ifdef WITH_CAIRO
    board.saveCairo("ConvexHullCW.png", Board2D::CairoPNG);
#endif
  }
 
  { //convex hull in counter-clockwise order
    vector<Z2i::Point> res; 
 
    //geometric predicate
    typedef PredicateFromOrientationFunctor2<Functor, false, false> StrictPredicate; 
    StrictPredicate predicate( functor ); 
 
    grahamConvexHullAlgorithm( pointSet.begin(), pointSet.end(), back_inserter( res ), predicate ); 
 
    //display
    Board2D board;
    drawPolygon( res.begin(), res.end(), board ); 
    board.saveSVG( "ConvexHullCCWbis.svg" );  
#ifdef WITH_CAIRO
    board.saveCairo("ConvexHullCCWbis.png", Board2D::CairoPNG);
#endif
  }
 
  { //convex hull of a simple polygonal line that is not weakly externally visible
    vector<Z2i::Point> polygonalLine;
    polygonalLine.push_back(Z2i::Point(0,0)); 
    polygonalLine.push_back(Z2i::Point(0,4)); 
    polygonalLine.push_back(Z2i::Point(1,4)); 
    polygonalLine.push_back(Z2i::Point(1,1)); 
    polygonalLine.push_back(Z2i::Point(3,1)); 
    polygonalLine.push_back(Z2i::Point(2,2)); 
    polygonalLine.push_back(Z2i::Point(3,4)); 
    polygonalLine.push_back(Z2i::Point(4,4)); 
    polygonalLine.push_back(Z2i::Point(4,0)); 
 
    vector<Z2i::Point> resGraham, res; 
 
    typedef PredicateFromOrientationFunctor2<Functor, false, false> StrictPredicate; 
    StrictPredicate predicate( functor ); 
    closedGrahamScanFromAnyPoint( polygonalLine.begin(), polygonalLine.end(), back_inserter( resGraham ), predicate );   
 
    DGtal::MelkmanConvexHull<Z2i::Point, Functor> ch( functor ); 
    for (std::vector<Z2i::Point>::const_iterator 
           it = polygonalLine.begin(), 
           itEnd = polygonalLine.end(); 
         it != itEnd; ++it)
      ch.add( *it ); 
 
    melkmanConvexHullAlgorithm( polygonalLine.begin(), polygonalLine.end(), back_inserter( res ), functor );   
 
    //display
    Board2D board;
    drawPolygon( polygonalLine.begin(), polygonalLine.end(), board, true ); 
    board.saveSVG( "SimplePolygonalLine.svg" );  
#ifdef WITH_CAIRO
    board.saveCairo("SimplePolygonalLine.png", Board2D::CairoPNG);
#endif
    board.clear(); 
    drawPolygon( resGraham.begin(), resGraham.end(), board ); 
    board.saveSVG( "SimplePolygonalLineGraham.svg" );  
#ifdef WITH_CAIRO
    board.saveCairo("SimplePolygonalLineGraham.png", Board2D::CairoPNG);
#endif
    board.clear(); 
    drawPolygon( res.begin(), res.end(), board ); 
    board.saveSVG( "SimplePolygonalLineMelkman.svg" );  
#ifdef WITH_CAIRO
    board.saveCairo("SimplePolygonalLineMelkman.png", Board2D::CairoPNG);
#endif
    board.clear(); 
    drawPolygon( ch.begin(), ch.end(), board ); 
    board.saveSVG( "SimplePolygonalLineMelkman2.svg" );  
#ifdef WITH_CAIRO
    board.saveCairo("SimplePolygonalLineMelkman2.png", Board2D::CairoPNG);
#endif
  }
 
  { //order of the points for andrew algorithm
    vector<Z2i::Point> res; 
    std::copy( pointSet.begin(), pointSet.end(), back_inserter( res ) ); 
 
    std::sort( res.begin(), res.end() ); 
 
    //display
    Board2D board;
    drawPolygon( res.begin(), res.end(), board, false ); 
    board.saveSVG( "AndrewWEVP.svg" );  
#ifdef WITH_CAIRO
    board.saveCairo("AndrewWEVP.png", Board2D::CairoPNG);
#endif
  }
 
  { //order of the points for graham algorithm
    vector<Z2i::Point> res; 
    std::copy( pointSet.begin(), pointSet.end(), back_inserter( res ) ); 
 
    //find an extremal point
    //NB: we choose the point of greatest x-coordinate
    //so that the sort step (by a polar comparator) 
    //returns a weakly externally visible polygon
    std::vector<Z2i::Point>::iterator itMax 
      = std::max_element( res.begin(), res.end() ); 
 
    //sort around this point with a polar comparator
    functors::PolarPointComparatorBy2x2DetComputer<Z2i::Point> comparator;  
    comparator.setPole( *itMax );
    std::sort( res.begin(), res.end(), comparator ); 
 
    //display
    Board2D board;
    drawPolygon( res.begin(), res.end(), board, false ); 
    board.saveSVG( "GrahamWEVP.svg" );  
#ifdef WITH_CAIRO
    board.saveCairo("GrahamWEVP.png", Board2D::CairoPNG);
#endif
  }
 
 
}

References DGtal::DigitalSetByAssociativeContainer< TDomain, TContainer >::begin(), DGtal::Color::Blue, ch, LibBoard::Board::clear(), DGtal::functions::Hull2D::computeHullThickness(), domain, LibBoard::Board::drawCircle(), LibBoard::Board::drawLine(), drawPolygon(), DGtal::DigitalSetByAssociativeContainer< TDomain, TContainer >::end(), DGtal::Shapes< TDomain >::euclideanShaper(), DGtal::Ball2D< TSpace >::getLowerBound(), DGtal::Ball2D< TSpace >::getUpperBound(), DGtal::functions::Hull2D::HorizontalVerticalThickness, DGtal::Trace::info(), DGtal::Color::Red, LibBoard::Board::saveCairo(), LibBoard::Board::saveSVG(), LibBoard::Board::setPenColor(), DGtal::functors::PolarPointComparatorBy2x2DetComputer< TPoint, TDetComputer >::setPole(), and DGtal::trace.

Referenced by main().

drawPolygon()

template<typename ForwardIterator , typename Board >

void drawPolygon	(	const ForwardIterator &	itb,
		const ForwardIterator &	ite,
		Board &	aBoard,
		bool	isClosed = true )

Definition at line 79 of file exampleConvexHull2D.cpp.

{
  BOOST_CONCEPT_ASSERT(( boost_concepts::ForwardTraversalConcept<ForwardIterator> )); 
  BOOST_CONCEPT_ASSERT(( boost_concepts::ReadableIteratorConcept<ForwardIterator> )); 
  typedef typename IteratorCirculatorTraits<ForwardIterator>::Value Point; 
 
  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]); 
        }
    }
}

References DGtal::Color::Black, and DGtal::Color::Red.

Referenced by convexHull().

main()

int main	(	int	argc,
		char **	argv )

Main procedure. Draw the convex hull of a point set coming from the digitization of a disk.

Parameters

argc	number of arguments
argv	array of arguments

Definition at line 354 of file exampleConvexHull2D.cpp.

{
  trace.beginBlock ( "Example exampleConvexHull2D" );
  trace.info() << "Args:";
  for ( int i = 0; i < argc; ++i )
    trace.info() << " " << argv[ i ];
  trace.info() << endl;
 
  convexHull(); 
 
  trace.endBlock(); 
 
  return 0;
}

References DGtal::Trace::beginBlock(), convexHull(), DGtal::Trace::endBlock(), DGtal::Trace::info(), and DGtal::trace.