And of course the source code for the convex hull algorithm. |
## Convex HullsA convex hull is a polygon in which the angle from one edge to the next is always bigger than 60 degrees. That sounds like a useless trait, but that property describes any polygon that can enclose an arbitrary collection of points without "bites" in the outline. Let's build some! For this particular implementation, we'll use a gift wrapping approach. We start at a virtual point offscreen, and drag a line across the screen until we've found a point to the left of which are all other points. That's our starting point, and the line from the virtual point to the starting point is our first edge. Albeit virtual. We then perform an extremely expensive algorithm: Given our edge from p Now run through every other point, and see what the angle is from p If the last point that's left in this way is the first point of our hull, we're done. We now have a closed hull. How "expensive" is this operation? Let's find out! On your computer, it takes ... milliseconds to find the convex hull for ... points! |