Evgeny Pokhilko's Weblog

Programmer's den

Convex Hull


I read about the problem of finding Convex Hull in Algorithm Design Manual and knew that the complexity should be N for points sorted by one coordinate. Before reading about existing solutions I determined to find my own. “Invent the wheel” in other words. I spent hours thinking about a solution. In the end I found one:

I have a collection containing convex hull points. It is an stl::list. It’s empty at the beginning. I loop through points sorted by x. So I move from left to right of the picture. At the end of processing each point I maintain the algorithm invariant in which the list contains the convex hull of the points processed so far.  If you imagine this visually, it’s like putting a deflated balloon on an object from left to right.

When I process a point, I calculate if it’s on the top edge of the hull and then I do the same for the bottom edge. I also loop through the points that are already in my existing convex hull collection to see if they are not on the edge yet given the current processed point. If it’s not I remove it from the hull collection.

An important part of the algorithm is the function ConvexHull::compare_vectors. It takes three points and calculates if the point in the middle is on the edge of the convex hull. It represents the three points p1, p2 and p3 as two vectors p1 – p2 and p2 – p3. Then it prolongs p1 – p2 vector until it intersects with x = p3.x line. If y of the intersection point is higher than p3.y, the point is on the top edge of the convex hull (picture 1).

compare_vectors

Picture 1

The algorithm is in a console application that takes an image file (Picture 2), draws the convex hull and saves it to another image file (Picture 3). It supports multiple image file formats thanks to the stbi_image library.

ovals

Picture 2

ovals(hull)

 

After experimenting with my rasterizing algorithm I used Anti-Grain Geometry by Maxim Shemanarev. See the result on Picture 4.

 

 

Picture 3

1942_Nash_Ambassador_X-ray(result)

Picture 4

You can find the sources on GitHub: https://github.com/evpo/ConvexHull

Binaries for windows are also available:

http://sourceforge.net/projects/convexhull/files/ (100% CLEAN award granted by Softpedia)

Download the zip file and run the cmd file to see it in action.

 

May 4, 2013 - Posted by | Algorithms, C++

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: