使用像素检测正方形

Question

那么这是一个有趣的问题。假设我在一个充满x，y坐标（正象限）的sql db上有一个表，每个表都有一个颜色值，即模式看起来像是<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不会对性能有很大影响，因为它将不得不生成所有的正方形。

您可以通过添加（color，x，y）和（color，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

假设你的问题的空间很小，比方说10×10（X 1和10之间为界），然后是天真和残酷的方法：

1. BotLeft：CROSS JOIN两套10个号码（比如一个子集Numbers表）给你所有可能的平方（100分）的左下角
2. TopRight：CROSS JOIN相同的两组，再次让所有的点
3. 正方形：INNER两个之间的连接，通过这里BotLeft必须过滤向左和向下TopRight
4. 给定所有可能的正方形，通过最终连接到（x，y）坐标落在正方形范围内的数据来测试每一个正方形，例如， left <= x <= right。这会生成一个庞大的集合
5. 使用GROUP BY（左下角，右上角）折叠上一个集合并测试分组子集中不同的颜色，例如， HAVING COUNT(DISTINCT color) = 1。
6. 如果数据集未完全充满，那么你还需要进行测试，在数据点的每平方米=计数像素的COUNT发现