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).
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.
After experimenting with my rasterizing algorithm I used Anti-Grain Geometry by Maxim Shemanarev. See the result on Picture 4.
You can find the sources on GitHub: https://github.com/evpo/ConvexHull
Binaries for windows are also available:
Download the zip file and run the cmd file to see it in action.
- OpenGL hardware acceleration through remote X11 SSH connection
- GDB: How do I set current source file for list and break commands
- How To Create and Seed a Torrent (Ubuntu server, Transmission)
- GIT TF: Undo shallow pull and pull squashed changeset
- Lynx on Windows 7 and lynx_bookmarks.html file problem
- Old MacBook Overheating and Installation of Mac OS 10.4 on New Hard Drives
- Memory Alignment Of Structures and Classes in C++
- Align label and input vertically
- Google Test Framework and Visual Studio 2010
- Convex Hull
- Run a bash script with sudo, nohup and in the background
- Contact database with web interface – EVPO Members