Computing the convex hull is a preprocessing step to many geometric algorithms and is the most important elementary problem in computational geometry, according to Steven Skiena in the Algorithm Design Manual.
Graham scan algorithm
This algorithm is pretty straightforward to learn.
You may have heard that you can use sorting to find a convex hull and wondered how and where sorting would come into play.
The basic idea
Initialize an empty stack that will contain the convex hull points.
Pick a starting point and add it to the stack.
Sort the rest of the points in counterclockwise order around the starting point.
Sweep through the sorted points.
Initially add each new point to the stack and then check to make sure that the hull is still convex with the new point.
Delete any points that create concave angles - these points lie inside of the hull.
Python implementation of the Graham scan algorithm
If the result is negative, then the three points are rotating right in a clockwise direction, which would add a concave angle to the polygon, so we want to get rid of the second point, p2, because it lies inside the convex hull.
After removing P2 from the stack, check to make sure the new triplet in hull[-3:] rotates left - if it still rotates right, keep removing the middle point until the triplet rotates left.
while len(hull) > 2 and get_cross_product(hull[-3],hull[-2],hull[-1]) < 0:
If the cross product is zero, meaning the points are in a straight line or collinear, it's up to you and your project requirements whether or not you want to keep or drop the point.
Then move on to the next point in the sweep.
When the sweep is done, the points that remain in hull are the points that form the convex hull.
D3 has a built-in force to detect circle collisions in force layouts, but what if you're working with rectangles? In this post we will go over how to detect and resolve collisions, and then adapt D3's built-in forceCollide to work on rectangles.
You can do a lot of interesting things with the Spotify API, like searching for artists and playlists, following and sharing them, and more. In this post we will access the API using Python to get featured playlists and associated artists and genres.
Pictograms have been around for a long time, and with good reason. They are interesting and engaging, and might even help your audience to remember the information better. In this post we will build a pictogram grid in D3.js.