使用像素檢測正方形

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發現