Finding filled rectangles given x, y coordinates using SQL

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

How do I write an SQL query to determine all the filled rectangles? A rectangle is defined by its top left and bottom right cor开发者_开发技巧ners.

Desired Results

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

Because

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

---

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.

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

---

WITH Box AS
( SELECT LeftUp.X     AS x1
       , LeftUp.Y     AS y1
       , RightDown.X  AS x2
       , RightDown.Y  AS y2
  FROM TableX AS LeftUp
    JOIN TableX AS LeftDown
      ON  LeftDown.X = LeftUp.X
      AND LeftDown.Y >= LeftUp.Y
    JOIN TableX AS RightUp
      ON  RightUp.Y = LeftUp.Y
      AND RightUp.X >= LeftUp.X
    JOIN TableX AS RightDown
      ON  RightDown.X = RightUp.X
      AND RightDown.Y = LeftDown.Y
    JOIN TableX AS Inside
      ON  Inside.X BETWEEN LeftUp.X AND RightDown.X
      AND Inside.Y BETWEEN LeftUp.Y AND RightDown.Y
  GROUP BY LeftUp.X
         , LeftUp.Y
         , RightDown.X
         , RightDown.Y
  HAVING COUNT(*) = (1 + RightDown.X - LeftUp.X) * (1 + RightDown.Y - LeftUp.Y)
)

SELECT B.*
FROM Box AS B                         --- SmallBox (but not very small)
WHERE NOT EXISTS                      --- as there not exists
        ( SELECT *                    --- any
          FROM Box AS BB              --- BigBox
          WHERE BB.x1 <= B.x1         --- that covers the "small" one
            AND BB.x2 >= B.x2
            AND BB.y1 <= B.y1
            AND BB.y2 >= B.y2
            AND (BB.x1, BB.x2, BB.y1, BB.y2) <> (B.x1, B.x2, B.y1, B.y2)
        )