Структура данных для быстрых запросов?

Я знаю, что могу использовать KD-Tree для хранения точек и быстрой итерации по части из них, которые близки к другой заданной точке. Мне интересно, есть ли что-то подобное для линий.

Учитывая набор линий L в3D (для хранения в этой структуре данных) и другая «строка запроса» q, я хотел бы иметь возможность быстро перебирать все строки в L, которые «достаточно близки» к q. Расстояние, которое я планирую использовать, - это минимальное евклидово расстояние между двумя точками u и v, где u - некоторая точка на первой линии, а v - некоторая точка на второй линии. Вычисление этого расстояния не является проблемой (есть хороший трюк с использованием перекрестного произведения).

Может быть, у вас есть хорошая идея или вы знаете, где искать документы, описания и т. Д.

ТИА, с.

Ответы на вопрос(2)

Ваш ответ на вопрос