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 de el conjunto, P es un subconjunto ordenado de S.Polígono que encierra un conjunto de puntos
¿Existen algoritmos conocidos para calcular esto? (Mi falta de cultura en este dominio es asombrosa ...)
Gracias por su ayuda
Hay muchos algoritmos para este problema. Se llama "minimum bounding box". Encontrará soluciones que también buscan "convex hull", especialmente here.
Una forma es encontrar el punto más a la izquierda y luego repetir para buscar un punto donde todos los otros puntos estén a la derecha de la línea p (n-1) p (n).
Gracias, esto era exactamente lo que estaba buscando. Al escribir "jarvis march java" o "quick hull java" en google, incluso encontré implementaciones java. –
"cuadro delimitador mínimo" es ... una caja. No es un polígono genérico. Los otros enlaces pueden ser buenos. –
No estoy seguro de qué tiene que ver el "cuadro delimitador mínimo", ya que se requiere que P sea un subconjunto de S. – AnT
Probablemente quiera decir que quiere el área más pequeña, que es el casco convexo.
Si realmente desea la menor cantidad de puntos, puede hacer un triángulo con posiciones de vértices supergrandes para que todos sus puntos estén encerrados.
Los puntos P de su gran triángulo no serían un subconjunto de S, que es uno de los requisitos. –
@DanielDaranas ¿Cómo se pueden obtener los vértices de este triángulo super grande? – Dinesh
Aquí es una solución simple ...
Comience con cualquiera de los tres puntos para formar un triángulo. Agregue cada punto adicional al polígono con la siguiente operación:
Divida los bordes en dos rutas continuas, donde en una ruta la línea de cada borde separa el punto que se agregará del resto del polígono (llamémoslo "separación de ruta") y en la otra ruta, la línea de cada borde tiene el punto en el mismo lado que el polígono.
(Nota: el tiempo que su forma se mantiene convexa, que debe, estos dos caminos será continua y formar la forma completa)
Si la ruta de separación no tiene bordes, el punto es el interior del polígono y debe ser ignorado; 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! :)
Aquí es un buen recurso en algoritmos de la envolvente convexa: The Convex Hull of a 2D Point Set or Polygon (by Dan Sunday)
Hola, Necesito implementar misma funcionalidad en mi solicitud. Por favor comparte algoritmo conmigo? –
Utilicé QuickHull. Referencia aquí: https://en.wikipedia.org/wiki/Quickhull –