|
|
|
Быстрый поиск в таблице
|
|||
|---|---|---|---|
|
#18+
Есть таблица объектов, расположенных на плоскости. Ее поля: ИД объекта, координатаХ, координатаУ - координаты пусть целочисленные. Задается некая точка своими координатами. Как устроить индексацию в таблице, чтобы максимально быстро найти ближайший объект к этой точке? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.04.2007, 18:39 |
|
||
|
Быстрый поиск в таблице
|
|||
|---|---|---|---|
|
#18+
Объекты не имеют размера? Тогда, думаю, вполне хватит двух индексов по X и Y. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.04.2007, 23:01 |
|
||
|
Быстрый поиск в таблице
|
|||
|---|---|---|---|
|
#18+
сравнивать расстояния до каждого. Линейная сложность. куда быстрее? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.04.2007, 04:36 |
|
||
|
Быстрый поиск в таблице
|
|||
|---|---|---|---|
|
#18+
Есть опыт решения таких задач, могу подсказать. Но чтобы лишнего не писать прошу уточнить задачу. Какие инструменты используете? Какую БД (если есть БД), на какой платформе будет исполнятся? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.04.2007, 11:39 |
|
||
|
Быстрый поиск в таблице
|
|||
|---|---|---|---|
|
#18+
имхо одним индексом не обойдешся в любом случае, можно например разбить плоскость на блоки размером deltaX*deltaY и проиндексировать по номерам блоков, поиск осуществлять итеративно, сначала по боку которому принадлежит точка потом по близлежащим. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.04.2007, 12:42 |
|
||
|
Быстрый поиск в таблице
|
|||
|---|---|---|---|
|
#18+
NafЕсть таблица объектов, расположенных на плоскости. Ее поля: ИД объекта, координатаХ, координатаУ - координаты пусть целочисленные. Задается некая точка своими координатами. Как устроить индексацию в таблице, чтобы максимально быстро найти ближайший объект к этой точке? http://en.wikipedia.org/wiki/R-tree ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.04.2007, 14:08 |
|
||
|
Быстрый поиск в таблице
|
|||
|---|---|---|---|
|
#18+
mayton http://en.wikipedia.org/wiki/R-tree "На рефлексах" я тоже хотел так ответить. А потом обратил внимание на формулировку задачи, и в результате появилась оговорка "если объект не имеет размеров"... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.04.2007, 14:10 |
|
||
|
Быстрый поиск в таблице
|
|||
|---|---|---|---|
|
#18+
softwarer"На рефлексах" я тоже хотел так ответить. А потом обратил внимание на формулировку задачи, и в результате появилась оговорка "если объект не имеет размеров"... Согласен. Вообще, способов индексирования пространственных данных - масса. Где-то я качал интересную статью про это дело. Если не забуду, завтра опубликую ссылку. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.04.2007, 14:49 |
|
||
|
|
start [/forum/topic.php?fid=16&fpage=165&tid=1346154]: |
0ms |
get settings: |
11ms |
get forum list: |
20ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
81ms |
get topic data: |
13ms |
get forum data: |
3ms |
get page messages: |
52ms |
get tp. blocked users: |
2ms |
| others: | 245ms |
| total: | 435ms |
| 0 / 0 |
