A Convex Hull algorithm implemented in C++. It's simple to read and understand and the complexity is O(N) when the points are sorted by one coordinate. The console app opens an image file, draws convex hull and creates an output image file.
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
Failed to load latest commit information.



A new algorithm and implementation of
1. Convex Hull problem
2. Line drawing algorithm

The C++ code is simple to read and understand. The complexity is O(N) when the points are sorted by one coordinate. 
This console app opens an image file, draws the convex hull and creates an output image file. 

The command line parameters:
ConvexHullConsole.exe <INPUT_FILE> -o <OUTPUT_FILE> [-c <RGBA>|<RGB>] [-w <STROKE_WIDTH>]

-c <RGBA>|<RGB> - Color components in HEX
  RRGGBBAA RGB and alpha A
  Alpha examples: FF - non transparent, 7F - half transparent and 00 - invisible
  Example: -c 00FF00FF for non transparent green
  Default: FF00007F
  If you don't specify the alpha, 0xFF is used by default
  Use color picker: http://www.w3schools.com/tags/ref_colorpicker.asp

-w <STROKE_WIDTH> - decimal value.
  Example: 1.5
  Default: 2.0
INPUT_FILE can be in any format supported by the stb_image.c library (see the link below). 

OUTPUT_FILE will be created in PNG format.

stb_image (http://nothings.org/stb_image.c)
stb_image_write (http://nothings.org/stb/stb_image_write.h)
Anti-Grain Geometry 2.5 by Maxim Shemanarev (http://www.antigrain.com/)
Google C++ Testing Framework (https://code.google.com/p/googletest/) 



Evgeny Pokhilko (C)
Sydney 2014

Release notes:

  1. Previously the application draw a convex hull around pixels that are not white (0xFFFFFF). So for any picture with a background the convex hull was the square at the edges of the picture. Now we take the median color from the picture to identify which pixels to ignore. So for a yellow background and a black image the yellow pixels are ignored. For a white background and a yellow image, the white pixels are ignored.

  1. Use AGG library for rasterization with higher quality and anti-aliasing.
  2. Added parameters -c and -w for specifying color and width of the stroke respectively.
  3. Support for images with gray and gray with alpha pixels.