Algoritmo Quickhull

[juanchi]

Hola. Quisiera saber alguien me pudiera pasar el código del algoritmo Quickhull en Delphi. Desde ya muchísimas gracias.


Un saludo cordial

[dec]

Hola,

¿Lo quieres indentado a dos o cuatro espacios? Joroba.

Hombre, yo creo que esas no son formas de pedir ayuda.

[juanchi]

Hola. Disculpá Dec, pero la ayuda que pedí la hice en forma respetuosa. Mi problema es que no lo llego a comprederlo, es por eso es que pedí ayuda. Es poco el material que conseguí, si alguien me pudiera brindar se lo agradecería, sino, esta todo bien. Desde ya muchas gracias.

[Delphius]

Mi problema es que no lo llego a comprederlo, es por eso es que pedí ayuda. Es poco el material que conseguí,

¿Algoritmo Quickhull?
Es la primera vez que lo escucho... mejor dicho leo.

Si deseas implementarlo, es porque al menos tienes una vaga IDEA de lo que realiza y COMO.
Entre el material que conseguiste, ¿No explica COMO lo hace?¿Que estructuras de Datos usa?
En muchas ocasiones no está disponible el algoritmo... pero si una idea o breve descripción puntual de lo que realiza. Lo difìcil es "traducir" ese COMO. Y Creeme, te lo digo por experiencia... (y que actualmente estoy liandome con uno).

Si puedes exponer un poco la IDEA o el OBJETIVO DEL ALGORITMO... o un link... Tal vez te podríamos dar una mano. ¿No crees?

Saludos,

[roman]

Tampoco había oído del algoritmo antes pero resulta ser algo muy interesante. Se tiene un conjunto de puntos en el plano y se desea encontrar el menor polígono convexo que los contenga a todos (envoltura convexa). El primer enlace (http://www.cs.princeton.edu/~ah/alg_anim/version1/QuickHull.html) encontrado con Google da la descripción del problema y del algoritmo.

// Saludos

[seoane]

Bueno, primera vez que oigo hablar de este algoritmo. Pero guiándome por lo que dicen en esta pagina, he implementado el algoritmo para encontrar el hull (¿casco?) superior (o inferior segun se mire :) ), no creo que te sea muy difícil sacar el otro lado, yo ahora me voy para cama :p

No te aseguro que se ajuste al algoritmo pero parece que funciona. Bueno, aquí te lo dejo empaquetado para regalo :p


EDITO:

Quito el archivo adjunto, ya que no era correcto, deje otro zip un par de respuestas mas abajo. Ese si que creo que esta bien :D

[roman]

¿Cómo no estabas durante mi carrera para hacerme la tarea? :rolleyes:

// Saludos

[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 ... :p

[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 :p

[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:o

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 :p , 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 :D

Bueno, aqui te queda:

[roman]

Insisto, ¿cuáles dos envolturas?

[seoane]

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.

[ramosjairo]

Buenas se que es algo tarde, pero yo tengo ese algoritmo tanto la parte teórica como los diagramas ya que fueron parte de mi tesis, pero lo tengo programado en VisualLisp lenguaje nativo de Autocad. Puedo enviarlo si todavía lo necesitas y tratarías de entenderlo. Un Saludo....