Поиск заполненных прямоугольников по координатам x, y с использованием SQL

Question

Учитывая следующие заполненные координаты x, y:

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-запрос для определения всех заполненных прямоугольников? Прямоугольник определяется его верхним левым и нижним правым углами.

Желаемые результаты

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

Answer 1

Интересная головоломка, решение отредактировано с идеями из ответа ypercube:

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

Сначала строится список всех возможных прямоугольников. Затем он требует, чтобы количество заполненных позиций соответствовало общему количеству позиций (площадь прямоугольника). Наконец, он требует, чтобы не было другого прямоугольника, который полностью покрывал бы прямоугольник.

Возможно, вам придется принять его для 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)
        )