algorithm - poligonos - encuentre el polígono convexo que contiene el menor número de puntos

poligonos concavos y convexos ejemplos

Question

dado un polígono convexo y un número N, ¿cómo encuentro el polígono más pequeño que

1. Contiene todos los puntos del polígono original.
2. tiene exactamente N puntos de esquina

Por ejemplo, supongamos que tengo un conjunto de puntos y calculo el casco convexo para ellos (verde). Ahora quiero encontrar el cuadrángulo más pequeño que contiene todos los puntos (rojo)

Es fácil ver que cualquier otro polígono con 4 esquinas sería más grande o no contendría todos los puntos. ¿Pero cómo encuentro este polígono en el caso general?

EDITAR:

Con el polígono más pequeño me refiero al que cubre el área más pequeña, aunque no estoy seguro de que la circunferencia más pequeña dé resultados diferentes.

Agregué dos imágenes de ejemplo más que, lamentablemente, no parecen funcionar con el enfoque ''eliminar bordes'' en una de las respuestas

Alguna información de fondo:

El objetivo es determinar con precisión las formas con reconocimiento de imagen. Por ejemplo, tomar una foto de un cuboide. Todos los puntos dentro del cuadro en la foto 2D estarán contenidos en un polígono convexo de 6 esquinas. Sin embargo, como las formas del mundo real no tienen esquinas perfectas, y la cámara añade algo de desenfoque, los bordes de este polígono se redondearán. Ver la imagen adjunta de la pregunta Obtención de esquinas a partir de puntos convexos.

Answer 1

Debe definir la noción de "más pequeño" en su pregunta. Sea cual sea su definición, esta pregunta ha sido muy estudiada en la literatura de geometría computacional. La frase clave de búsqueda es mínima y encierra k-gon :

• Mictchell et al .: "Perímetro mínimo que encierra k-gon" 2006 ( enlace CiteSeer )
• Aggarwal et al .: "Polígonos de circunscripción de área mínima" 1985 ( enlace CiteSeer )
• O''Rourke et al .: "Un algoritmo óptimo para encontrar triángulos circundantes mínimos" 1986, Algorithmica ( enlace ACM )

Los algoritmos generales no son simples (aunque los algoritmos para triángulos o rectángulos de área mínima son simples). Dependiendo de sus objetivos, es posible que deba abandonar cualquier noción matemática de "más pequeño" y dirigirse a una heurística.

Answer 2

While number of edges > N do
  remove the shortest edge by replacing its endpoints 
  with the intersection point of the adjacent edges