Finding filled rectangles based on x, y coordinates using SQL

Question

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 to write a SQL query to determine all filled rectangles? A rectangle is defined by its upper left and lower right corners.

Desired Results

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

Because the

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

Answer 1

An interesting puzzle, the solution was edited using the ideas from ypercube 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)
        );

First, it creates a list of all possible rectangles. Then it requires that the number of filled positions correspond to the total number of positions (rectangle area.) Finally, it requires that there is no other rectangle that completely covers the rectangle.

, PostgreSQL, .

Answer 2

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)
        )