Как найти незанятые области через запрос MySql

#mysql #select

Приложил картинку:
в базе хранятся закрашенные области (серый цвет), как координаты левого верхнего
угла и правого нижнего, т.е. ЧЕТЫРЕ числа (х1,у1,х2,у2).
Как запросом в базу MySql получить координаты свободной области, если условия такие:  


начиная сверху слева найти свободную область размером 1х1  
начиная сверху слева найти свободную область размером 2х2  


То есть для п.1 ответ должен быть 0,0,1,1 (голубой квадратик)
для п.2 = 6,0,8,2 (оранжевый квадратик)  

 
Все, на что хватило знаний)) -это функцией MIN нахожу свободную координату по оси
X, но в совокупности с осью Y это неправильно. И для поиска областей 2х2 поиск через
MIN вообще не применим.
Как вариант, думал создать еще одну таблицу с перечислением всех возможных точек
(т.е. для данного квадрата это 10х10=100 строк) и ставить пометку - такие-то точки
заняты, а такие-то нет и искать среди незанятых, но если размер поля надо будет увеличить
(с 10х10 до например 100х100), то скорее всего начнутся задержки???
База:  



DROP TABLE IF EXISTS `m_items`;
CREATE TABLE `m_items` (
  `id` int(11) NOT NULL,
  `x1` smallint(4) NOT NULL,
  `y1` smallint(4) NOT NULL,
  `x2` smallint(4) NOT NULL,
  `y2` smallint(4) NOT NULL
) ENGINE=MyISAM DEFAULT CHARSET=utf8;






INSERT INTO `m_items` (`id`, `x1`, `y1`, `x2`, `y2`) VALUES
(1, 3, 0, 6, 4),
(2, 8, 0, 9, 2),
(3, 0, 1, 2, 2),
(4, 0, 3, 2, 5),
(5, 7, 3, 9, 7),
(6, 1, 6, 6, 7),
(7, 1, 8, 2, 10);



    

Ответы

Ответ 1

Попробуйте так:

select x,y
from c -- см. ответ @mnv
left join m_items
on x <= X2-1 and
   x+2 >= X1 and
   y <= Y2-1 and
   y+2 >= Y1
where x+2<10 and y+2<10
and id is null
order by y, x;


+2 - это квадраты 3x3.

SQLFiddle


Ответ 2

Можно сделать так. Строим табличку всех возможных комбинаций x и y (от 1 до 10).
Чтобы проще воспринимался запрос для получения результата, оформляем это в виде временной
таблицы:

CREATE TEMPORARY TABLE IF NOT EXISTS c AS (
    SELECT x, y FROM (
        SELECT 0 as x UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 
        UNION SELECT 5 UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9
    ) x
    CROSS JOIN (
    SELECT 0 as y UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 
            UNION SELECT 5 UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9
    ) y
);


В @size положим размер свободного квадрата. Тут 0 означает квадрат размером 1x1.
Для квадрата 2x2 делаем так:

SET @size = 2 - 1;


Теперь все готово для того, чтобы найти ближайший свободный квадрат. Следующий запрос
находит все свободные квадраты, сортирует результаты в нужном порядке и выбирает первый,
что требуется по условию. Смысл запроса - поиск областей, которые не пересекаются с
тем, что имеется на поле:

SELECT * FROM c WHERE NOT EXISTS (
    SELECT 1 FROM t WHERE (
        (x >= x1 AND x <= x2) 
        OR (x + @size >= x1 AND x + @size <= x2)
        OR (x1 >= x AND x1 <= x + @size)
        OR (x2 >= x AND x2 <= x + @size)
    ) AND (
        (y >= y1 AND y <= y2) 
        OR (y + @size >= y1 AND y + @size <= y2)
        OR (y1 >= y AND y1 <= y + @size)
        OR (y2 >= y AND y2 <= y + @size)
    )
)
AND x < 10 - @size
AND y < 10 - @size
ORDER BY x, y
LIMIT 1;


Посмотреть пример и поэкспериментировать можно тут.

ОБНОВЛЕНИЕ

Запрос выше для случая, когда надо двигаться сперва по оси y, потом по x (так изначально
был поставлен вопрос). Если нужен ответ для отредактированного варианта вопроса, то
просто поменяйте условие сортировки:

ORDER BY y, x