This example demonstrates computing the convex_hull of a set of points on the plane based on the quickhull algorithm. See https://en.wikipedia.org/wiki/Quickhull for more information.

The example generates a set of random 2D points by std::generate. Then performs the quickhull algorithm on it. Left and right most points are found by std::minmax_element. On each step points on the right side of oriented line are copied by std::copy_if and the farthest point is found by std::max_element. Correctness of the convex hull is checked by std::any_of algorithm with counting iterators. The output of the example application is a CSV file with points of the convex hull.

System Requirements

For the most up-to-date system requirements, see the release notes.

Files
convex_hull.cpp
Implementation of the quickhull algorithm based on Parallel STL.
utils.h
Utility code: template point, random points generator.
Makefile
Makefile for building the example.
Directories
msvs
Contains a Microsoft* Visual Studio* IDE workspace for building and running the example (Windows* OS systems only).
Build instructions

To use Parallel STL, set up the environment by calling the pstlvars script (if you use a command line) or set the %PSTLROOT% environment variable pointing to the <pstl_installdir> folder (in Microsoft* Visual Studio* IDE on Windows* OS) and add the <pstl_installdir>/pstl/include folder to the compiler include paths.

Use the Makefile to build the example on the command line.

Use the msvs/convex_hull.sln project file to build the example in the Microsoft* Visual Studio* IDE (Windows* systems only).

Usage
convex_hull or convex_hull.exe
Outputs the result convex hull ConvexHull.csv

Legal Information

Intel and the Intel logo are trademarks of Intel Corporation in the U.S. and/or other countries.
* Other names and brands may be claimed as the property of others.
© 2017, Intel Corporation