Polígono que encierra un conjunto de puntos

Question

Tengo un conjunto S de puntos (2D: definido por x e y) 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 asombrosa ...)

Gracias por tu ayuda

Answer 1

Hay muchos algoritmos para este problema. Se llama " cuadro de límite mínimo " ;. También encontrará soluciones buscando " 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).

Answer 2

Aquí hay una solución simple ...

Comienza 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 va a agregar del resto del polígono (llamémoslo `` camino de separación '') y en el otro camino, el la línea de cada borde tiene el punto en el mismo lado que el polígono.

(Nota: mientras su forma permanezca convexa, lo que debe ser, estos dos caminos serán continuos y formarán toda la forma)

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! :)

Answer 3

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

Si realmente quiere la menor cantidad de puntos , puede hacer un triángulo con posiciones de vértices súper grandes para que todos sus puntos estén encerrados.

Answer 4

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)