|
|
|
карты +
|
|||
|---|---|---|---|
|
#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 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=38777674&tid=1340983]: |
0ms |
get settings: |
10ms |
get forum list: |
15ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
175ms |
get topic data: |
11ms |
get forum data: |
3ms |
get page messages: |
81ms |
get tp. blocked users: |
2ms |
| others: | 245ms |
| total: | 548ms |

| 0 / 0 |
