픽셀을 사용하여 사각형 감지하기

Question

여기 흥미로운 문제가 있습니다. x, y 좌표 (양의 사분면)로 채워진 SQL 데이터베이스에 테이블이 있고 각 테이블에 색상 값이 있다고 가정하면 스키마는 <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 

, 그것은 어쨌든 모든 사각형을 생성해야하기 때문에 성능에 많은 영향을 증언 요구 무산 한계 일을한다.

(색상, 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

,의는 10 × 10 (x는 1과 10 사이의 경계)라고하자, 그 다음 순진하고 잔인한 방법 :

1. BotLeft : CROSS의 (a의 말 일부 10 개 숫자의 두 세트를 가입 Numbers 표) 당신에게 모든 가능한 사각형 (100 점)의 왼쪽 하단 모서리를 제공하는
2. TopRight : CROSS 다시
3. 사각형의 모든 포인트를 얻을 같은 두 세트를 가입 : INNER 어디 BotLeft가 반드시 필터링, 둘 사이에 가입하세요 왼쪽 아래에있다. TopRight
4. 모든 가능한 사각형을 감안할 때, (x, y) 좌표가 사각형 경계 내에있는 데이터에 마지막으로 결합하여 각각의 사각형을 테스트하십시오. left <= x <= right. 그러면 큰 세트가 생성됩니다.
5. GROUP BY (왼쪽 하단, 오른쪽 상단)를 사용하여 이전 세트를 축소하고 그룹화 된 하위 세트 내에서 고유 한 색상을 테스트합니다 (예 : HAVING COUNT(DISTINCT color) = 1. 데이터 세트가 완전히 작성되지 않은 경우
6. 는, 당신은 또한 당신이 수, 당신은 단지 모서리가 같은 색상을 할 수 요청하면 데이터 포인트의 각 평방 = 수의 픽셀 COUNT는