Wiem, że mogę użyć drzewa KD do przechowywania punktów i szybko iterować na ułamku z nich, które są blisko innego danego punktu. Zastanawiam się, czy jest coś podobnego dla linii.

Podany zestaw linii L w3D (do przechowywania w tej strukturze danych) i innej „linii zapytania” q, chciałbym móc szybko iterować przez wszystkie linie w L, które „są wystarczająco blisko” do q. Odległość, którą zamierzam wykorzystać, to minimalna odległość euklidesowa między dwoma punktami u i v, gdzie u jest pewnym punktem na pierwszej linii, a v jest pewnym punktem na drugiej linii. Obliczanie tej odległości nie jest problemem (jest fajna sztuczka dotycząca produktu krzyżowego).

Może macie dobry pomysł lub wiecie, gdzie szukać dokumentów, opisów itp ...

TIA, s.