д0kСледующий вопрос ,
у вас есть улица длиной 5 км и шириной 30 м.
Как должно быть построено индексное хранение , что бы тыцнув
мышей в карту в любом месте улицы , получить ее название и координаты
всех перекрестков и названия пересекающих улиц.
Не вычитвая с диска квадрат 5км на 5 км со всеми его обьектами.Для этого надо индексировать не только шейпы, но и дополнительно их ключевые точки, при этом для прямых линий, "слишком протяжённых" в обычном зуме, надо дополнительно накидать точек вдоль линий (и при необходимости штриховку внутри них), а для объектов, слишком больших по площади в этом зуме, надо держать отдельные списки. Перед этим шейпам объектов разных типов назначаются, само собой, разные уровни "обычного зума" и разные уровни зума, при котором объекты вообще скрываются с карты. Тогда вы будете вычитывать квадрат с размером в полторы-две-три характерных ширины улицы, то есть для улицы это будет 50x50 метров.

Правда, тогда полезут большие вопросы производительности для мультилиний со слишком большим количеством точек, но я не уверен, что могу рассказать, как они решаются, не нарушив контракт :|

Но можно этого и не делать. Все улицы квадрата 5x5 километров уютно улягутся в памяти и дадут вам интерактивное время без фокусов. Вот когда всё очертание побережья мирового океана разбито на всего лишь три десятка мультиполигонов, и все изобаты разбиты так же, у вас карта раскрашена 20 слоями изобат с заливкой контуров, и вы даёте зум в Индонезию с её тясячами островов... одним неловким движением мыши в QGIS... вам придётся немножко подождать, прежде чем вы сможете сделать следующее движение карты :)

nikichaleд0kпропущено...



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

Нашел 2000 года статью
"Comparing Z-order B-tree and R-tree Family for Spatial Query Processing"

по http://webcache.googleusercontent.com/search?q=cache:CglmEYxoLcwJ:europa.nvc.cs.vt.edu/~ctlu/Publication/1998-2006/Z-order-B-tree.ps &cd=8&hl=ru&ct=clnk&gl=ru

и вывод, что Z-order B-tree индекс для пространственных выборок не хуже, чем R-tree, но проще.

А тут
http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves
джентлемен все заново изобрел только для точек, но в коментах ему объяснилиС 2000 года в СУБД поменялось почти всё :)

д0k Я так думаю ИМХО, с фунтаментальной точки зрения,
на определенном масштабе математика оптимального хранения
должна быть другая . Фракталы хороши только тогда, когда ты сначала рисуешь побережье, а потом приводишь местность в соотвествие с картой. Ну а вообще да, для мелкого хранения нужны уже не изобаты, а просто 3D-треугольная сетка. Одна беда --- если есть именно изобаты, да ещё заранее неизвестно, валидны ли они, то к 3d сетке без потерь данных не перейти.

д0kiv_an_ruпропущено...
Фракталы хороши только тогда, когда ты сначала рисуешь побережье, а потом приводишь местность в соотвествие с картой. Ну а вообще да, для мелкого хранения нужны уже не изобаты, а просто 3D-треугольная сетка. Одна беда --- если есть именно изобаты, да ещё заранее неизвестно, валидны ли они, то к 3d сетке без потерь данных не перейти.


Я не понял, что вы имеете ввиду( выделено).

Карта уже нарисована , ее нужно оптимально хранить и быстро искать участки .Тогда фракталы не нужны.