Easy Convex Hull Construction
Sunday, 1. November 2009, 06:35:50
If you've ever tried to look at P=NP and related problems, you've probably encountered the traveling salesman problem. And if you've ever tried to find a solution to this, even if just for fun, you may have thought about building a convex hull to start off. Well, I thought of building one. But I couldn't find an easy algorithm that I could understand. Sure, there are plenty of them out there and I know how they work, but they all seemed a little convoluted. So I created my own algorithm only to find out it's a variation of the Graham Scan (you can see the one liner at the bottom of the article describing it under "Notes"). Still, the version described here is super simple to understand and I thought it deserves a mention.
A Convex Hull is essentially a list of points that completely contains all other points where all angles between any three points of this convex hull is convex (hence its name). You can think of it as an elastic band surrounding all points.
A Convex Hull is essentially a list of points that completely contains all other points where all angles between any three points of this convex hull is convex (hence its name). You can think of it as an elastic band surrounding all points.
WIDGETIZE