Sé que los kd se usan tradicionalmente para almacenar puntos, pero en su lugar quiero almacenar líneas. ¿Sería mejor dividir la línea en cada intersección con la división del árbol kd? ¿o almacenaría solo los puntos finales en kd-suficiente para encontrar al vecino más cercano?Cómo almacenar mejor las líneas en un árbol kd
Bueno, tienes que dividir las líneas en las intersecciones, de lo contrario te metes en problemas con los pesos de las hojas del árbol.
Por otro lado, si no usa SAH o cualquier otro algoritmo para atravesar el árbol, puede hacer lo que quiera con la idea original del árbol kd. Pero si es vinculado a algunos algoritmos tradicionales, tiene para dividir líneas. Tienes que hacerlo solo porque cada hoja del árbol tiene un peso (supongo que en tu caso depende de la longitud de las líneas).
Y si no divide las líneas, también obtendrá los pesos incorrectos de las hojas. No, si no divide las líneas, debe duplicarlas en ambas hojas a las que pertenece la línea.
¿Tienes que usar un árbol kd? Para primitivas extendidas, un bv-tree podría ser más eficiente.
El kd-tree en sí está diseñado para objetos punto. Ni siquiera para cajas, esferas o algo como esto. Creo que puede de alguna manera usar un árbol 6d que almacena minx, maxx, miny, maxy, minz, maxz; pero no estoy del todo seguro sobre cómo consultarlo correctamente.
El R*-tree (Wikipedia) podría ser una mejor opción aquí. Está realmente diseñado para objetos con una extensión espacial. Si buscas las publicaciones relacionadas, incluso experimentaron con diferentes aproximaciones de objetos complejos; por ejemplo, si vale la pena triangularizarlos, usar una circumsfera, un cuadro delimitador y, curiosamente, IIRC, el polígono de 5 esquinas proporciona el mejor rendimiento en algunos casos.
De todos modos, la familia de árboles * R podría ser una opción interesante.
Depende de lo que quieras hacer. Recuerde que una línea (segmento) es simplemente una colección de dos coordenadas, por lo que puede describirse por una sola coordenada, con el doble de dimensiones. Por lo tanto, podría almacenar líneas como puntos en un árbol kd de mayor dimensión. –
Estoy tratando de crear un campo de distancia con las líneas. Por lo tanto, utilizaré la funcionalidad vecina más cercana del kd-tree. Sin embargo, no quiero agregar más datos de los que tengo (los puntos finales de los segmentos de línea). – newDelete