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

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

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

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

ТИА, с.

 Thomas30 сент. 2009 г., 17:43
Это расстояние всегда равно 0, если линии не параллельны. Или вы говорите о линиисегменты?
 sellibitze30 сент. 2009 г., 17:47
Это нене имеет значения на самом деле. Если это поможет, я мог бы сделать это отрезками. Но линии бесконечной длины тоже подойдут. Я неНе ожидайте, что результат изменится. В настоящее время я параметризирую свои линии двумя точками и ожидаю, что точки u / v будут на этих отрезках.
 Thomas30 сент. 2009 г., 17:49
Интересный вопрос, кстати.
 Thomas30 сент. 2009 г., 17:49
Извините, я пропустил3D» часть. Теперь все ясно.
 Matthieu M.30 сент. 2009 г., 17:48
Хм, в 3D две линии не могут пересекаться друг с другом, не будучи параллельными, поскольку они могут быть в разных планах.

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

Решение Вопроса

дексации в дисковых системах баз данных - этоR-Tree, Это'немного сложнее в реализации, чем KD-Tree, но этоОбычно считается, что быстрее и не имеет проблем с индексацией линий и полигонов.

 sellibitze01 окт. 2009 г., 11:19
+1. Чтобы назвать другое преимущество: такая структура данных нене требует "расщепляющие элементы " (избыточность), потому что узлы ограничительные рамки могут перекрываться - очень похоже на свободную октру.
 sellibitze01 окт. 2009 г., 18:24
Принято за предложение другой структуры данных, которая нене требует разделения объектов

Это'Можно построить дерево KD, которое работает на примитивах, а не на точках. Многие трассировщики лучей делают это, чтобы тестирование треугольников было намного быстрее. Лучшее описание явидел, что в этомучебник по трассировке лучей.

Потенциально более быстрое, хотя и не на 100% точное решение, состоит в том, чтобы просто сохранить список точек на сегмент линии и вставить их в стандартное дерево KD на основе точек. Найдите ближайшие точки, затем пометьте их сегментом линии и используйте его для получения ближайших линий. Это'с сырой, но часто очень быстро по сравнению с другими вариантами. "трюк» заключается в том, чтобы найти правильный баланс между большими промежутками между точками вдоль сегмента (быстрее) и разбить сегмент на большее количество точек (медленнее, но более точно).

 sellibitze30 сент. 2009 г., 18:03
+1 Спасибо за ваши предложения. Я'Я должен проверить вашу ссылку и подумать об этом.
 sellibitze01 окт. 2009 г., 11:11
Вместо того, чтобы хранить точки в каждом листе, я мог бы хранить отрезки и разделять эти отрезки. В любом случае я бы закончил тем, что сохранил строку как-то излишне. Может быть, другие структуры данных являются более подходящими (свободный октри, R-дерево, ...)

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