Find the left-most vertex (vertex 1). Imagine a vector going to the left from that. Make that angle 0 where clockwise rotation increases the angle. Search all connected verts until you find the one with the smallest angle (vertex 2). Make the vector between that and the previous vertex angle 0. Repeat until you get back to vertex one and then you'll have your border.

Does this sound right? Anyone have any better suggestions?

Yes, that's exactly one of the most known algorithms for computing the convex hull. However there are a lot better ones (the best one performing at O(n log n), or O(n) if the vertices are sorted on a coordinate) as well as optimizations to this one. However, appughar has already given you some :)

appugharMarch 27 2008, 05:42:59 UTC 8 years ago

Qhull is a popular algorithm to compute the convex hull.

ginaspiderMarch 27 2008, 05:46:04 UTC 8 years ago

ginaspiderMarch 27 2008, 05:44:04 UTC 8 years ago

Find the left-most vertex (vertex 1). Imagine a vector going to the left from that. Make that angle 0 where clockwise rotation increases the angle. Search all connected verts until you find the one with the smallest angle (vertex 2). Make the vector between that and the previous vertex angle 0. Repeat until you get back to vertex one and then you'll have your border.

Does this sound right? Anyone have any better suggestions?

antilamerMarch 27 2008, 05:56:43 UTC 8 years ago