ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Проектирование БД [игнор отключен] [закрыт для гостей] / Таблица расстояний между точками
15 сообщений из 15, страница 1 из 1
Таблица расстояний между точками
    #37968387
design21
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
design21
Гость
В БД хранится список точек с географическими координатами. Необходимо часто решать следующие задачи:

1. Добавлять новые точки.
2. Находить список точек в радиусе X от заданной.

Первым в голову пришло такое решение. Пожалуйста покритикуйте, если может быть придет в голову что-то лучшее.

Имеется функция которая вычисляет расстояние по паре координат:
F_dist(Lat1,Long1,Lat2,Long2)

Мне прило в голову что логично будет не выислять на лету расстяония между каждой парой точек, а создать таблицу расстояний между ними. Вот так

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
CREATE TABLE  Points (
PointId INT PRIMARY KEY,
Lat DECIMAL(20,10),
Long DECIMAL(20,10))

CREATE TABLE Distances (
A INT NULL REFERENCES Points(PointId),
B INT NULL REFERENCES Points(PointId),
Dist FLOAT)



В таблице Distances хранятся расстояния между точками. Строки не дублируются: т.е. если есть запись A - B, то записи B - A быть не должно.

Чтобы добавить точку механизм следующий:
Добавляем точку в таблицу Points и запоминаем ее PointId и координаты во временную таблицу #NewPoints.
Т.е. в #NewPoints после вставки будет одна строка.

Код: sql
1.
2.
3.
4.
CREATE TABLE #NewPoints (
PointId INT,
Lat DECIMAL(20,10),
Long DECIMAL(20,10))



строки для вставки в Distances получаем так:

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
INSERT INTO Distances (A,B,Dist)
SELECT n.PointId,old.PointId, F_dist(Old.Lat,OldLong,n.Lat,n.Long)
FROM #NewPoints n
CROSS JOIN (
SELECT PointId = A FROM Distances 
UNION
SELECT PointId = B FROM Distances) old
JOIN Points coord_old ON old.PointId = coord_old.old.PointId



Механизм для поиска точек в радиусе такой:

Пусть надо найти точки в радиусе R от точки X.
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
SELECT PointId
FROM
(SELECT A PointId
FROM Distances 
WHERE Dist < R AND (A=X OR B=X) 
UNION
SELECT B PointId
FROM Distances 
WHERE Dist < R AND (A=X OR B=X))


Меня как-то смущает обилие UNION. Может быть можно как-то по-другому?
...
Рейтинг: 0 / 0
22.09.2012, 20:00
| Ответить | Цитировать | Написать  
Таблица расстояний между точками
    #37968398
Ы
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Ы
Гость
design21, ваша СУБД не умеет работать с геометрическими типами данных (point, box, line и т.п.) напрямую?
...
Рейтинг: 0 / 0
22.09.2012, 20:29
| Ответить | Цитировать | Написать  
Таблица расстояний между точками
    #37968407
design21
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
design21
Гость
я пока не выбрал базу, но скорее всего это будет MySQL 5
...
Рейтинг: 0 / 0
22.09.2012, 20:53
| Ответить | Цитировать | Написать  
Таблица расстояний между точками
    #37968437
Фотография Роман Дынник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Роман Дынник
Участник
design21,

Почитайте теорию графов. Все эти задачи ей покрываются.
...
Рейтинг: 0 / 0
22.09.2012, 22:08
| Ответить | Цитировать | Написать  
Таблица расстояний между точками
    #37968475
Gallagher
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gallagher
Гость
Полный граф получается, если хранить расстояние для каждой пары. Количество не смущает?
...
Рейтинг: 0 / 0
22.09.2012, 23:37
| Ответить | Цитировать | Написать  
Таблица расстояний между точками
    #37968479
Gallagher
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gallagher
Гость
Какое кол-во точек планируете хранить?
Как часто будут добавляться новые / изменяться старые?
Как часто будут запрашивать точки в радиусе от?
...
Рейтинг: 0 / 0
22.09.2012, 23:43
| Ответить | Цитировать | Написать  
Таблица расстояний между точками
    #37968481
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> я пока не выбрал базу, но скорее всего это будет MySQL 5

Лучше замени на Postgres, он поддерживает GEO, и там ещё
кажется есть специальные индексы пространственные.
Так что решение этой задачи лежит не в выдумывании структур
и запросов к ним, которые никогда не будут работать,
а в правильном выборе СУБД, которая это умеет.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
22.09.2012, 23:55
| Ответить | Цитировать | Написать  
Таблица расстояний между точками
    #37969220
design21
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
design21
Гость
думаю что добавляться точки будут штук по 10 в день, может и больше в перспективе, сложно сказать - это веб-сайт для поиска попутчиков. при добавлении поездки добавляются точки, в самом начале я точек сам добавлять не планирую - будут добавляться пользователями.
...
Рейтинг: 0 / 0
24.09.2012, 02:01
| Ответить | Цитировать | Написать  
Таблица расстояний между точками
    #37969271
tanglir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tanglir
Участник
MasterZivЛучше замени на Postgres+1
Хотя и в 5-м мускле есть геомтипы. Правда, только для (уже превращающихся в окаменелость) MyISAM-таблиц.
...
Рейтинг: 0 / 0
24.09.2012, 07:36
| Ответить | Цитировать | Написать  
Таблица расстояний между точками
    #37969543
хранить или нет
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
хранить или нет
Гость
смотря для каких задач.

для транспортных задач эффективное "расстояние" не исчисляется [только] из координат, и более того - анизотропно
Код: sql
1.
 расстояние(А,Б)<>расстояние(Б,А)


т.е. хранить граф "расстояний" - естественно

для геометрических же - смотря от того, что вы хотите нагрузить. есть свободные вычислительные мощности - нагружайте процессор (не храните расстояния). туго с ними - тормозите с дисковыми операциями.
...
Рейтинг: 0 / 0
24.09.2012, 11:07
| Ответить | Цитировать | Написать  
Таблица расстояний между точками
    #37969640
Cane Cat Fisher
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Cane Cat Fisher
Участник
design21,

Проектирование калькулятора для расчета стоимости доставки товаров по стране.
...
Рейтинг: 0 / 0
24.09.2012, 11:56
| Ответить | Цитировать | Написать  
Таблица расстояний между точками
    #37970139
Ы
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Ы
Гость
design21,

привяжитесь к гуглемапсу и не мучайтесь
...
Рейтинг: 0 / 0
24.09.2012, 16:08
| Ответить | Цитировать | Написать  
Таблица расстояний между точками
    #37970487
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
design21 ,
При N точках, количество расстояний будет N*(N-1), ну или N*(N-1)/2, если не дублировать расстояния A-B и B-A.
Квадратичная зависимость имеет свойство быстро нарастать ;) так что сам оцените, как у вас будет с кол-вом данных.
Конечно, это ускорит поиск, но (имхо), надо поэкспериментировать на данных, близких к реальньм.
...
Рейтинг: 0 / 0
24.09.2012, 19:54
| Ответить | Цитировать | Написать  
Таблица расстояний между точками
    #37971572
Кот Матроскин
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кот Матроскин
Участник
Не стал бы хранить рассчитанные расстояния
1. Как уже сказали, зависимость квадратичная, для 10 тыс. точек будет около 50 миллионов расстояний
2. точки в радиусе R от заданной (x, y) - это те, которые попадают в круг радиусом R с центром в (x, y). Отобрать точки, которые попадают в квадрат, описанный вокруг этого круга - тривиально просто по координатам. А для этих (немногих) точек не так уж дорого и рассчитать функцию.
...
Рейтинг: 0 / 0
25.09.2012, 15:41
| Ответить | Цитировать | Написать  
Таблица расстояний между точками
    #37972277
Volochkova
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Volochkova
Участник
S.G.design21 ,
При N точках, количество расстояний будет N*(N-1), ну или N*(N-1)/2, если не дублировать расстояния A-B и B-A.
Квадратичная зависимость имеет свойство быстро нарастать ;) так что сам оцените, как у вас будет с кол-вом данных.
Конечно, это ускорит поиск, но (имхо), надо поэкспериментировать на данных, близких к реальньм.

Первый же знак одностороннее движение и расстояния A-B уже не равно B-A.
А таких "знаков" бывает много, и реки и круговые и т.п.
...
Рейтинг: 0 / 0
26.09.2012, 06:02
| Ответить | Цитировать | Написать  
15 сообщений из 15, страница 1 из 1
Форумы / Проектирование БД [игнор отключен] [закрыт для гостей] / Таблица расстояний между точками
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=32&msg=37970487&tid=1541537]:
 0ms
get settings:
 9ms
get forum list:
 9ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 138ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 33ms
get tp. blocked users:
 1ms
others: 197ms
total:  400ms
созд. / загр.: 400ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]