使用SQL查找给定x，y坐标的填充矩形 [英] Finding filled rectangles given x, y coordinates using SQL

问题描述

以下填充的x，y坐标：

Given the following filled x, y coordinates:

0, 0
0, 1
0, 2
1, 0 
1, 1
1, 2
2, 0
2, 1
2, 2
4, 0
4, 1
5, 0
5, 1

如何编写SQL查询以确定所有填充的矩形？一个矩形由其左上角和右下角定义。

How do I write an SQL query to determine all the filled rectangles? A rectangle is defined by its top left and bottom right corners.

预期结果

Desired Results

x1 | y1 | x2 | y2 
 0    0   2    2 
 0    4   1    5

因为

+---+---+---+---+
|   | 0 | 1 | 2 |
+---+---+---+---+
| 0 | X | X | X |
| 1 | X | X | X |
| 2 | X | X | X |
| 3 |   |   |   |
| 4 | X | X |   |
| 5 | X | X |   |
+---+---+---+---+

推荐答案

有趣的益智，用ypercube的答案提出的解决方案编辑的解决方案：

Interesting puzzle, solution edited with ideas from ypercube's answer:

declare @t table (x int, y int);
insert @t (x,y) values (0, 0), (0, 1), (0, 2), (1, 0),  (1, 1), (1, 2), 
                       (2, 0), (2, 1), (2, 2), (4, 0), (4, 1), (5, 0), (5, 1);

; with  all_rectangles as
        (
        select  lt.x as x1
        ,       lt.y as y1
        ,       rt.x as x2
        ,       lb.y as y2
        from    @t lt -- Left top
        join    @t rt -- Right top
        on      rt.y = lt.y -- Must share top
                and rt.x > lt.x
        join    @t lb -- Left bottom
        on      lb.x = lt.x -- Must share left
                and lb.y > lt.y
        join    @t rb -- Right bottom (limits resultset)
        on      rb.x = rt.x -- Must share right
                and rb.y = lb.y -- Must share bottom
        )
,       filled_rectangles as
        (
        select  rect.x1
        ,       rect.y1
        ,       rect.x2
        ,       rect.y2
        from    all_rectangles rect
        join    @t crossed
        on      crossed.x between rect.x1 and rect.x2
                and crossed.y between rect.y1 and rect.y2
        group by
                rect.x1
        ,       rect.y1
        ,       rect.x2
        ,       rect.y2
        having  count(*) = 
                (rect.x2 - rect.x1 + 1) * (rect.y2 - rect.y1 + 1)
        )
select  *
from    filled_rectangles rect
where   not exists
        (
        select  *
        from    filled_rectangles bigger
        where   bigger.x1 <= rect.x1 and rect.x2 <= bigger.x2
                and bigger.y1 <= rect.y1 and rect.y2 <= bigger.y2
                and (rect.x1 <> bigger.x1 or rect.x2 <> bigger.x2 
                or rect.y1 <> bigger.y1 or rect.y2 <> bigger.y2)
        );

它首先建立所有可能矩形的列表。然后它要求填充位置的数量与位置的总数（矩形的面积）匹配。最后，它要求没有其他矩形完全覆盖矩形。

It first builds a list of all possible rectangles. Then it demands that the number of filled positions matches the total number of positions (the area of the rectangle.) Finally, it demands that there's no other rectangle that entirely covers the rectangle.

您可能不得不为PostgreSQL采用它，但这个想法应该可行。

You might have to adopt it for PostgreSQL, but the idea should work.

这篇关于使用SQL查找给定x，y坐标的填充矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！