Dado un gran conjunto de vértices en un polígono no convexo, ¿cómo puedo encontrar los bordes?

Question

Tengo un conjunto de vértices (llamado A) y quiero encontrar todos los vértices fronterizos de modo que este conjunto de vértices de borde sea un contorno de la forma.

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

Mi pregunta es similar a Best Algorithm to find the edges (polygon) of vertices pero necesito que funcione para una caja de polígono no convexa.

EDITAR: Aclaración: La imagen de abajo es un polígono cóncavo. Esto es lo que quise decir con no convexo. Si ejecuto un algoritmo de casco convexo, no preservaría la parte cóncava del polígono (a menos que esté equivocado).

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

Answer 1

Esto parece ser un tema candente .. https://gis.stackexchange.com/questions/1200/concave-hull-definition-algorithms-and-practical-solutions

Este trabajo parece ser la mejor. 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

Su descripción es algo vaga, pero es posible que esté buscando el algoritmo para construir un Convex Hull de un conjunto de puntos. En pocas palabras, el casco convexo es la forma que obtienes si pones una banda elástica alrededor de todos los vértices.
Escribir un algoritmo de casco convexo en 2D no es terriblemente difícil y hay algunas bibliotecas que lo hacen como qhull

(Esa respuesta se da también en la pregunta que se vincula a lo que parece ser un caso especial de su pregunta)

Answer 3

Esta es una pregunta antigua, tal vez abandonada, pero me hace pensar en ello. No estás buscando un casco convexo, quieres mantener la forma de los polígonos, pero simplemente deshacerte de los puntos que se encuentran entre los "bordes" a lo largo de una línea.

La solución podría ser atravesar puntos vecinos y calcular la pendiente lineal de la primera y segunda, luego guardar ese valor de pendiente, calcular la pendiente de la segunda y tercera, si la pendiente de pt1-pt2 es igual a esa de pt2-pt3, entonces pt2 es redundante en la formación de la línea y, por lo tanto, se puede eliminar. Siga haciendo un looping hasta que termine en pt1.

Esto aseguraría que se mantenga su forma cóncava pero se eliminen los puntos extra irrelevantes.