Given a large set of vertices in a non-convex polygon, how can i find the edges?

Question

I have a set of vertices(called A) and I want to find all the border vertices such that this border vertices set is an outline of the shape.

Many of the vertices in A are redundant because they are inside the shape, I want to get rid of these vertices.

My question is similar to http://stackoverflow.com/questions/477867/best-algorithm-to-find-the-edges-polygon-of-vertices but i need it to work for a non-convex polygon case.

EDIT: Clarification: The below image is a concave polygon. This is what i meant by non-convex. If I run a convex hull algorithm on it, it would not preserve the concave part of the polygon.(unless i'm mistaken).

I have a set of vertices inside and on the border of the polygon: [[x1,y1], [x2,y2]...] I want to reduce the set so that the vertices are just the border outline of the shape.

Answer 1

Your description is somewhat vague but it is possible that you are looking for the algorithm to construct a Convex Hull of a set of points. Simply put, the convex hull is the shape you get if you put a rubber band around all of the vertices.
Writing a convex hull algorithm in 2D isn't terribly difficult and there are some libraries that do it like qhull

(That answer is also given in the question you you link to which seems to be a special case of your question)

Answer 2

This is an old, maybe abandoned question, but it's got me thinking about it. You're not looking for a convex hull, you want to maintain the polygons shape, but just get rid of points that lie in between "edges" along a line.

The solution could be to step through neighboring points and calculate the linear slope of the first and second, then saving that slope value, calculate the slope of the second and third, if the slope of pt1-pt2 is equal to that of pt2-pt3 then pt2 is redundant in forming the line and thus can be removed. Keep looping through until you wind up back at pt1.

This would ensure your concave shape is maintained but irrelevant extra points are removed.

Answer 3

Perhaps you should have a look at the Douglas&Peuckert Algorithm. This has always done the trick for me... (if I understand your question correctly)

Tom

Answer 4

This seems to be a hot topic.. http://gis.stackexchange.com/questions/1200/concave-hull-definition-algorithms-and-practical-solutions

This paper seems to be the best. Duckham, M., Kulik, L., Worboys, M.F., Galton, A. (2008) Efficient generation of simple polygons for characterizing the shape of a set of points in the plane. Pattern Recognition v41, 3224-3236