Busqueda de punto 3D (x,y,z) en una lista de puntos

[JF Sebastian]

Se trata de realizar (lo mas rapidamente posible) la busqueda de un punto en el espacio 3D dadas sus coordenadas x,y,z dentro de una lista de puntos 3D.
La busqueda secuencial es muy lenta.
Para una dimension la cosa parece facil con arboles binarios, pero para 3D???
Se podria aprovechar la funcionalidad de ordenacion de un TList para ello??

[Neftali [Germán.Estévez]]

Para estas cosas, yo siempre utilizo TStringList y la ordenación que ya posee.
Se trata de ir añadiendo los puntos a la TStringList (ordenada), a medida que los tienes.

La búsqueda en ese caso será dicotómica en lugar de secuencial.

Lo único que hay que tener en cuenta es que el formato con el que añadas los números debe ser "correcto" para que la búsqueda funcione. Me explico:

En lugar de añadir los números(puntos) así:
"1-34-2"
Añadirlos así:
"0001-0034-0002"
En tu caso, como se trata de puntos del espacio, y hay que tener en cuenta el signo, puedes hacer algo así:
"+0001/+0034/-0127"
Es decir se trata de estandarizar el formato, de forma que a la hora de buscar un número sepas exactamente lo que tienes que buscar.

Por ejemplo, si los has añadido con el último formato comentado, a la hora de buscar el punto (1,23,-4), deberás montar la cadena: "+0001,+0023,-0004" y buscarla.

No se si me explico (es que hoy estoy un poco "espesito"...)

[Neftali [Germán.Estévez]]

Creo que con un pequeño ejemplo se ve mejor lo que quiero explicar...

[JF Sebastian]

Muy bueno neftali,
Una cosa mas:
Los numeros en principio son de coma flotante y supongo que habria que escribirlos en formato de exponente. Y luego habria que tener en cuenta que el StringList deberia devolver el numero de la lista no ordenada para poder acceder a el en la estructura de datos original (un TList del que cuelgan las clases de cada punto 3D) supongo que habria que anadir dicho numero detras de la coordenada z...
Habria que limitar tambien el numero de decimales para evitar problemas de redondeo. Y tambien seria interesante el caso de devolver no el punto exacto sino tambien el mas proximo, pero creo que esto se tendria que hacer con arboles de busqueda.
Funcionaria la ordenacion en el caso del formato de coma flotante?

Un saludo

[Neftali [Germán.Estévez]]

Empezado por JF Sebastian

Los numeros en principio son de coma flotante y supongo que habria que escribirlos en formato de exponente. Y luego habria que tener en cuenta que el StringList deberia devolver el numero de la lista no ordenada para poder acceder a el en la estructura de datos original (un TList del que cuelgan las clases de cada punto 3D) supongo que habria que anadir dicho numero detras de la coordenada z...

El formato original de los número da igual, siempre y cuando el formato que tú crees para adaptarlos sea estandard de forma que la ordenación funcione correctamente.
En cuanto a añadir más datos, como tú comentas, puede hacerse al final y si no recuerda que cada elemento del TStringList tiene un puntero en el que puedes almacenar más información (colgar objetos e incluso yo en alguna ocasión he utilizado ese puntero para almacenar directamente el entero correspondiente al índice de otra lista -esto tal vez sea lo más sencillo-).

Empezado por JF Sebastian

Habria que limitar tambien el numero de decimales para evitar problemas de redondeo. Y tambien seria interesante el caso de devolver no el punto exacto sino tambien el mas proximo, pero creo que esto se tendria que hacer con arboles de busqueda.

Para el tema del más próximo con esta estructura sólamente está claro que no te va a servir. Lo que ya no tengo claro es si ese dato vale la pena almacenarlo o calcularlo en el momendo necesario.

Empezado por JF Sebastian

Funcionaria la ordenacion en el caso del formato de coma flotante?

La ordenación funcionará siempre; Dependerá de cómo estés almacenando tú los datos de los puntos.