powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / карты +
25 сообщений из 47, страница 1 из 2
карты +
    #38773775
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
есть
1) множество точек
2) множество одинаковых квадратов
3) множество неодинаковых прямоугольников

есть прямоугольник - запрос.
стороны всех фигур параллельны осям координат.
как проиндексировать таблицу с этим всем хозяйством (тремя множествами), чтобы
выбор фигур, пересекающих запрос, был быстрый?
...
Рейтинг: 0 / 0
карты +
    #38773780
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
2D spatial geometry?
...
Рейтинг: 0 / 0
карты +
    #38776581
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
tchingizкак проиндексировать таблицуА СУБД-то какая?
...
Рейтинг: 0 / 0
карты +
    #38776601
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Чингиз. Р+Дерево мать его так. Кури Р+Дерево.
...
Рейтинг: 0 / 0
карты +
    #38777662
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
miksofttchingizкак проиндексировать таблицуА СУБД-то какая?


будет sqlite
...
Рейтинг: 0 / 0
карты +
    #38777671
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
карты +
    #38777672
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЧингиз. Р+Дерево мать его так. Кури Р+Дерево.
сенкс
...
Рейтинг: 0 / 0
карты +
    #38777674
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Akina2D spatial geometry?
и почему вы, евреи, всегда отвечаете вопросом на вопрос?
...
Рейтинг: 0 / 0
карты +
    #38777710
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сведи все хранение к точкам. Если хотя бы один угол квадрата/прямоугольника попал в искомую область - значит фигура перекрывается искомой областью хотя бы частично.

Дальше получается таблица Point (x int, y int, figure_id int)

индекс по (x, y) если sqlite не умеет составные индексы - придется немного извратиться.
...
Рейтинг: 0 / 0
карты +
    #38777790
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
а если все четыре угла прямоугольника не попадают в прямоугольник запроса?
...
Рейтинг: 0 / 0
карты +
    #38777911
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
tchingizа если все четыре угла прямоугольника не попадают в прямоугольник запроса?
Прямоугольник не попадет в результат запроса.
...
Рейтинг: 0 / 0
карты +
    #38777922
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Судя по вопросу предполагаю недопонимание "а чего дальше делать?"
дальше
Код: sql
1.
2.
3.
4.
5.
select distinct figure_id 
from Point 
where 
        (x between x_start and x_end) 
  and (y between y_start and y_end)


где координаты углов прямоугольника запроса (x_start, y_start) и (x_end, y_end)
и при условии x_start >= x_end и y_start >= y_end



Модератор:
ничего, что я поправил?
...
Рейтинг: 0 / 0
карты +
    #38777923
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima Tи при условии x_start >= x_end и y_start >= y_end
попутал, <= надо, т.е.
авторпри условии x_start <= x_end и y_start <= y_end
...
Рейтинг: 0 / 0
карты +
    #38777953
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima Ttchingizа если все четыре угла прямоугольника не попадают в прямоугольник запроса?
Прямоугольник не попадет в результат запроса.
точно?
...
Рейтинг: 0 / 0
карты +
    #38777961
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
tchingizточно?
Точно. Не веришь - проверь - пишешь прогу которая генерит случайные наборы прямоугольников, делает выборку случайного размера и гоняешь все это пока не надоест или не получишь конкретный случай доказывающий обратное. Хотя тут достаточно почеркаться на бумажке чтобы понять что точно.
...
Рейтинг: 0 / 0
карты +
    #38778115
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Не совсем точно, возможно 3 случая (см. картинку, красным запрос):
1. Прямоугольник запроса полностью перекрывает искомый (B)
2. Прямоугольник запроса частично перекрывает искомый (C)
3. Прямоугольник запроса целиком внутри искомого (А)

Третий вариант не найдется.
...
Рейтинг: 0 / 0
карты +
    #38782344
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
угу ))
вспомнил. хватит одной проекции. Пусть на ось X
л левая точка, п - правая для отбираемого отрезка, Л и П - левая и правая точки для запроса.

п < Л или л > П - это те, которые не попадают в запрос.
Отрицание это те, кто попадают:
!(п < Л || л > П ) <=> (по законам Моргана) (!п < Л) && (!л > П ) <=>
(п >= Л) && (л <=П).
...
Рейтинг: 0 / 0
карты +
    #38782348
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
карты +
    #38782442
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Как вариант: сделать два индекса по Л и по П, возможно sqlite сумеет оба задействовать.
Только выражение лучше так переписать (поле оператор константа) чтобы парсер запроса не запутывать
Код: sql
1.
(П >= л) && (Л <= п)


Если sqlite будет только один индекс брать, то польза от такого индекса под вопросом, возможно полный перебор без индекса с той же скоростью будет работать.

PS Твою формулу можно под прямоугольники переделать: В - верх, Н - низ прямоугольника, в, н - верх, низ запроса
Код: sql
1.
(П >= л) && (Л <= п) && (В >= н) && (Н <= в)
...
Рейтинг: 0 / 0
карты +
    #38782931
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ок.

(поле, оператор, константа)

это большие буквы - это параметры рамки, а маленькие - поля.
Только не константа, а выражение без без использования полей.
...
Рейтинг: 0 / 0
карты +
    #38782963
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
tchingizэто большие буквы - это параметры рамки, а маленькие - поля.
Верно, я напутал, но не сильно, т.к. условие зеркально разворачивается
Код: sql
1.
(П >= л) && (Л <= п)


или
Код: sql
1.
(п >= Л) && (л <= П)



tchingizТолько не константа, а выражение без без использования полей.
я к тому что в запросе это будет константа, т.е. допустим таблица
Код: sql
1.
create table fig (fig_id int, л int, п int)


запрос
Код: sql
1.
select * from fig where (fig.п >= Л) && (fig.л <= П)


т.е. Л и П можно заменить на конкретные значения перед отправкой запроса.
...
Рейтинг: 0 / 0
карты +
    #38783019
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Код: 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.
create table zoom(             --масштаб

  id     INTEGER PRIMARY KEY,
	nm     text(128),             --название масштаба
  pw     INTEGER not null,     --    ширина тайла в условных пикселях  для масштаба
  ph     INTEGER not null,      --   высота тайла в условных пикселях 
  ltt    INTEGER not null,     --    точка на карте, которая попадает в  пиксель (0, 0) 
  lng    INTEGER not null,      --
  lttW   INTEGER not null,     --     ширина и
  lngH   INTEGER not null       --    высота тайла в единицах на местности

);

create table tile(               -- тайлы масштаба
  id     INTEGER PRIMARY KEY,
  zm     INTEGER not null,
  px     INTEGER not null,     --        координата левого 
  py     INTEGER not null,      --       верхнего угла в условных пикселях
  ltt    INTEGER not null,     -          координаты левого верхнего
  lng    INTEGER not null,      --        в единицах на местности
  constraint co1 foreign key (zm) references zoom(id)   -- 

);


create index i_tile1 on tile (zm, py, px);
--  высота будет меньше ширины, тайлов по высоте будет меньше
--  точно сравнивать надо будет по zm, py, а по меньше равно по px





Рассматриваем случай

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.
select  t.id, t.px, t.py, z.pw , z.ph,
  from  zoom as z, tile as t
  where
         t.zm = z.id
    and  t.zm = Масштаб
    and  t.py in (pyO, py1, ..., pyN)
    and  t.px <= П and  (t.px + z.pw ) >= Л
--    and  t.px <= П and  (t.px >=  Л - z.pw) z.pw можно узнать перед этим запросом и оно будет
--                                            константой
согласно документации zm, py используются по равенству, px - последнее поле по неравенству.
...
Рейтинг: 0 / 0
карты +
    #38783035
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
*верх проекции на Y первого, пересекающегося с проекцией на Y запросом тайла (то есть, В >= py0 + ph )
...
Рейтинг: 0 / 0
карты +
    #38783042
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
> В - верх, Н - низ прямоугольника, в, н - верх, низ запроса (В >= н) && (Н <= в)
тока наоборот.
Если пиксели возрастают вниз то (В <= н) && (Н >= в)

--
- Сара, твой Абрам пошел налево.
Сара, выглядывая из окна - когда он пошел направо, он пошел налево,
а когда он пошел налево, это он пошел на работу
...
Рейтинг: 0 / 0
карты +
    #38783156
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
tchingiz
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
select  t.id, t.px, t.py, z.pw , z.ph,
  from  zoom as z, tile as t
  where
         t.zm = z.id
    and  t.zm = Масштаб
    and  t.py in (pyO, py1, ..., pyN)
    and  t.px <= П and  (t.px + z.pw ) >= Л
--    and  t.px <= П and  (t.px >=  Л - z.pw) z.pw можно узнать перед этим запросом и оно будет
--                                            константой
согласно документации zm, py используются по равенству, px - последнее поле по неравенству.
Это лишнее
Код: sql
1.
 t.zm = z.id


т.к. есть
Код: sql
1.
    and  t.zm = Масштаб


достаточно
Код: sql
1.
t.zm = Масштаб


tchingizz.pw можно узнать перед этим запросом и оно будет константой
Надо затестить скорость двумя запросами, из второго вообще выкинуть таблицу zoom. Есть подозрение что оптимизатор не поймет что (Л - z.pw) это константа и не использует индекс для проверки t.px >= Л - z.pw

И еще вопрос, если отсюда выкинуть условие "and t.px <= П and (t.px + z.pw ) >= Л", то много выберется записей? т.е.
Код: sql
1.
2.
3.
select count(*) from tile as t
  where t.zm = Масштаб
    and  t.py in (pyO, py1, ..., pyN)


если относительно немного, то выкинуть px из индекса и попробовать так
Код: sql
1.
2.
3.
4.
 where
    t.zm = Масштаб
    and  (t.py between pyO and pyN)
    and  t.px <= П and  (t.px + z.pw ) >= Л



PS Надо план выполнения запроса смотреть, там будет видно какие индексы используются.
...
Рейтинг: 0 / 0
25 сообщений из 47, страница 1 из 2
Форумы / Программирование [игнор отключен] [закрыт для гостей] / карты +
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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