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

This seems to be a hot topic.. https://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

Answer 2

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 3

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 4

The term you are looking for is concave hull.

The simplest form of the problem is not well defined like convex hull, because the concave polygon that covers given points is not unique. However there are many good approaches.

One of the simplest approach is, you use the gift wrapping algorithm but instead of considering all the points at each step you only consider k-nearest neighbors of the current vertex.

Here k is your hyper-parameter to tune. If k is too high you get the convex hull. If k is too low you the resulting polygon has lots of concavities.

---

Here are some related links:

• https://github.com/mapbox/concaveman
• https://gis.stackexchange.com/questions/1200/what-are-definition-algorithms-and-practical-solutions-for-concave-hull
• Concave hull: A k-nearest neighbours approach for the computation of the region occupied by a set of points (link)