Нумерация точек в системе координат.

← →
Кщд (2013-11-19 10:11) [40]

>jumping jack (19.11.13 08:41) [39]
структуру таблицы и предполагаемые индексы можно увидеть?
или сферический конь в вакууме?)

← →
jumping jack (2013-11-19 12:31) [41]

Кщд, поясните что именно вы не поняли?
структуру определит автор, но в ней явно будут X, Y, и индексное поле
индекс, конечно, один-единственный (а зачем их могло бы понадобиться несколько???)

← →
Кщд (2013-11-19 14:24) [42]

>jumping jack (19.11.13 12:31) [41]
структуру таблицы, в которой, конечно, будут X и Y(пусть, например, это будут X, Y и некое поле VAL), ф-лу для заполнения "индексного" поля и тип индекса - можно увидеть?
а также хотелось бы посмотреть типовой(ые?) запрос(ы)
пока есть мнение, что Вы не представляете, о чем говорите

← →
jumping jack (2013-11-19 14:59) [43]

Кщд, подожду мнения ТС
троллей много, а жизнь коротка
(извините)

← →
Кщд (2013-11-19 15:20) [44]

>jumping jack (19.11.13 14:59) [43]
согласен
пустая демагогия имеет свойство разбиваться о суровую конкретную техническую реальность

← →
jumping jack (2013-11-19 15:30) [45]

← →
Кщд (2013-11-19 22:58) [46]

>jumping jack (19.11.13 15:30) [45]
автор потерялся, жаль
мне, как человеку, работающему с нелепыми ГИС-системами, которые отчего-то решили построить на реляционной базе, очень интересна конкретная реализация Вашего подхода

буквально четыре строки: создание таблицы, ф-ла для вычисляемого поля, тип индекса(достаточно команды на создание) и типовой select(точнее - два: получение координат объекта(напр., по имени) и получение объектов по диапазону координат).

PS про нелепые системы - это не сарказм. ГИС-системы не нужно создавать на основе реляционных баз, ибо они дурно ложатся на плоские таблицы
PPS можно в синтаксисе любой СУБД, с которой Вы знакомы достаточно свободно

← →
Кщд (2013-11-19 23:01) [47]

*создание таблицы - либо нескольких, если надобно, конечно
если таблица одна, то вопрос про "select" координат по имени снимается

← →
jumping jack (2013-11-20 02:41) [48]

Кщд, ок!
сама формула для индексного поля (вычисляемого, но хранимого в таблице) получится большая и некрасивая, но принцип должен быть ясен: биты от беззнаковых целых координат Х и У чередуются по одному с сохранением порядка старшие-младшие: старший от Х, старший от У, следующий от Х и т.д.
т. е. индексное поле - целочисленного типа, беззнакового либо без использования знакового бита, я бы взял BIGINT (int64), но это на усмотрение автора
возможно, БД не поддерживает побитовые сдвиги и логику - тогда вычислять это нужно в своём приложении

тип индекса - самый простой, неуникальный, ASC[ending] (хотя и DESC скорее всего будет так же работать), по одному этому полю

получение точечных объектов по диапазону координат будет простым для любого из иерархических (суб)квадрантов -
select * from table where index_field between m and n
объяснение, что такое m и n заняло бы еще абзац-другой, так что просто ознакомьтесь с концепцией "quad-tree"
вкратце, это min и max значения индексных чисел, адресующих малейшие субквадранты в заданном квадранте
т.е. 0 или несколько последних _пар_ бит в m будут нулями, а в n - единичками

получение точечных объектов для любой прямоугольной области сложнее и может потребовать в запросе четырех разных диапазонов - (between m1 and n1) or (between m2 and n2) or (between m3 and n3) or (between m4 and n4) - по описанным в [39] причинам - и последующей фильтрацией лишних объектов (предположительно не на сервере)
все детали описывать не берусь
sapienti sat

впрочем, автор/ТС наверняка уже ушел прорубаться в дебрях встроенных гео-средств mssql, и наверное, правильно сделал - удачи ему там

← →
jumping jack (2013-11-20 02:47) [49]

*) под "пара бит будет единичками" имел в виду "оба бита в паре установлены"

← →
jumping jack (2013-11-20 03:41) [50]

на всякий случай, для тех, кто в танке, еще одно пояснение:
что собственно означают отдельные биты беззнакового целого числа?
а вот что: самый старший бит показывает, в какой половине области значений данного типа чисел данное число располагается - в "большой" половине или в "малой" - т.е. больше число, чем MaxVal div 2 или меньше/равно?
следующий бит показывает, в какой из четвертей (половин предыдущих половин) области значений находится число и так далее
по такому же принципу построены вышеописанные "quad-tree index numbers", только там вместо единичных битов, указывающих на половину, половину половины и т.д. - пары битов, указывающих на квадрант, субквадрант в предыдущем квадранте и т.д.

в случае, когда области значений координат Х и У одинаковы, пары битов, определяющих субквадранты, можно брать прямиком из битов одинакового старшинства значений координат - получится их чередование

сходным образом для трехмерных данных можно построить "octo-tree index", уже с тройками бит

а это примечание не для тех, кто "в танке":
если координаты - это широта и долгота, то есть смысл биты широты ставить по старшинству впереди соотв. битов долготы - если формировать запросы по половинкам субквадрантов, то такая разбивка будет оптимальнее (с удалением от экватора километраж одного градуса долготы уменьшается, а у градуса широты он всегда постоянный) - на половинки лучше разбивать именно широту

← →
jumping jack (2013-11-20 05:35) [51]

"у градуса широты он (километраж) всегда постоянный"
- не совсем, он немного увеличивается с удалением от экватора

← →
jumping jack (2013-11-20 13:32) [52]

а вот и пресловутая "формула":
unsigned long long expand_bits(unsigned long long n) { n = n & 0x0000ffff0000ffff | (n & 0xffff0000ffff0000) << 16; n = n & 0x00ff00ff00ff00ff | (n & 0xff00ff00ff00ff00) << 8; n = n & 0x0f0f0f0f0f0f0f0f | (n & 0xf0f0f0f0f0f0f0f0) << 4; n = n & 0x3333333333333333 | (n & 0xcccccccccccccccc) << 2; n = n & 0x5555555555555555 | (n & 0xaaaaaaaaaaaaaaaa) << 1; return n; } unsigned long long index_val = expand_bits(x) << 1 | expand_bits(y);

← →
Кщд (2013-11-20 14:43) [53]

>jumping jack (20.11.13 02:41) [48]
всего лишь просил четыре строки кода
увидел одну

понял, что при мелком разбиение крупных областей может не хватить и int64
а самое главное - такой подход неэффективен на порядке записей ~10^8
даже при использовании индекса по битовой маске

использование такого подхода снизит скорость модификации данных(перестройка индекса) и выборки данных - по причине выше

← →
jumping jack (2013-11-20 16:22) [54]

> может не хватить и int64
если меридиан длиной 20000 км разбить на 2^32 частей, получим ~ 5 мм - или вы антаресодезией там у себя занимаетесь?
> такой подход неэффективен
очень радует, что есть более эффективные - значит РСУБД все-таки на что-то еще годятся

Нумерация точек в системе координат. Найти похожие ветки