SQL query to get neighbours from table with two dimensional data

I have a table, that contains partitioning of world map. Partition is done by splitting all area into rectangles, called 'tile'. As usual, rectangle has bottom-left and upper-right corners, both referred by floating point coordinates.

The task is this:

For each tile get its neighbour to the right and its neighbour to the top, like a set of {tile_id, id_of_top_neighbour, id_of_right_n}.

By right neighbour of tile A meant such tile B, that has the closest min_x coordinate to A's max_x coord, while y are the same.

Description of the table:

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

Failed solution:

First, I tried to sort by one coordinate, iterate by this result set on the java side and then perform an additional select for each row. The performance was inadequate.

Now I wonder if a pure SQL solution would be possible and quicker at runtime...

Appreciated any help or ideas beforehand.

EDIT: There could be a gap between two tiles, so (e.g. for right neighbour) B.min_x - A.max_x could be > 0. Hovewer, two tiles cannot intersect more, than by boundary.

We are using Postgres 8.3

Answers


Windowing functions and CTEs would make this pretty easy to do. I think both are available in 8.4 and above. I would strongly suggest you upgrade. I tested this solution on 9.0:

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

Result:

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


Need Your Help

To get a Class object we use MyClass.class-It seems “class” is a static member of “MyClass”

java class

To get a Class object we use MyClass.class-It seems “class” is a static member of “MyClass”

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.