Algoritmo Quickhull

[[seoane]]

Bueno, acabo de ver la pagina de roman y creo que no estoy aplicando bien el algoritmo, llego al mismo resultado pero no sigo los mismo pasos. Que le vamos a hacer ...

[roman]

Pensé que en tu primer mensaje te referías a esa página (que, por cierto, no es mía ) ¿En qué página consultaste? ¿A qué te refieres con superior e inferior? ¿Y al otro lado? Ya me estás intrigando. Según yo, sólo hay una posible envoltura convexa.

// Saludos

[[seoane]]

Vamos a ver. En el algoritmo QuickHull, parte de una linea, y solo utilizan los que están por encima de ella (luego el proceso se repite para los que están por debajo). Ahora se busca el punto mas alejado a la linea y se forma un triángulo, se eliminan los puntos dentro del triángulo y se repite el proceso en los 2 nuevos lados del triángulo.

Pues bien, yo lo que hago es lo siguiente. Parto de la misma linea que en el caso anterior, busco el punto mas a la izquierda que este por encima de la linea, y el que esta mas a la derecha. Trazo entonces una nueva linea imaginaria entre ambos, elimino todos los puntos que quedan por debajo, y vuelvo a repetir el proceso. Los extremos de esas lineas imaginarias forman la envoltura convexa.

Y como tu dices roman solo hay una envoltura convexa, y de las 2 formas se obtiene el mismo resultado. Pero según parece el primer método es la forma mas eficiente de hacerlo. Aunque lo de calcular distancias de un punto a una recta, o saber si algo esta dentro o fuera de un triángulo se me hace complicado de calcular. Aunque también puede que ser porque aquí ya son mas de las 4 de la mañana

[[Delphius]]

Cuando me doy con la sorpresa de que Roman y seoane ya estuvieron posteando, me puse a ver bien de se trata esto... no pensé que fuera tan complicado.

Ha decir verdad.. me quedo con el algoritmo de zoom mediante interpolacion lineal

Empezado por seoane

Aunque lo de calcular distancias de un punto a una recta, o saber si algo esta dentro o fuera de un triángulo se me hace complicado de calcular.

Tengo mis apuntes de Algebra a mano. Tendría que ver un poco el código que pusiste para ver como lo "acoplo" pero mis "luces" también me andan fallando (2PM).
Si logro hacerme un tiempito, a lo mejor le hecho un ojo.

[[seoane]]

Bueno, parece que con la luz del día veo las cosas mas claras. Aquí te dejo el programa, ahora si , con el algoritmo QuickHull, aunque puede que tengas que revisar la parte en la que se unen las dos envolturas, porque a veces falla. Yo por mi parte ya me doy por satisfecho

Bueno, aqui te queda:

[roman]

Insisto, ¿cuáles dos envolturas?

[[seoane]]

Empezado por roman

Insisto, ¿cuáles dos envolturas?

En el algoritmo se parte de dos puntos, los llamaremos A y B, el algoritmo primero se aplica sobre los puntos que se encuentran pro encima de la recta AB y luego sobre los puntos que se encuentran por debajo. De esta forma juntando la envoltura superior y la envoltura inferior, tenemos la envoltura completa.