SQL-запрос для получения соседей из таблицы с двумерными данными

Question

У меня есть таблица с разделением карты мира. Разделение осуществляется путем разделения всей области на прямоугольники, называемые «плиткой». Как обычно, прямоугольник имеет нижний левый и верхний правый углы, оба обозначаются координатами с плавающей точкой.

Задача такая:

Для каждой плитки возьмите ее соседа справа и соседа сверху, как набор {tile_id, id_of_top_neighbour, id_of_right_n}.

Под правым соседом мозаичного элемента A подразумевается такой мозаичный элемент B, который имеет ближайшую координату min_x к координате max_x A, а y совпадают.

Описание таблицы:

integer tile_id; --Tile id. PK.
real    min_x;  --X coordinate of bottom-left point
real    min_y;  --Y coordinate of bottom-left point
real    max_x;  --X coordinate of upper-right point
real    max_y;  --Y coordinate of upper-right point

Неудачное решение:

Сначала я попытался отсортировать по одной координате, перебрать этот набор результатов на стороне Java, а затем выполнить дополнительный выбор для каждой строки. Спектакль был неадекватным.

Теперь мне интересно, возможно ли решение на чистом SQL быстрее и быстрее во время выполнения ...

Заранее оценил любую помощь или идеи.

EDIT: Между двумя тайлами может быть промежуток, поэтому (например, для правого соседа) B.min_x - A.max_x может быть> 0. Однако, две плитки не могут пересекаться больше, чем по границе.

Мы используем Postgres 8,3

Answer 1

Функции управления окнами и CTE делают это довольно простым делом.Я думаю, что оба доступны в 8.4 и выше.Я настоятельно рекомендую вам обновить.Я протестировал это решение на 9.0:

<code>with tile_data as
(
    select
        tile_id,
        min_x,
        min_x + 0.9 as max_x,
        min_y,
        min_y + 0.9 as max_y
    from
    (
     select 1 as tile_id, 0.0 as min_x, 0.0 as min_y union all
     select 2, 1.0, 0.0 union all
     select 3, 2.0, 0.0 union all
     select 4, 0.0, 1.0 union all
     select 5, 1.0, 1.0 union all
     select 6, 2.0, 1.0 union all
     select 7, 0.0, 2.0 union all
     select 8, 1.0, 2.0 union all
     select 9, 2.0, 2.0 
    ) a
),
right_neighbor_tiles as
(
    select
        tile_id,
        other_tile_id as right_neighbor_tile_id
    from
    (
        select
             a.tile_id,
             b.tile_id as other_tile_id,
             row_number() over(partition by a.tile_id order by b.min_x - a.min_x) as distance_rank
        from 
            tile_data a
        inner join
            tile_data b
        on
            a.min_x < b.min_x 
            and a.min_y = b.min_y
    ) ranked_tiles_right
    where
        distance_rank = 1
),
up_neighbor_tiles as
(
    select
        tile_id,
        other_tile_id as up_neighbor_tile_id
    from
    (
        select
            a.tile_id,
            b.tile_id as other_tile_id,
            row_number() over(partition by a.tile_id order by a.min_y - b.min_y) as distance_rank
        from 
            tile_data a
        inner join
            tile_data b
        on
            a.min_y > b.min_y 
            and a.min_x = b.min_x
    ) ranked_tiles_up
    where
        distance_rank = 1
)
select 
    a.*,
    b.right_neighbor_tile_id,
    c.up_neighbor_tile_id
from
    tile_data a
left join
    right_neighbor_tiles b
on
    a.tile_id = b.tile_id
left join
    up_neighbor_tiles c
on
    a.tile_id = c.tile_id

Результат:

<code>tile_id  min_x  max_x  min_y  max_y  right_neighbor_tile_id   up_neighbor_tile_id
1        0      0.9    0      0.9    2
2        1      1.9    0      0.9    3
3        2      2.9    0      0.9
4        0      0.9    1      1.9    5                        1
5        1      1.9    1      1.9    6                        2
6        2      2.9    1      1.9                             3
7        0      0.9    2      2.9    8                        4
8        1      1.9    2      2.9    9                        5
9        2      2.9    2      2.9                             6

Answer 2

Измените ваши данные для использования типа Box.

create temp table test (
    nick    char,
    tile    box
);


/*
.........
aa..bbcc.
aa..bbcc.
*/

insert into test values ('a',  box(point(0,1),point(1,0)));
insert into test values ('b',  box(point(4,0),point(5,1)));
insert into test values ('c',  box(point(7,0),point(8,1)));

select
    distinct on (test.nick)

    test.nick,
    r.nick as right,
    least((r.tile[0])[0], (r.tile[1])[0]) as least_x -- gets the lowest x cord

from test
    join test as r
        on  test.tile << r.tile -- strictly left of operator

    group by test.nick, right, least_x

вывод:

 nick | right   | least_x
 ------+---------+---------
 a    | b       |       4
 b    | c       |       7
 (2 rows)