使用SQL查找给定x，y坐标的填充矩形

Question

使用SQL查找给定x，y坐标的填充矩形

5

给出以下填写的x，y坐标：

我该如何编写一个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 |   |
+---+---+---+---+

- TheNuke

1

什么是关系型数据库管理系统？你的示例数据期望得到什么样的结果？ - Martin Smith

你使用的是SQL Server吗？Oracle？MySQL？ - Martin Smith

这个XY坐标序列是否代表一个填充多边形的路径？ - alexm

@MartinSmith 不，查询需要在不使用该功能的情况下正常工作。 - TheNuke

1

只是挑剔一下，在你的示例数据中，x 的值最高到 5，但在你期望的结果中，y 的值最高到 5。这并不改变基本原理。 - Andomar

显示剩余4条评论

2个回答

3

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

- ypercubeᵀᴹ

哇，那是一个复杂的查询。完美地工作了，谢谢。现在我要尝试理解它！ - TheNuke

我喜爱这个社群！将会在你的要求下给予他相应的荣誉。 - TheNuke

@Andomar：谢谢。我在想我们是否可以摆脱GROUP BY和HAVING COUNT(*) = ...的检查。 - ypercubeᵀᴹ

我喜欢这个解决方案只尝试在填充位置处有角落的矩形。+1 - Andomar

@ypercube 不错的答案...！你能解释一下你是如何得出这个答案的吗？你是怎样推理最终写出这个查询语句的？ - JPCF

显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Andomar · Accepted Answer

有趣的难题，编辑了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进行调整，但这个想法应该是可行的。