有趣的谜题,用 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 中采用它,但这个想法应该可行。