ginaspider (ginaspider) wrote in algorithms,
ginaspider
ginaspider
algorithms

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

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 4 comments

appughar

March 27 2008, 05:42:59 UTC 7 years ago

Convex Hull

Qhull is a popular algorithm to compute the convex hull.

ginaspider

March 27 2008, 05:46:04 UTC 7 years ago

Hey, this looks like it will work. Thanks!!

ginaspider

March 27 2008, 05:44:04 UTC 7 years ago

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?

antilamer

March 27 2008, 05:56:43 UTC 7 years ago

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