Search code examples
outlinepolygonsverticesconcave

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

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

concave polygon

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.

Solution

  • 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