ginaspider (ginaspider) wrote in algorithms,

Anyone know of a good algorithm to find the border around a 2d polygon mesh?
  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

Convex Hull

Qhull is a popular algorithm to compute the convex hull.
Hey, this looks like it will work. Thanks!!
Ok, so this was what I was thinking about so far.

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 :)