Welcome back to another Maple Learn blog post! Today we’re going to talk about the gift-wrapping algorithm, used to find the convex hull of a set of points. If you’re not sure what that means yet, don’t worry! We’re going to go through it with four Maple Learn documents; two which are background information on the topic, one that is a visualization for the gift-wrapping algorithm, and another that goes through the steps. Each will be under their own heading, so feel free to skip ahead to your skill level!
Before we can get into the gift-wrapping algorithm we need to define a few terms. Let’s start by defining polygons and simple polygons.
Polygon: A closed shape created by joining a series of line segments.
Simple polygon: A polygon without holes and that does not intersect itself.
So, what are convex and concave polygons? Well, there are three criteria that define a convex polygon. A polygon that is not convex is called concave. The criteria are…
- Any line segment connecting any two points within the polygon stays within the polygon.
- Any line intersects a polygon’s boundary at most twice.
- All interior angles are less than 180 degrees or pi radians.
Because the criteria are equivalent, if any one is missing, the shape is concave. AKA, all three criteria must be present for a shape to be convex. Most “regular shapes”, such as trapezoids, are convex polygons!
A shape that satisfies convex criteria but not the criteria for being a polygon is called a convex set.
As mentioned at the start of this post, the gift-wrapping algorithm is used to find the convex hull of a set of points. Now that we know what convex polygons and convex sets are, we can define the convex hull!
Convex hull: The convex set of a shape or several shapes that fully contains the object and has the smallest possible area.
Why was the convex polygon important? Well, the convex hull of a set of points is always a convex polygon. Some of the points in the set are the vertices of said polygon, and are called extreme points. You can find the convex hull of either concave or convex polygons.
This document amazed me when I tried it for the first time. Here, you can generate a set of points with the “Generate Another” button, and then press the “Visualize” button. The document then calculates the perimeter of the convex hull of the set of points! The set can be further customized below the buttons, by changing the number of points. The other option below it allows you to slow down or speed up the visualization. Pretty cool, huh? It’s like it’s thinking!
Try the document out a few times, or watch the gif below to get a quick idea of it.
This final document walks you through the steps of how to use the gift wrapping algorithm. It is a simple loop of 4 steps, with one set-up step. Unlike the other documents in this post, I won’t be delving too far into the math behind the steps. I want to encourage you to check this one out yourself, as it’s really quite a fun problem to solve once you have some time!
I hope you check out the documents in this post. Please let us know below if there’s any other documents you’d like to see featured!
