Así que hay varias preguntas sobre cómo calcular el casco convexo de un conjunto de puntos. Sin embargo, digamos que al inspeccionar el conjunto de puntos se inscribe una forma de estrella. Un algoritmo de casco convexo definiría un pentágono alrededor de una estrella de cinco puntos y lo llamaría casco convexo, pero si quisiera identificar la forma como una estrella de cinco puntas eso sería insuficiente.
¿Cómo podría entonces decirle al ordenador que defina un polígono que pueda ser cóncavo, que contenga todos los puntos de Q y tenga un área no nula, pero que minimice las áreas delimitadas por la forma en la que no hay puntos de Q?
Estoy pensando que un simple ajuste del Graham Scan para permitir los giros a la derecha, pero que en cambio no permita que las líneas se crucen, podría hacerlo, pero eso es sólo un tiro salvaje en la oscuridad que no he probado. También estoy pensando que, dada la aplicación normal de esto en los ordenadores (reconocimiento de patrones de imagen), que también tendría un conjunto de puntos R que NO deberían estar contenidos en el polígono, y después de encontrar el "casco convexo" de los puntos Q puedo entonces ejecutar una variación del algoritmo que añade "giros a la derecha" en los puntos que deberían estar fuera de la forma, pero actualmente están contenidos dentro.
Así que primero define el subconjunto H que define el casco convexo de un conjunto de puntos Q. Ahora, toma cada punto X de un conjunto R de puntos que no debe estar contenido en el polígono final. Determine si ese punto se encuentra dentro del polígono (lo hace si una línea desde cualquier punto en Q a X interseca cero o un número par de segmentos de línea que definen el polígono actual). Si es así, inserte X en H entre los dos puntos adyacentes M y N en H que tienen la menor distancia media de X. Entonces, para todos los P en Q que no están en H, si P ahora se encuentra fuera de la forma definida por H, añadir P a H entre M y X, o X y N, dependiendo de qué dos puntos tienen la menor distancia media. Repite la operación para todos los X de R.
¿Existe algún algoritmo probado que logre esto (y que sea menos complejo que O(N^2logN) dado que Q y R son aproximadamente iguales en cardinalidad)?
