Busqueda de punto 3D (x,y,z) en una lista de puntos
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?? |
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. :D 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"...) :D:D |
1 Archivos Adjunto(s)
Creo que con un pequeño ejemplo se ve mejor lo que quiero explicar...
|
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 |
Cita:
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-). Cita:
Cita:
|
La franja horaria es GMT +2. Ahora son las 15:54:11. |
Powered by vBulletin® Version 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Traducción al castellano por el equipo de moderadores del Club Delphi