Найти первую свободную область через запрос MySQL

Формулировка задачи:

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

                    Листинг программы
                
 
                        
                          
                    
CREATE TABLE `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 `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);

Решение задачи: «Найти первую свободную область через запрос MySQL»

Листинг программы

CREATE TABLE items (
  id INT UNSIGNED NOT NULL AUTO_INCREMENT,
  t SMALLINT NOT NULL,
  l SMALLINT NOT NULL,
  b SMALLINT NOT NULL,
  r SMALLINT NOT NULL,
  ls linestring NOT NULL,
  CONSTRAINT pk_items_id PRIMARY KEY(id),
  spatial INDEX (ls)
) engine = myisam DEFAULT CHARACTER SET = cp1251;
 
delimiter ~
CREATE definer = CURRENT_USER TRIGGER bi_items BEFORE INSERT ON items
FOR each ROW
BEGIN
  SET NEW.ls = linestring(point(NEW.t, NEW.l), point(NEW.b, NEW.r));
END~
 
CREATE definer = CURRENT_USER FUNCTION getCell (
  asize INT,     -- размер квадратика 
  maxsize INT)   -- размер проверяемой квадратной (обязательно!) матрицы [0, 1, ..., maxsize]
RETURNS linestring
BEGIN
  DECLARE nR INT DEFAULT 0; -- row
  DECLARE nC INT DEFAULT 0; -- col
  DECLARE find tinyint DEFAULT 1;
 
X:  repeat
    SELECT
      SUM(intersects(linestring(point(nR + 0.1, nC + 0.1), point(nR + asize - 0.1, nC + asize - 0.1)), ls))
       INTO find
    FROM items;
    
    IF find > 0 THEN
      IF (nC + asize + 1) > maxsize THEN
        SET nC = 0;
        IF (nR + asize + 1) > maxsize THEN
          leave X;
        ELSE
          SET nR = nR + 1;
        END IF;
      ELSE
        SET nC = nC + 1;
      END IF;
    END IF;
  until find = 0
  END repeat;
  IF find = 0 THEN
    RETURN linestring(point(nR, nC), point(nR + asize, nC + asize));
  ELSE
    RETURN NULL;
  END IF;
END~
delimiter ;
 
INSERT INTO items(t, l, b, r) VALUES
  (0, 3, 4, 6),
  (0, 8, 2, 9),
  (1, 0, 2, 2),
  (3, 0, 5, 2),
  (3, 7, 7, 9),
  (6, 1, 7, 6),
  (8, 1, 10,2);
 
SELECT astext(getCell(1, 10)) FROM dual; -- поиск ячейки размером 1x1
SELECT astext(getCell(2, 10)) FROM dual; -- поиск ячейки размером 2x2

Объяснение кода листинга программы

Создание таблицы items с полями id, t, l, b, r, ls типа INT, SMALLINT, SMALLINT, SMALLINT, SMALLINT, linestring соответственно. Тип linestring используется для хранения геометрических данных.
Создание триггера bi_items перед таблицей items, который будет автоматически присваивать геометрическое значение в поле ls при вставке новой записи.
Создание функции getCell, которая принимает два параметра: asize и maxsize. Функция проверяет пересечение вставленной в таблицу items линии с каждой ячейкой размером asize x maxsize и возвращает координаты первой свободной ячейки.
Вставка данных в таблицу items.
Вызов функции getCell с размерами 1x1 и 2x2 для поиска свободных ячеек.