CONVEX_HULL
Convex Hull Demonstration

CONVEX_HULL is a MATLAB library which reads a file containing the coordinates of a set of points in 2D, computes the convex hull of the points, and displays it.

The MATLAB program convhull ( ) is used to create the image. For practical calculations, convhull ( ) should be used. This program is designed instead to demonstrate the ideas behind a simple version of the convex hull algorithm in 2D, known as the gift wrapping algorithm.

It is intended to augment this program by including a function which computes and displays the convex hull one edge at a time. This has the advantage of displaying the logic behind the calculation.

Usage:

convex_hull ( 'prefix' )

• 'prefix'_nodes.txt is the name of the file containing the node coordinates.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

CONVEX_HULL is available in a MATLAB version.

Related Data and Programs:

CG_LAB_TRIANGLES, MATLAB programs which deal with computational geometry and triangles;

convex_hull_test

GEOMETRY, a MATLAB library which performs geometric calculations in 2, 3 and M dimensional space.

POLYGON, a dataset directory which contains examples of polygons.

TRIANGULATE, a MATLAB program which triangulates a (possibly nonconvex) polygon, based on a C program by Joseph ORourke.

Reference:

1. Marc deBerg, Marc Krevald, Mark Overmars, Otfried Schwarzkopf,
   Computational Geometry,
   Springer, 2000,
   ISBN: 3-540-65620-0,
   LC: QA448.D38.C65.
2. William Eddy,
   CONVEX, a dnew convex hull algorithm for planar sets,
   ACM Transactions on Mathematical Software,
   Volume 3, 1977, pages 411-412.
3. Joseph ORourke,
   Computational Geometry in C,
   Second Edition,
   Cambridge, 1998,
   ISBN: 0521649765,
   LC: QA448.D38.

Source Code:

• convex_hull.m, a program which reads a file of point coordinates, computes and displays the convex hull.

Examples and Tests:

EDDY is 20 points provided by William Eddy as a test case for his ACM TOMS Algorithm 523 for convex hulls.

• eddy_nodes.txt, the nodes.
• eddy_nodes.png
• eddy_hull.png

ELLIPSOID1 is 200 points that lie on an ellipse;

• ellipsoid1_nodes.txt, the nodes.
• ellipsoid1_nodes.png
• ellipsoid1_hull.png

ELLIPSOID2 is 1000 points that lie inside an ellipse.

• ellipsoid2_nodes.txt, the nodes.
• ellipsoid2_nodes.png
• ellipsoid2_hull.png

GRAHAM is 11 points used by O'Rourke in a discussion of Graham's algorithm:

• graham_nodes.txt, the nodes.
• graham_nodes.png
• graham_hull.png

HAND is 59 points that outline a hand.

• hand_nodes.txt, the nodes.
• hand_nodes.png
• hand_hull.png

KN57 is 57 points which represent city locations in a traveling salesman problem.

• kn57_nodes.txt, the nodes.
• kn57_nodes.png
• kn57_hull.png

STAR is 10 points which are the vertices of a star.

• star_nodes.txt, the nodes.
• star_nodes.png
• star_hull.png

You can go up one level to the MATLAB source codes.