Polígono que encierra un conjunto de puntos

Tengo un conjunto S de puntos (2D: definido por xey) y quiero encontrar P, el polígono más pequeño (es decir, con el menor número de puntos) que encierra todos los puntos del conjunto, P es un subconjunto ordenado de S.

¿Hay algún algoritmo conocido para calcular esto? (Mi falta de cultura en este dominio es sorprendente …)

Gracias por tu ayuda

Hay muchos algoritmos para este problema. Se llama ” caja límite mínima “. Encontrará soluciones que también buscan ” casco convexo “, especialmente aquí .

Una forma es encontrar el punto más a la izquierda y luego repetir para buscar un punto donde todos los demás puntos estén a la derecha de la línea p (n-1) p (n).

Aquí hay una solución simple …

Comience con tres puntos para formar un triángulo. Agregue cada punto adicional al polígono con la siguiente operación:

Divida los bordes en dos caminos continuos, donde en un camino la línea de cada borde separa el punto que se agregará del rest del polígono (llamémoslo “camino de separación”) y en el otro camino, la línea de cada borde tiene el punto en el mismo lado que el polígono.

(Nota: siempre que su forma permanezca convexa, lo cual debe ser, estas dos rutas serán continuas y formarán la forma completa)

Si la ruta de separación no tiene bordes, el punto está dentro del polígono y debe ignorarse; de ​​lo contrario, elimine la ruta de separación del polígono. Reemplácelo con dos segmentos, conectando cada punto final de la ruta de separación al nuevo punto.

Ta-da! 🙂

Probablemente quiera decir que quiere el área más pequeña, que es el casco convexo.

Si realmente quieres la menor cantidad de puntos , puedes hacer un triángulo con posiciones de vértices supergrandes para que todos tus puntos estén encerrados.

Aquí hay un buen recurso sobre algoritmos de casco convexo: el casco convexo de un conjunto de puntos 2D o polígono (por Dan Sunday)