Finding the Convex Hull

Why Convex Hull?

Finding the convex hull of a set of points is the most elementary interesting problem in computational geometry, just as minimum spanning tree is the most elementary interesting problem in graph algorithms. It arises because the hull quickly captures a rough idea of the shape or extent of a data set.

Convex hull also serves as a first preprocessing step to many, if not most, geometric algorithms. For example, consider the problem of finding the diameter of a set of points, which is the pair of points a maximum distance apart. The diameter will always be the distance between two points on the convex hull. The O(n \lg n). algorithm for computing diameter proceeds by first constructing the convex hull, then for each hull vertex finding which other hull vertex is farthest away from it. This so-called ``rotating-calipers'' method can be used to move efficiently from one hull vertex to another.

INPUT                    OUTPUT

What is convex hull? What is the convex hull problem?

For a subset of , the convex hull is defined as the smallest convex set in containing .

The convex hull computation means the ``determination'' of for a given finite set of points $S = \{p^1, p^2, \ldots, p^n\}$ in .

The usual way to determine is to represent it as the intersection of halfspaces, or more precisely, as a set of solutions to a minimal system of linear inequalities. This amounts to output a matrix $A \in R^{m \times d}$ and a vector $b\in R^m$ for some such that $conv(S) =\{ x \vert A \; x \le b \}$ . When is full-dimensional, each (non redundant) inequality corresponds to a facet of . Thus the convex hull problem is also known as the facet enumeration problem.

Some people define the convex hull computation as the determination of extreme points of , or equivalently that of redundant points in to determine . This is much simpler computation than our convex hull problem. In fact, this can be done by solving linear programs and thus polynomially solvable.

Guidelines for Use

To illustrate the convex hull, we start with a simple image containing some distinct artificial objects( specifically text)

Now we apply Grayscale conversion to the image to convert it to Grayscale image.

Now, we will convert the image into binary so only two intensities will be present in the image..... Black and white or in other words 0 and 1.

After scanning this image and labeling the distinct pixels classes with a different grayvalue, we obtain the labeled output image.

C# Sample Program:

The algorithm is coded in C# using unsafe so the quality and speed of the program may not be affected. The class BitmapData is used to read and process the pixels in the image. This is the specialty of C# to provide such a speed even on image processing applications. There is a set of modules that are designed to implement the algorithm. The program scans the image to convert the image into grayscale Levels. Then it converts the image into binary. This binary image will be subjected to splitting it into components. Here we can use 4-Connected or 8-Connected Algorithm but we used 8-Connected Algorithm for finding the Blobs in the image as described above.
The final output is a colored image showing separate colors for every blob.... An array named objects of Type Class Objects contains the sizes of each blob or object being segmented and the object also contains the convex hulls of the objects yet obtained...

Please refer to the article RTS Invariant Moments for more information about the class hierarchy used here. Here we discuss the other used classes.

CDLL: This is the doubly linked list used to organize the points. So, the decision is made whether the point is included in the convex hull or not. Its functionality is same as that of the usual Linked lists.

Point: A class similar to the built in Point class in C#.

Polysort: The points are sorted using this class..

Output: A word file containing the Convex Hull of each of the blob so obtained.

Attachments:

Project Files: ConvexHull.zip