Ich weiß, dass ich mithilfe eines KD-Baums Punkte speichern und schnell über einen Bruchteil davon iterieren kann, die sich in der Nähe eines anderen gegebenen Punkts befinden. Ich frage mich, ob es für Zeilen etwas Ähnliches gibt.

Gegeben eine Reihe von Zeilen L in3D (um in dieser Datenstruktur gespeichert zu werden) und eine weitere "Abfragezeile" q, möchte ich in der Lage sein, schnell alle Zeilen in L durchlaufen zu können, die "nahe genug" an q liegen. Der Abstand, den ich verwenden möchte, ist der minimale euklidische Abstand zwischen zwei Punkten u und v, wobei u ein Punkt auf der ersten Linie und v ein Punkt auf der zweiten Linie ist. Die Berechnung dieser Distanz ist kein Problem (es gibt einen netten Trick mit dem Kreuzprodukt).

Vielleicht habt ihr eine gute Idee oder wisst, wo ihr nach Papieren, Beschreibungen usw. suchen sollt.

TIA, s.