Обнаружение квадратов с использованием пикселей

Ну вот интересная проблема. Предположим, у меня есть таблица в sql db, заполненная координатами x,y (положительный квадрант), и у каждой есть значение цвета, т.е. схема выглядит <x , y, color>, Задача состоит в том, чтобы обнаружить максимально возможный квадрат того же цвета. Я пытался решить эту проблему в течение нескольких часов, и, кажется, не могу сделать в ней вмятину.

Я не ищу решение, а скорее намеки.

Обратите внимание, что все это должно происходить в SQL в основном с использованием различных операций объединения, группировки и агрегирования. Некоторый пример кода был бы хорош.

Источник

2 ответа

Решение

Если вы запрашиваете только углы одного цвета, вы можете сделать

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)
Источник

Предполагая, что ваше проблемное пространство мало, скажем, 10x10 (x ограничено между 1 и 10), тогда наивный и жестокий подход:

  1. BotLeft: CROSS СОЕДИНЯТЬ два набора из 10 чисел (скажем, подмножество Numbers таблица), чтобы дать вам левый нижний угол всех возможных квадратов (100 баллов)
  2. TopRight: CROSS СОЕДИНЯЙТЕСЬ с теми же двумя сетами, чтобы снова получить все очки
  3. Квадраты: ВНУТРЕННЕЕ СОЕДИНЕНИЕ между ними, отфильтрованные по тому, где BotLeft должен быть слева и ниже TopRight.
  4. Учитывая все возможные квадраты, протестируйте каждый из них, наконец, присоединившись к вашим данным, где координаты (x,y) находятся в пределах границ квадрата, например left <= x <= right, Это создает огромный набор
  5. Сверните предыдущий набор с помощью GROUP BY (внизу слева, вверху справа) и проверьте наличие разных цветов в сгруппированном подмножестве, например HAVING COUNT(DISTINCT color) = 1,
  6. Если ваш набор данных заполнен не полностью, вам также необходимо проверить, что COUNT пикселей в каждом квадрате = количество найденных точек данных
Источник
Другие вопросы по тегам