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

← →
Дмитрий СС (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]

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

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

> Дмитрий СС (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 22:20) [36]

← →
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]
структуру таблицы и предполагаемые индексы можно увидеть?
или сферический конь в вакууме?)

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