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