Teniendo en cuenta un amplio conjunto de vértices en un polígono no convexo, ¿Cómo puedo encontrar los bordes?

Question

Tengo un conjunto de vértices (llamada) y quiero encontrar todos los vértices de la frontera de tal manera que este conjunto de vértices frontera es un esquema de la forma.

Muchos de los vértices en A son redundantes porque están dentro de la forma, quiero para deshacerse de estos vértices.

Mi pregunta es similar a mejor algoritmo para encontrar los bordes (polígono) de vértices pero que necesitan trabajar para un caso polígono no convexo.

EDIT: Aclaración: La imagen abajo es un polígono cóncavo. Esto es lo que quería decir con no-convexa. Si me quedo un algoritmo de casco convexo en él, no sería preservar la parte cóncava del polígono. (Si no me equivoco).

Tengo un conjunto de vértices en el interior y en el límite del polígono: [[x1, y1], [x2, y2] ...] Quiero reducir el conjunto de manera que los vértices son sólo el contorno borde de la forma.

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)