Polígono que encierra un conjunto de puntos
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, siendo P 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
4 answers
Hay muchos algoritmos para este problema. Se llama " caja delimitadora mínima". 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).
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-05-06 10:07:34
Aquí hay una solución simple...
Comience con tres puntos cualesquiera para formar un triángulo. Añadir cada punto adicional al polígono con la siguiente operación:
Divida las aristas en dos trazados continuos, donde en un trazado la línea de cada arista separa el punto a añadir del resto del polígono (llamémoslo el "trazado de separación") y en el otro trazado, la línea de cada arista tiene el punto en el mismo lado que el polígono.
(Nota: siempre y cuando su forma permanece convexo, que debe, 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 extremo de la ruta de separación al nuevo punto.
¡Ta-da! :)Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-05-06 10:27:52
Probablemente quiere 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értice súper grandes para que todos tus puntos estén encerrados.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-05-06 10:12:53
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)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-05-07 05:24:40