使用像素检测正方形

Question

这里有一个有趣的问题。假设我在sql db上有一个表，其中充满了x，y坐标（正象限），每个坐标都有一个颜色值，即模式看起来像<x , y, color>。任务是检测具有相同颜色的最大可能正方形。几个小时以来，我一直在尝试解决这个问题，但似乎无法对此有所作为。

我不是在寻找解决方案，而是在寻找提示。

请注意，这一切都必须在SQL中发生，主要使用各种连接，分组和聚合操作。一些示例代码会很好。

Answer 1

如果你只要求角的颜色相同，你可以这样做

top left corner
join top right corner on equal x and color and greater y
join bottom left corner on equal y and color and greater x
join bottom right on equal x, y and color
order by (x1-x2)*(y1-x2) descending
limit 1

当然，极限 1 不会对性能产生太大影响，因为它无论如何都必须生成所有正方形。

您可以通过添加（颜色，x，y）

和（颜色，y，x）索引（大大）提高速度。执行计划很可能最终会：

(1) full scan for all top left corners
(2) dependent index scan for all top right corners
(3) dependent index scan for all bottom left corners
(4) dependent index scan for the bottom right corner expecting at most one match
(5) (partial) table sort of the entire set of squares (cannot use indexes)

Answer 2

假设你的问题空间很小，假设 10x10（x 在 1 到 10 之间），那么一个幼稚而残酷的方法：

1. BotLeft：交叉连接两组 10 个数字（例如Numbers表的子集），为您提供所有可能的方块的左下角（100 分）
2. 右上：交叉连接相同的两组以再次获得所有积分
3. 正方形：两者之间的内部连接，按 BotLeft 必须在左侧和右上角下方的位置进行过滤
4. 给定所有可能的正方形，通过最终连接到 （x，y） 坐标落在正方形边界内的数据来测试每个正方形，例如 left <= x <= right . 这会产生一个巨大的集合
5. 使用 GROUP BY（左下角，右上角）折叠上一组，并测试分组子集中的不同颜色，例如 HAVING COUNT(DISTINCT color) = 1 .
6. 如果您的数据集未完全填充，则还需要测试每个方块中的像素COUNT = 找到的数据点计数