draw_convex_hull

A QT program that draws the convex hull of randomly generated points.

• Requires at least CMake 3.13 to compile and build.
• The project depends on Qt5 and GoogleTest.

Install Dependencies

GoogleTest

On MacOS I find it most convenient to install GoogleTest system-wide as opposed to directly including the googletest/include directory in the project. Clone GoogleTest and build with CMake like so

   git clone https://github.com/google/googletest.git
   mkdir build
   cd build
   cmake ../ && make && make install

On Pop_OS! (which is based on Ubuntu) I don't formally build the project and install system-wide, instead I clone the project and simply move it to a place like /usr/src/ where it's visible in the system search PATH.

Qt5

On Pop_OS! install Qt5 with sudo apt-get -y install qtbase5-dev. On MacOS run brew install qt5. The install ends with a message like

 qt is keg-only and must be linked with --force

A consequence of which is that Qt5Widgets is not findable. Remedy the situation by adding to the the system PATH.

  echo 'export PATH="/usr/local/opt/qt/bin:$PATH"' >> ~/.zshrc

Capabilities

Compute and Draw a Convex Hull of a 2D Point Cloud

There is an executable that creates a configurable convex hull demo. The user can

• choose the number of randomly generated points from which a convex hull is generated
• pick a fast, ( n * log(n) ) convex hull algorithm, or a slower quadratic implementation.

Required parameters: 
--num  [Int] number of points to generate
--fast [Boolean] 'true' for the n*log(n) implemenation of convex hull algorithm
Ex.
 draw_convex_hull_demo --num 10000 --fast true

Mask 2D Points with a Point-In-Polygon Predicate

Given a simple closed 2D polygon generate a point-in-polygon predicate. In the image below one sees several thousand randomly generated points that were masked (or filtered) by PointInPolygon of the polygon marked in green. For comparison, the convex hull of the polygon is shown in blue.