Example Convex Hull

The following program generates a list L of 10 rat_points in the square (-100,-100,100,100) and computes the convex hull H of L. Then it draws the points of L and finally shows the convex hull by drawing the points on the convex hull in red and edges between those vertices. On the right there is a screenshot of the program. Clicking on the picture shows the window in original size.

#include <LEDA/core/list.h>
#include <LEDA/geo/rat_point.h>
#include <LEDA/geo/random_rat_point.h>
#include <LEDA/graphics/window.h>
#include <LEDA/geo/geo_alg.h>

using namespace leda;

int main()
{
  list<rat_point> L;
  random_points_in_square(10,100,L);

  list<rat_point> H=CONVEX_HULL(L);
 
  window W;W.init(-110,110,-110); 
  W.open(); W.display();
  W.set_line_width(3);

  rat_point p;  //draw points in L
  forall(p,L) {W.draw_filled_node(p.to_point(),black);}
  W.read_mouse();
  
  //make points of convex hull red and draw edges
  list_item lit;
  forall_items(lit,H) {
    rat_point p=H[lit];
    rat_point q=H[H.cyclic_succ(lit)];
    W.draw_filled_node(p.to_point(),red);
    W.draw_edge(p.to_point(),q.to_point(),red);
    W.read_mouse();
  }

  W.screenshot("convex_hull");
 
  return 0;
}	  

See also:

Linear Lists

Windows and Panels

Data Types for 2-D Geometry

Convex Hull

Geometry

Number Types

Manual Entries

Manual Page of Geometry Algorithms