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 iterator (Threading Building Blocks (TBB) 2019 is required). 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 (1) 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

Read Getting Started with Parallel STL for general instructions on setting up and using Parallel STL.

Use the Makefile (1) 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

(1) The delivered Makefile is provided for illustration purpose and supports Intel® C++ Compiler only.


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-2019, Intel Corporation