3 ms·
I'm probably missing something, because I don't see what's so difficult about this. You can do this as a "rolling" algorithm. Start with three points, defining
by TheLoneWolfling 12y ago
I'm probably missing something, because I don't see what's so difficult about this.
You can do this as a "rolling" algorithm. Start with three points, defining a triangle. Then repeatedly add the next point.
To add a point, first check if it's inside the (convex) polygon found so far. If it is, you're done. Just continue to the next point to add.
If it isn't, you walk along both directions along the (convex) polygon until you hit the first point that doesn't violate the convexity constraint. (Just compare slopes of the lines between the next point and the target point, and the target point and the point to be added). Then just splice it in in place of the chunk removed.
Now, this isn't particularly fast - O(n^3) I think, but it's still faster than spinning up a LP solver.
(Again, I'm probably missing something.)
- Trombone12 12y agoThe solution demonstrated on the page seems to ask for the n-gon that circumscribes n randomly placed points, which isn't the same as the smallest convex hull that contains them. I'm not sure why the polygon should have the same number sides as there are points to contain, especially since the original tweet asks for a convex hull, but there you go.
- TheLoneWolfling 12y agoOh, ok. That makes much more sense.
- Strilanc 12y agoFYI, the algorithm you were describing was to compute a convex hull. It can be done in O(n lg n) time by sorting the points by angle w.r.t. some starting point and then "gift wrapping". You can find where to add a new point in O(lg h) time with a binary search, but you may need to eject O(h) old points. Points can only be ejected once, so there might still be some nice aggregate bound in terms of n. http://en.wikipedia.org/wiki/Convex_hull_algorithms http://en.wikipedia.org/wiki/Convex_hull_algorithms
- laex 12y agoSome time back, I wrote a simple convex hull computing code in Go. If anyone's interested: https://github.com/hemantasapkota/go-convexhull https://github.com/hemantasapkota/go-convexhull