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

← →
Дмитрий СС (2013-11-17 20:15) [0]

Предположим есть двухмерная система координат, где координаты - целые числа.
Всевозможные точки необходимо пронумеровать. Должно быть некое соответствие:
n = f(x,y), где
x, y - координаты точки (целые).
n - номер этой точки.

Каждой точке соответствует один номер, каждому номеру - одна точка.
Должна быть возможность получить координаты по номеру точки (расчетом, а не перебором).
А также, важно, чтобы номер возрастал по мере отдаления точки от центра координат (поэтому, упаковка n=x*k+y, (где k - некое большое число) не подойдет).
Желательно, чтобы подсчет был математически простым.
Я помню мы это проходили в институте, знаю, что великие математики уже решили эту задачу, но не помню даже по каким словам искать.
Буду благодарен за направления для поиска! Спасибо.

← →
Kerk © (2013-11-17 20:39) [1]

Отрицательные координаты могут быть?

← →
Дмитрий СС (2013-11-17 20:42) [2]

> Отрицательные координаты могут быть?

да

← →
Павиа (2013-11-17 21:25) [3]

По-спирали из центра пронумеруй.

← →
Styx (2013-11-17 21:26) [4]

Ну дык по спирали намотать... вроде очевидно. Или хочется готовую формулу?

← →
Дмитрий СС (2013-11-17 21:37) [5]

> Или хочется готовую формулу?

Конечно хочется, зачем велосипед изобретать. К тому же может быть есть что-то оптимальнее чем "по-спирали"

← →
картман © (2013-11-17 21:46) [6]

x,y: smallint;
n: int64;
n = ( ( (x^2 * y^2) shl 32) ) or (y shl 16) or x;

← →
картман © (2013-11-17 21:50) [7]

> (x^2 * y^2) shl 32)

(x^2 + y^2) shl 32)

← →
Дмитрий СС (2013-11-17 22:02) [8]

> картман

Так это ж тоже самое что и
n=x*k+y

Вот в упрощенном виде:
n = x shl 32 + y

Хотя изучая материал в интернете я уже не думаю, что это такая уж плохая идея.

← →
Styx (2013-11-17 22:44) [9]

> n=x*k+y

Это же не удовлетворяет требовантю

> чтобы номер возрастал по мере отдаления точки от центра
> координат

Или оно уже не важно, коли никто за Вас формулу для спирпли придумывать не стал? ;-)

← →
[ВладОшин] © (2013-11-17 22:45) [10]

> Так это ж тоже самое что и
> n=x*k+y
>
> Вот в упрощенном виде:
> n = x shl 32 + y

а где тут

> А также, важно, чтобы номер возрастал по мере отдаления
> точки от центра координа

← →
Дмитрий СС (2013-11-17 22:50) [11]

Последним двух авторам:
Это плата за простоту.

Те способы, которые я нашел - они в лоб и слишком сложны.

А n = x shl 32 + y проста, но не все условия выполняются. придется выбирать, если не найду чего то более простого

← →
Dimka Maslov © (2013-11-17 22:52) [12]

1. Номер должен быть уникальным
2. Номер должен возрастать по мере удаления от центра
3. Из номера можно получить координаты
4. Возможны отрицательные координаты

По моему это взаимоисключающие параграфы

← →
Дмитрий СС (2013-11-17 22:54) [13]

не вижу противоречий, что именно?

← →
[ВладОшин] © (2013-11-17 22:54) [14]

Ну, задача твоя, тебе видней :)

А может сменить систему отсчета?
Пусть Х - расстояние до центра, а Y - угол с осью.
В Х уже заложено расстяние до центра :)
а У всегда выражается целочисленной дробью.

← →
Sha © (2013-11-17 23:03) [15]

> важно, чтобы номер возрастал по мере отдаления точки от центра координат

как будем нумеровать равноудаленные точки?

← →
картман © (2013-11-17 23:08) [16]

> Должна быть возможность получить координаты по номеру точки
> (расчетом, а не перебором).

а откуда такое ограничение? Ну, что мешает завести ассоциативный массив?

← →
Dimka Maslov © (2013-11-17 23:13) [17]

> Дмитрий СС (17.11.13 22:54) [13]

Как должны соотноситься друг с другом номера точек (-99, 99) и (99, -100), которые почти равноудалены от центра? Так что, либо возрастание по мере удаления от центра, либо возможность восстановления, либо простота. Теорему вон Ферма сколько лет доказывали по принципу "должно быть просто и понятно"?

← →
Дмитрий СС (2013-11-18 02:02) [18]

> как будем нумеровать равноудаленные точки?

недалеко отстоящими значениями. Это не принципиально.

Идея в том, что если расширить тип N до, скажем Int64 мы должны увеличить площадь охватываемого поля.

> а откуда такое ограничение? Ну, что мешает завести ассоциативный
> массив?

Есть же разница: массив с таскать или по формуле считать )

← →
wicked © (2013-11-18 02:22) [19]

вот ссамое близкое решение твоей задачи

> [ВладОшин] © (17.11.13 22:54) [14]
> Ну, задача твоя, тебе видней :)
>
> А может сменить систему отсчета?
> Пусть Х - расстояние до центра, а Y - угол с осью.
> В Х уже заложено расстяние до центра :)
> а У всегда выражается целочисленной дробью.

на n условия целочисленности нет?
тогда выражать n = int(r) + phi/360 (r - радиус, phi - в градусах)

либо, если будет много точек возле начала координат, то заменить int(r) на int(r * 1000), чтобы близколежащие точки не путались

← →
jumping jack (2013-11-18 08:05) [20]

упаковка n=расстояние*n+x*k+y (n>k)
пересчет в полярную с. к. не обеспечит абсолютной точности обратного пересчета

← →
jumping jack (2013-11-18 08:10) [21]

если не будет влезать - от y можно оставить только знак и пару младших бит (или от х)

← →
Sha © (2013-11-18 09:41) [22]

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

Все стесняются спросить, тогда придется мне: а зачем это надо?

← →
Дмитрий СС (2013-11-18 12:33) [23]

> Sha © (18.11.13 09:41) [22]

Есть таблица с объектами с их координатами (планируемый разброс координат +/-10E8). Необходимо построить такой индекс, с помощью которого можно извлечь все объекты из любой небольшой прямоугольной области (к примеру 1000х500). Поскольку от индекса по координатам толку не будет я решил сделать следующее:
разбить плоскость на квадраты (или секторы, для удобства размером 1024х1024) и каждый квадрат пронумеровать. По этому номеру проиндексировать все объекты.
Когда потребуется поиск по области, я вычисляю в каких квадратах она лежит и делаю запрос с условием sector in (...) and x between .... and y between. Тем самым очень сильно сужаю область поиска.

Сейчас я понимаю что нумерация по спирали неэффективная, т.к. расчеты будут очень сложными. Поэтому сектора я буду нумеровать парами чисел M и N: порядковые номера по горизонтали и по вертикали соответственно), а базе это будет bigint, рассчитанный по формуле Sector=(M shl 32) or N. Формула указана на вскидку.

Всем спасибо!

← →
[ВладОшин] © (2013-11-18 13:38) [24]

> Поскольку от индекса по координатам толку не будет

Сомневаюсь..

пробовал?
если четыре индекса: [х], [у], [x][y], [y][x] и если целочисленные - думаю, поможет хорошо.

← →
Дмитрий СС (2013-11-18 13:42) [25]

> [ВладОшин] © (18.11.13 13:38) [24]

Запрос к примеру:
SELEC * FROM objects WHERE (x BETWEEN 10000 AND 11000) AND (y BETWEEN -6000 AND -5000)

И какой индекс использовать?

← →
[ВладОшин] © (2013-11-18 13:48) [26]

> 10E8

ух ты, не обратил внимания
тогда не надо [x][y], [y][x] :)

> И какой индекс использовать?

а СУБД какая?

← →
MBo © (2013-11-18 14:02) [27]

см. kd-tree, r-tree
Как с базами данных это сочетается, не знаю

← →
Дмитрий СС (2013-11-18 14:06) [28]

> [ВладОшин] © (18.11.13 13:48) [26]
>

Не важно какая СУБД, принцип индексирования все-равно один и тот же.
Но если для примера: mysql. Можете взять и mssql.

> ух ты, не обратил внимания

Это не значит что объектов столько, просто разброс координат такой:)

← →
Дмитрий СС (2013-11-18 14:07) [29]

> MBo © (18.11.13 14:02) [27]

Спасибо, прочту!

← →
Павиа (2013-11-18 14:12) [30]

Тогда за одно советую ещё прочитать "в ведение в вычислительную геометрию".

← →
[ВладОшин] © (2013-11-18 14:36) [31]

> Дмитрий СС (18.11.13 14:06) [28]

Ok, mssql.
Проверю дома одну мыслю.

← →
Кщд (2013-11-18 14:59) [32]

>Дмитрий СС (18.11.13 14:06) [28]
1. СУБД - важна, ибо в некоторых есть поддержка гео-данных и, соответственно, возможность индексирования с массой полезнах ф-ция(расстояние между объектами, вхождение одного объекта в другой и пр.);
2. В случае "плоских" данных поможет индекс по [x, y];
3. Идея с разбиением на бОльшие области и подразбиением каждой из них на меньшие - не нова и правильна при большом кол-ве объектов.
Не ясно, зачем нужна ф-ция нумерации, когда это решается след. алгоритмом:
1. Найти большУю область, в которой лежит точка;
2. Найти её подобласть, к которой точка принадлежит;
3. Повторить (2), если имеются меньшие подобласти.

Создаёте либо обычный индекс, либо индекс по ф-ции вхождения точки в область.

← →
Кщд (2013-11-18 14:59) [33]

полезнах))

← →
jumping jack (2013-11-18 20:39) [34]

http://technet.microsoft.com/ru-ru/library/bb964712(v=sql.105).aspx

← →
[ВладОшин] © (2013-11-18 21:14) [35]

а каковы реальные объемы?
сколько объектов?

← →
Дмитрий СС (2013-11-18 22:20) [36]

> [ВладОшин] © (18.11.13 21:14) [35]

10-100 млн. такой порядок.

> jumping jack (18.11.13 20:39) [34]

Очень круто.

← →
jumping jack (2013-11-19 05:44) [37]

если вдруг захочется свой велосипед делать - можно генерировать число для индексации по типу quad-tree: допустим, карта квадратная; старшие 2 бита числа определяют квадрант (квадрат в 1/4 от большего) на этой карте - Юго-Западный, СЗ, СВ или ЮВ; следующие 2 бита помладше - субквадрант внутри предыдущего и так далее

тогда 1 запрос c WHERE ... BETWEEN выдаст точки внутри любого из иерархических субквадрантов (но не любого произвольного прямоугольника - тут нужны либо несколько запросов, либо (наверное, быстрее) самому отфильтровать лишние точки из наименьшего полностью включающего нужную область субквадранта)

← →
jumping jack (2013-11-19 05:54) [38]

иными словами, этот quad-tree-index легко получить так: биты координат X и Y должны в индексном числе чередоваться: старший от X, старший от Y, следующие от X и Y и т. д. (самые младшие наверное не нужны, да и не войдут)
получается, все довольно легко и просто!

← →
jumping jack (2013-11-19 08:41) [39]

p.s. видимо, стоит закладываться на 4 запроса: например, область в самом центре карты не попадает полностью вообще ни в какой 1 субквадрант, но покроется 4-мя достаточно маленькими субквадрантами

ну и от минуса в координатах при рассчете индекса придется избавиться (добавить константу)

← →
Кщд (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 мм - или вы антаресодезией там у себя занимаетесь?
> такой подход неэффективен
очень радует, что есть более эффективные - значит РСУБД все-таки на что-то еще годятся

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