|
|
|
карты +
|
|||
|---|---|---|---|
|
#18+
есть 1) множество точек 2) множество одинаковых квадратов 3) множество неодинаковых прямоугольников есть прямоугольник - запрос. стороны всех фигур параллельны осям координат. как проиндексировать таблицу с этим всем хозяйством (тремя множествами), чтобы выбор фигур, пересекающих запрос, был быстрый? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.10.2014, 20:32 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
tchingizкак проиндексировать таблицуА СУБД-то какая? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.10.2014, 18:32 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
Чингиз. Р+Дерево мать его так. Кури Р+Дерево. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.10.2014, 18:50 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
miksofttchingizкак проиндексировать таблицуА СУБД-то какая? будет sqlite ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.10.2014, 16:40 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
maytonЧингиз. Р+Дерево мать его так. Кури Р+Дерево. сенкс ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.10.2014, 16:43 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
Akina2D spatial geometry? и почему вы, евреи, всегда отвечаете вопросом на вопрос? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.10.2014, 16:43 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
Сведи все хранение к точкам. Если хотя бы один угол квадрата/прямоугольника попал в искомую область - значит фигура перекрывается искомой областью хотя бы частично. Дальше получается таблица Point (x int, y int, figure_id int) индекс по (x, y) если sqlite не умеет составные индексы - придется немного извратиться. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.10.2014, 16:58 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
а если все четыре угла прямоугольника не попадают в прямоугольник запроса? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.10.2014, 17:44 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
tchingizа если все четыре угла прямоугольника не попадают в прямоугольник запроса? Прямоугольник не попадет в результат запроса. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.10.2014, 19:11 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
Судя по вопросу предполагаю недопонимание "а чего дальше делать?" дальше Код: sql 1. 2. 3. 4. 5. где координаты углов прямоугольника запроса (x_start, y_start) и (x_end, y_end) и при условии x_start >= x_end и y_start >= y_end Модератор: ничего, что я поправил? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.10.2014, 19:29 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
Dima Tи при условии x_start >= x_end и y_start >= y_end попутал, <= надо, т.е. авторпри условии x_start <= x_end и y_start <= y_end ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.10.2014, 19:31 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
Dima Ttchingizа если все четыре угла прямоугольника не попадают в прямоугольник запроса? Прямоугольник не попадет в результат запроса. точно? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.10.2014, 20:21 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
tchingizточно? Точно. Не веришь - проверь - пишешь прогу которая генерит случайные наборы прямоугольников, делает выборку случайного размера и гоняешь все это пока не надоест или не получишь конкретный случай доказывающий обратное. Хотя тут достаточно почеркаться на бумажке чтобы понять что точно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.10.2014, 20:43 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
Не совсем точно, возможно 3 случая (см. картинку, красным запрос): 1. Прямоугольник запроса полностью перекрывает искомый (B) 2. Прямоугольник запроса частично перекрывает искомый (C) 3. Прямоугольник запроса целиком внутри искомого (А) Третий вариант не найдется. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.10.2014, 06:33 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
угу )) вспомнил. хватит одной проекции. Пусть на ось X л левая точка, п - правая для отбираемого отрезка, Л и П - левая и правая точки для запроса. п < Л или л > П - это те, которые не попадают в запрос. Отрицание это те, кто попадают: !(п < Л || л > П ) <=> (по законам Моргана) (!п < Л) && (!л > П ) <=> (п >= Л) && (л <=П). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.10.2014, 23:56 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
Как вариант: сделать два индекса по Л и по П, возможно sqlite сумеет оба задействовать. Только выражение лучше так переписать (поле оператор константа) чтобы парсер запроса не запутывать Код: sql 1. Если sqlite будет только один индекс брать, то польза от такого индекса под вопросом, возможно полный перебор без индекса с той же скоростью будет работать. PS Твою формулу можно под прямоугольники переделать: В - верх, Н - низ прямоугольника, в, н - верх, низ запроса Код: sql 1. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.10.2014, 08:31 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
ок. (поле, оператор, константа) это большие буквы - это параметры рамки, а маленькие - поля. Только не константа, а выражение без без использования полей. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.10.2014, 14:36 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
tchingizэто большие буквы - это параметры рамки, а маленькие - поля. Верно, я напутал, но не сильно, т.к. условие зеркально разворачивается Код: sql 1. или Код: sql 1. tchingizТолько не константа, а выражение без без использования полей. я к тому что в запросе это будет константа, т.е. допустим таблица Код: sql 1. запрос Код: sql 1. т.е. Л и П можно заменить на конкретные значения перед отправкой запроса. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.10.2014, 14:50 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. Рассматриваем случай 2) множество одинаковых квадратов (или прямоугольников) - пересекающихся по соседней границе, тайлы карты. Запрос больше тайлов по обеим координатам. Тогда по паре (В, Н) получаем список проекций горизонтальных линий между соседними тайлами на ось У, упородоченный по возрастанию (условные пиксели нумеруются от 0 к максимальному условному пикселю вниз), P == {pyO, py1, ..., pyN, такие что py0 - это верх первого, пересекающегося с запросом тайла (то есть, В >= py0 + ph ), а pyN - низ последнего пересекающегося с запросом тайла (Н <= pyN - ph ) }. Будем подбирать масштаб так, чтобы P.Length было небольшим (скажем от 3 до 13). Тогда запрос следующий запрос будет использовать указанный индекс i_tile1: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.10.2014, 15:14 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
*верх проекции на Y первого, пересекающегося с проекцией на Y запросом тайла (то есть, В >= py0 + ph ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.10.2014, 15:21 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
> В - верх, Н - низ прямоугольника, в, н - верх, низ запроса (В >= н) && (Н <= в) тока наоборот. Если пиксели возрастают вниз то (В <= н) && (Н >= в) -- - Сара, твой Абрам пошел налево. Сара, выглядывая из окна - когда он пошел направо, он пошел налево, а когда он пошел налево, это он пошел на работу ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.10.2014, 15:26 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
tchingiz Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. Это лишнее Код: sql 1. т.к. есть Код: sql 1. достаточно Код: sql 1. tchingizz.pw можно узнать перед этим запросом и оно будет константой Надо затестить скорость двумя запросами, из второго вообще выкинуть таблицу zoom. Есть подозрение что оптимизатор не поймет что (Л - z.pw) это константа и не использует индекс для проверки t.px >= Л - z.pw И еще вопрос, если отсюда выкинуть условие "and t.px <= П and (t.px + z.pw ) >= Л", то много выберется записей? т.е. Код: sql 1. 2. 3. если относительно немного, то выкинуть px из индекса и попробовать так Код: sql 1. 2. 3. 4. PS Надо план выполнения запроса смотреть, там будет видно какие индексы используются. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.10.2014, 16:19 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
Dima TЭто лишнее Код: sql 1. напутал, не лишнее, так хотел написать Код: sql 1. 2. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.10.2014, 16:23 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
ок >ЮИ еще вопрос, если отсюда выкинуть условие "and t.px <= П and (t.px + z.pw ) >= Л", то много выберется записей? т если карта существенно шире запроса, то много лишних. потестить надо, но карты лежат на флопиках, в парадоксе, насколько я помню. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.10.2014, 16:45 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
2а) множество одинаковых квадратов (или прямоугольников) области накрытия, половинками по вертикали накладывющиеся друг на друга - специальное накрытие карты, для каждого из масштабов. вид со стороны оси y Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. Для текущего масштаба М будем вынимать области из масштаба М-1 и выше до Ласт (пусть от 0 до 16, 16 масштабов достаточно). Чем выше номер масштаба, тем больше размер тайлов. список проекций увеличится в два раза от 6 до 26. В худшем случае Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. на 15 масштабе 14 26 15 13 из 38 точек. от 40 до 80 точек. получаем вместо 1 селекта объединение до 16 или последовательное выполнение до 16 селектов. поскольку индекс начинается с масштаба - запросы идут по возрастанию Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.10.2014, 17:27 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
3) множество неодинаковых прямоугольников надо рассовать прямоугольники по областям накрытия, в зависимости от размера прямоугольника. таблица областей ниразу не нужна, нужна таблица обьектов, которые рассортированы по областям накрытия, в разные масштабы, в зависимости от вхождения объекта. Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. и нужны функции а) пересчета реальных координат в условные пиксели LngToX: Int -> Int и AttToY: Int -> Int б) пересчета реальных координат в координаты областей накрытия SzToEnv: (Int >< Int) >< (Int >< Int) -> UChar >< (Int >< Int) по реальному левому верхнему и правому нижнему углу прямоугольника на местности получить масштаб и левый, верхний угол области в условных пикселях. Грубый отбор прямоугольников == 16 запросов меняются на такие .f Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. .^ дальше по первому запросу строим любезно подсказанное Майтоном РдеревоМатьЕгоТак с грубо отобранными прямоугольниками и их айдями, которое и используется для окончательного отображения в окне тайлов карты и считанных объектов в условных координатах. Если рамка запроса сдвигается и или меняется масштаб - то надо, в рДеревеМатьЕгоТак, стереть объекты (или не стереть если много памяти) не попадающие в новый запрос прямоугольники, а затем дочитать новые. фух ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.10.2014, 18:12 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
tchingiz поскольку индекс начинается с масштаба - запросы идут по возрастанию Думаю оптимизатору пофиг как они идут - как идут так и будет выполнять (отдельно каждый сам по себе) и склеивать результат. В данном запросе я бы точно выкинул zoom, т.е. сначала Код: sql 1. затем сгенерить запрос только из environs с кучей union. что-то конкретнее сказать не могу, плохо соображаю вечером, утром еще гляну. Не надо считать индекс панацеей для оптимизации, он хорошо ускоряет запросы если помогает выбрать 3-5% записей, если больше, то индекс может превратится в тормоз, т.к. полный скан таблицы быстрее, чем получить из индекса указатель на запись, проверить соответствие остальным неоптимизируемым критериям, получить из индекса указатель на следующую запись и т.д. Поэтому не всегда надо максимально подходящий индекс. Возможно менее полный индекс окажется быстрее. я про (zm, py) вместо (zm, py, px) В любом случае надо тестить на реальных данных, смотри план выполнения запроса, там видно что будет в реале: использован индекс или скан по таблице. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.10.2014, 18:49 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
http://gis-lab.info/projects/osm_dump/index.html конвертилка osm - sqlite3 если не лень, ткните пальцем как с опенстрит скачать карту, например, киевской области - ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.10.2014, 14:31 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
список прямоугольников, содержащих линии на карте киевской области http://agp1.hx0.ru/kbd/kr.zip и УССР http://agp1.hx0.ru/kbd/USSR.zip сами точки http://agp1.hx0.ru/kbd/kievRegion.1.zip http://agp1.hx0.ru/kbd/UkSSR.1.zip ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.12.2014, 13:31 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
ну, вот так выглядела в 1994 году ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.12.2014, 13:47 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
tchingizну, вот так выглядела в 1994 году Похоже на телёнка с крыльями. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.12.2014, 15:03 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
а мне медвеженка напоминал. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.12.2014, 16:47 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
maytonА чего кверху ногами? потому что на экране вертикальная координата увеличивается от нуля вниз. пысы оно еще пока зеркальное. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.12.2014, 16:48 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
Прям какой-то тест Роршаха. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.12.2014, 16:53 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
нагенерировали первую версию бд на sqlite из этих файлов на бд удалось протестировать схема спай (schemaSpy_5.0.0.jar ) генератор документации по схеме бд. в частности получилась такая картинка ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.05.2015, 18:02 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
SQLite летает аж свист стоит, с парадоксом из 96 года не сравнить. тут 25 тыщ линий и полмиллиона точек, может и не надо морочить голову с ускорением запросов? -- на sqlite вся бд отображалась за 22 секунды, из файловой системы за 10 мин, ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.06.2015, 17:59 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
в таблице sgmstr по паре (sgm, sgmPoint) пришлось индекс сделать, ибо Код: c# 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.06.2015, 18:04 |
|
||
|
карты +
|
|||
|---|---|---|---|
|
#18+
на бд с киевской областью (50к сегментов и 1 млн точек) тестировали скорость выполнения запросов по выбору точек из таблицы SgmStr либо из блоба таблицы Segment для разного количества точек в запросе ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.07.2015, 22:44 |
|
||
|
|

start [/forum/topic.php?all=1&fid=16&tid=1340983]: |
0ms |
get settings: |
5ms |
get forum list: |
13ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
135ms |
get topic data: |
6ms |
get forum data: |
1ms |
get page messages: |
41ms |
get tp. blocked users: |
1ms |
| others: | 195ms |
| total: | 401ms |

| 0 / 0 |
