Cascos convexos interiores en un conjunto de puntos 2D

Question

Un conjunto de 2D Puntos se encuentran dispersos al azar (es decir, no se especifica el patrón), estamos interesados en encontrar todos interno-convexo-cascos (ICH) en un orden de mayor en la zona de mínimo hasta que toda el área de estudio a ser cubierto por el conjunto de Cish, si es posible.

Como se muestra en la siguiente figura, parece que el verde convex-hull es el más grande posible de interior. Nos referimos a la interior, lo que implica que no hay un punto puede estar dentro de la deseada convex-hull. La condición de contorno para la región puede ser una normal (es decir, convencionalmente reconocidos) convex-hull para todos los puntos. En la Figura de la primera más grande en el área de interior-convex-hull #1 está seleccionado en primer lugar. El área cubierta por el #1 es entonces excluidos para evitar la superposición del problema de las próximas generaciones. Parece un poco confuso y difícil, la esperanza, la Figura de la ayuda. Supongo que puede ser el concepto de cubierto más grande de elipse podría ayudar. Sin embargo, es una suposición de arranque.

Actualización 1:
Bien, el resultado de la aplicación de la idea dada a continuación por Uffe Kousgaard está aquí:

Los números son rangos, es decir, a menor número, mayor área. Muestra de trabajo, sin embargo, nos dimos cuenta de varios casos el resultado no es correcto. Puede ser debido a errores en nuestra aplicación o el método, como señaló whuber abajo como comentario.

Aquí es el resultado del método mencionado por Uffe aplicado en whuber's de datos:

Al parecer hay algo que NO funciona bien!

Actualización 2:
La correcta solución completa es la siguiente (para whuber's de datos de ejemplo):

Hay tres etapas, por lo tanto, para completar la solución. Se aplica el método plenamente en cada etapa. Es decir, en la primera fase, cuando todos los triángulos fueron visitados por posible más grande del interior del convex-hull, el seleccionado ICH se almacena y el obsoleto asociados bordes/puntos se retiran a partir de los datos. El procedimiento se inicia de nuevo para el resto de los datos. Encontrado una solución, los pasos mencionados anteriormente se aplican. Después de agotar todas las iteraciones (en una suerte de situación como aquí), la zona está totalmente cubierto por Cish (aquí por 3 ICH), que es nuestro objetivo final. Tenga en cuenta que las respuestas posibles hasta ahora son sólo una iteración.

Aquí mostramos nuestra comprensión de la whuber's comentario/respuesta.

Fue correcto que codiciosos enfoque no funcionará como se demostró anteriormente. Esto descalifica Uffes de la idea de una solución correcta, por desgracia. Parece más difícil así, en comparación con los primeros pensamientos.

Answer 1

Una solución podría ser esta:

1) Calcular una triangulación de todo el área.

2) Para cada triángulo, prueba si la inclusión de triángulos vecinos retiene la convexidad. Si más de 1, elige el vecino, que añade más a la zona. Ejecute la prueba de nuevo con un nuevo conjunto de triángulos vecinos.

No sé si esto realmente encontrará la mayor ICH, pero debe ser un buen candidato.

Answer 2

Este es un comentario, pero podría ser considerado parcial progreso hacia una solución en la medida en que se puede dirigir la conversación fuera de un subóptima de la técnica.

Un algoritmo voraz basa en una triangulación no siempre funciona. Como contraejemplo, considere la posibilidad de la colección de rojo y azul puntos en esta figura:

Un parcial de triangulación se muestra: se extienden en cualquier forma que quieras, a los puntos rojos. Esta triangulación utiliza solamente los puntos azules, en las coordenadas ((-2,-1),(-1,-4),(0,-1),(2,-1),(2,1),(1,4),(0,1),(-2,1)) (en fin, como el número "1" al "8"). Los triángulos con termini en "2" y "6" cada uno tiene el área 3 (llamar a estos "grandes" triángulos"); los otros cuatro triángulos tienen zona 2.

Es fácil ver que el "casco interior" de área máxima es el rectángulo de 1458, de la zona 8. Sin embargo, cualquier algoritmo voraz que asegúrese de recoger, al menos, un gran triángulo, pero no ambas. Pero tan pronto como se incluye uno, se puede incluir en la mayoría de los otros dos triángulos, limitando el área de su solución a la 7, que no es óptima. Algunos de los puntos rojos podría además ser incluidos, pero obviamente que va a agregar sólo una insignificante de la zona: la solución permanecerá no es la óptima.

Tenga en cuenta que este ejemplo puede ser alterado por el movimiento de los puntos 2 y 6 más cerca de los otros puntos (casi vertical) hasta que los triángulos grandes áreas sólo ligeramente mayor que 2. También puede ser alterado mediante la inclusión de más puntos rojos dentro de los triángulos 678 y 123, haciendo su contribución a cualquier óptima completamente despreciable. En consecuencia, esta construcción muestra que el algoritmo voraz puede producir soluciones de área 6+e, para pequeños valores de e, cuando la solución óptima ha de la zona 8.

---

Otra de las contribuciones de esta respuesta es para compartir este método de construcción de útiles pequeños ejemplos para trabajar: por aspersión de un gran número de estrechamente espaciadas puntos en áreas clave, que efectivamente se puede eliminar aquellas áreas de las posibles soluciones. Esto nos permite centrarnos en arbitrario punto de conjuntos (y sus triangulaciones), de cualquier forma, sin tener que considerar la totalidad de sus cascos convexos. (En este ejemplo, los puntos rojos elimina los triángulos 687 y 243 de la consideración en la solución).