DGtal  0.9.2
exampleConvexHull2D.cpp
1
30 #include <iostream>
32 #include "DGtal/base/Common.h"
33 #include "DGtal/base/IteratorCirculatorTraits.h"
34 #include "DGtal/helpers/StdDefs.h"
35
37 #include "DGtal/geometry/tools/Hull2DHelpers.h"
39 #include "DGtal/geometry/tools/PolarPointComparatorBy2x2DetComputer.h"
40 #include "DGtal/geometry/tools/determinant/AvnaimEtAl2x2DetSignComputer.h"
41 #include "DGtal/geometry/tools/determinant/InHalfPlaneBySimple3x3Matrix.h"
42
43 #include "DGtal/shapes/ShapeFactory.h"
44 #include "DGtal/shapes/Shapes.h"
45
46 #include "DGtal/topology/DigitalSetBoundary.h"
47 #include "DGtal/topology/DigitalSurface.h"
48 #include "DGtal/graph/DepthFirstVisitor.h"
49
50 #include "DGtal/io/boards/Board2D.h"
52
53 using namespace std;
54 using namespace DGtal;
55
57 /*
58  * @brief Procedure that draws on a board a polygon given by a range of vertices.
59  * @param itb begin iterator
60  * @param ite end iterator
61  * @param aBoard any board
62  * @param isClosed bool equal to 'true' for closed polygon, 'false' otherwise.
63  * @tparam ForwardIterator at least a readable and forward iterator
64  * @tparam Board equivalent to Board2D
65  */
66 template <typename ForwardIterator, typename Board>
67 void drawPolygon(const ForwardIterator& itb, const ForwardIterator& ite,
68  Board& aBoard, bool isClosed = true)
69 {
73
74  ForwardIterator it = itb;
75  if (it != ite)
76  {//for the first point
77  Point p1 = *it;
78  Point p = p1;
79  //display
80  aBoard << SetMode( p.className(), "Grid" )
81  << CustomStyle( p.className()+"/Grid", new CustomPenColor( Color::Red ) )
82  << p
83  << CustomStyle( p.className()+"/Grid", new CustomPenColor( Color::Black ) );
84
85  Point prev = p;
86  for (++it; it != ite; ++it, prev = p)
87  {//for all other points
88  //conversion
89  p = *it;
90  //display
91  aBoard << p;
92  if (prev != p)
93  aBoard.drawArrow(prev[0], prev[1], p[0], p[1]);
94  }
95
96  //display the last edge too
97  if (isClosed)
98  {
99  if (prev != p1)
100  aBoard.drawArrow(prev[0], prev[1], p1[0], p1[1]);
101  }
102  }
103 }
104
105
110 void convexHull()
111 {
112  //Digitization of a disk of radius 6
113  Ball2D<Z2i::Space> ball(Z2i::Point(0,0), 6);
114  Z2i::Domain domain(ball.getLowerBound(), ball.getUpperBound());
115  Z2i::DigitalSet pointSet(domain);
116  Shapes<Z2i::Domain>::euclideanShaper(pointSet, ball);
117
119  using namespace functions::Hull2D;
121
124  Functor functor;
126
127  { //convex hull in counter-clockwise order
128  vector<Z2i::Point> res;
129
132  StrictPredicate predicate( functor );
134  //according to the last two template arguments, neither strictly negative values, nor zeros are accepted:
135  //the predicate returns 'true' only for strictly positive values returned by the underlying functor.
136
138  andrewConvexHullAlgorithm( pointSet.begin(), pointSet.end(), back_inserter( res ), predicate );
143
145  Z2i::Point antipodalP, antipodalQ, antipodalS;
146  th = DGtal::functions::Hull2D::computeHullThickness(res.begin(), res.end(), DGtal::functions::Hull2D::HorizontalVerticalThickness, antipodalP, antipodalQ, antipodalS);
148
149
150  trace.info() <<" ConvexHull HV thickness: " << th << std::endl;
151  //display
152  Board2D board;
153  drawPolygon( res.begin(), res.end(), board );
156  board.drawCircle( antipodalS[0], antipodalS[1], 0.2) ;
158  board.drawCircle(antipodalP[0], antipodalP[1], 0.2);
159  board.drawCircle(antipodalQ[0], antipodalQ[1], 0.2);
160  board.drawLine(antipodalP[0], antipodalP[1], antipodalQ[0], antipodalQ[1]);
162
163  board.saveSVG( "ConvexHullCCW.svg" );
164 #ifdef WITH_CAIRO
165  board.saveCairo("ConvexHullCCW.png", Board2D::CairoPNG);
166 #endif
167  }
168
169  { //convex hull in counter-clockwise order with all the points lying on the edges
170  vector<Z2i::Point> res;
171
174  LargePredicate predicate( functor );
176  //according to the last template argument, zeros are accepted so that
177  //the predicate returns 'true' for all the positive values returned by the underlying functor.
178
179  //andrew algorithm
180  andrewConvexHullAlgorithm( pointSet.begin(), pointSet.end(), back_inserter( res ), predicate );
181
182  //display
183  Board2D board;
184  drawPolygon( res.begin(), res.end(), board );
185  board.saveSVG( "ConvexHullCCWWithPointsOnEdges.svg" );
186 #ifdef WITH_CAIRO
187  board.saveCairo("ConvexHullCCWWithPointsOnEdges.png", Board2D::CairoPNG);
188 #endif
189
190  }
191
192  { //convex hull in clockwise order
193  vector<Z2i::Point> res;
194
197  StrictPredicate predicate( functor );
199  //according to the last two argument template,
200  //the predicate returns 'true' only for strictly negative values returned by the underlying functor.
201
202  //andrew algorithm
203  andrewConvexHullAlgorithm( pointSet.begin(), pointSet.end(), back_inserter( res ), predicate );
204
205  //display
206  Board2D board;
207  drawPolygon( res.begin(), res.end(), board );
208  board.saveSVG( "ConvexHullCW.svg" );
209 #ifdef WITH_CAIRO
210  board.saveCairo("ConvexHullCW.png", Board2D::CairoPNG);
211 #endif
212  }
213
214  { //convex hull in counter-clockwise order
215  vector<Z2i::Point> res;
216
217  //geometric predicate
219  StrictPredicate predicate( functor );
220
222  grahamConvexHullAlgorithm( pointSet.begin(), pointSet.end(), back_inserter( res ), predicate );
224
225  //display
226  Board2D board;
227  drawPolygon( res.begin(), res.end(), board );
228  board.saveSVG( "ConvexHullCCWbis.svg" );
229 #ifdef WITH_CAIRO
230  board.saveCairo("ConvexHullCCWbis.png", Board2D::CairoPNG);
231 #endif
232  }
233
234  { //convex hull of a simple polygonal line that is not weakly externally visible
235  vector<Z2i::Point> polygonalLine;
236  polygonalLine.push_back(Z2i::Point(0,0));
237  polygonalLine.push_back(Z2i::Point(0,4));
238  polygonalLine.push_back(Z2i::Point(1,4));
239  polygonalLine.push_back(Z2i::Point(1,1));
240  polygonalLine.push_back(Z2i::Point(3,1));
241  polygonalLine.push_back(Z2i::Point(2,2));
242  polygonalLine.push_back(Z2i::Point(3,4));
243  polygonalLine.push_back(Z2i::Point(4,4));
244  polygonalLine.push_back(Z2i::Point(4,0));
245
246  vector<Z2i::Point> resGraham, res;
247
249  StrictPredicate predicate( functor );
250  closedGrahamScanFromAnyPoint( polygonalLine.begin(), polygonalLine.end(), back_inserter( resGraham ), predicate );
251
254  for (std::vector<Z2i::Point>::const_iterator
255  it = polygonalLine.begin(),
256  itEnd = polygonalLine.end();
257  it != itEnd; ++it)
260
262  melkmanConvexHullAlgorithm( polygonalLine.begin(), polygonalLine.end(), back_inserter( res ), functor );
264
265  //display
266  Board2D board;
267  drawPolygon( polygonalLine.begin(), polygonalLine.end(), board, true );
268  board.saveSVG( "SimplePolygonalLine.svg" );
269 #ifdef WITH_CAIRO
270  board.saveCairo("SimplePolygonalLine.png", Board2D::CairoPNG);
271 #endif
272  board.clear();
273  drawPolygon( resGraham.begin(), resGraham.end(), board );
274  board.saveSVG( "SimplePolygonalLineGraham.svg" );
275 #ifdef WITH_CAIRO
276  board.saveCairo("SimplePolygonalLineGraham.png", Board2D::CairoPNG);
277 #endif
278  board.clear();
279  drawPolygon( res.begin(), res.end(), board );
280  board.saveSVG( "SimplePolygonalLineMelkman.svg" );
281 #ifdef WITH_CAIRO
282  board.saveCairo("SimplePolygonalLineMelkman.png", Board2D::CairoPNG);
283 #endif
284  board.clear();
285  drawPolygon( ch.begin(), ch.end(), board );
286  board.saveSVG( "SimplePolygonalLineMelkman2.svg" );
287 #ifdef WITH_CAIRO
288  board.saveCairo("SimplePolygonalLineMelkman2.png", Board2D::CairoPNG);
289 #endif
290  }
291
292  { //order of the points for andrew algorithm
293  vector<Z2i::Point> res;
294  std::copy( pointSet.begin(), pointSet.end(), back_inserter( res ) );
295
296  std::sort( res.begin(), res.end() );
297
298  //display
299  Board2D board;
300  drawPolygon( res.begin(), res.end(), board, false );
301  board.saveSVG( "AndrewWEVP.svg" );
302 #ifdef WITH_CAIRO
303  board.saveCairo("AndrewWEVP.png", Board2D::CairoPNG);
304 #endif
305  }
306
307  { //order of the points for graham algorithm
308  vector<Z2i::Point> res;
309  std::copy( pointSet.begin(), pointSet.end(), back_inserter( res ) );
310
311  //find an extremal point
312  //NB: we choose the point of greatest x-coordinate
313  //so that the sort step (by a polar comparator)
314  //returns a weakly externally visible polygon
315  std::vector<Z2i::Point>::iterator itMax
316  = std::max_element( res.begin(), res.end() );
317
318  //sort around this point with a polar comparator
320  comparator.setPole( *itMax );
321  std::sort( res.begin(), res.end(), comparator );
322
323  //display
324  Board2D board;
325  drawPolygon( res.begin(), res.end(), board, false );
326  board.saveSVG( "GrahamWEVP.svg" );
327 #ifdef WITH_CAIRO
328  board.saveCairo("GrahamWEVP.png", Board2D::CairoPNG);
329 #endif
330  }
331
332
333 }
334
342 int main( int argc, char** argv )
343 {
344  trace.beginBlock ( "Example exampleConvexHull2D" );
345  trace.info() << "Args:";
346  for ( int i = 0; i < argc; ++i )
347  trace.info() << " " << argv[ i ];
348  trace.info() << endl;
349
350  convexHull();
351
352  trace.endBlock();
353
354  return 0;
355 }
356 // //
void beginBlock(const std::string &keyword="")
Trace trace
Definition: Common.h:130
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...
void drawLine(double x1, double y1, double x2, double y2, int depthValue=-1)
Definition: Board.cpp:368
STL namespace.
double endBlock()
void drawCircle(double x, double y, double radius, int depthValue=-1)
Definition: Board.cpp:451
void saveCairo(const char *filename, CairoType type=CairoPNG, PageSize size=Board::BoundingBox, double margin=10.0) const
Definition: Board.cpp:1139
Aim: Class that implements a binary point predicate, which is able to compare the position of two giv...
Aim: This class implements the on-line algorithm of Melkman for the computation of the convex hull of...
Aim: Model of the concept StarShaped represents any circle in the plane.
Definition: Ball2D.h:60
static const Color Blue
Definition: Color.h:394
double computeHullThickness(const ForwardIterator &itb, const ForwardIterator &ite, const ThicknessDefinition &def)
Procedure to compute the convex hull thickness given from different definitions (Horizontal/vertical ...
DGtal is the top-level namespace which contains all DGtal functions and types.
Aim: A wrapper class around a STL associative container for storing sets of digital points within som...
Go to http://www.boost.org/doc/libs/1_52_0/libs/iterator/doc/ForwardTraversal.html.
void andrewConvexHullAlgorithm(const ForwardIterator &itb, const ForwardIterator &ite, OutputIterator res, const Predicate &aPredicate)
Procedure that retrieves the vertices of the hull of a set of 2D points given by the range [ itb ...
void saveSVG(const char *filename, PageSize size=Board::BoundingBox, double margin=10.0) const
Definition: Board.cpp:1012
std::ostream & info()
Modifier class in a Board2D stream. Useful to choose your own mode for a given class. Realizes the concept CDrawableWithBoard2D.
Definition: Board2D.h:247
void melkmanConvexHullAlgorithm(const ForwardIterator &itb, const ForwardIterator &ite, OutputIterator res, Functor &aFunctor)
Procedure that retrieves the vertices of the hull of a set of 2D points given by the range [ itb ...
Board & setPenColor(const DGtal::Color &color)
Definition: Board.cpp:298
static const Color Red
Definition: Color.h:391
Aim: A utility class for constructing different shapes (balls, diamonds, and others).
Custom style class redefining the pen color. You may use Board2D::Color::None for transparent color...
Definition: Board2D.h:312
void grahamConvexHullAlgorithm(const ForwardIterator &itb, const ForwardIterator &ite, OutputIterator res, const Predicate &aPredicate, PolarComparator &aPolarComparator)
Procedure that retrieves the vertices of the convex hull of a set of 2D points given by the range [ i...
Aim: Class that implements an orientation functor, ie. it provides a way to compute the orientation o...
Aim: This class specializes a 'Board' class so as to display DGtal objects more naturally (with <<)...
Definition: Board2D.h:70