I attached a picture: the shaded areas (gray color) are stored in the database, as are the coordinates of the upper left corner and the lower right, i.e. FOUR numbers (x1, y1, x2, y2). As a query to the database MySql get the coordinates of the free area, if the conditions are:

  1. starting from the top left find a free area of ​​1x1
  2. starting from the top left find a free area of ​​2x2

That is, for item 1, the answer should be 0,0,1,1 (blue square) for p. 2 = 6,0,8,2 (orange square)

enter image description here All that was enough knowledge)) is the MIN function to find the free coordinate along the X axis, but in combination with the Y axis this is wrong. And for searching for 2x2 areas, searching through MIN is not applicable at all.
Alternatively, I thought of creating another table listing all possible points (i.e., for a given square, this is 10x10 = 100 rows) and ticking off — such and such points are occupied, but such-and-such is not and search among the unoccupied, but if the size is the fields will need to be increased (from 10x10 to for example 100x100), then delays will most likely begin ???
Base:

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); 

  • one
    Give a sample of the test table with the data filled in on the basis of this image in a format suitable for direct loading into the database. Those. SQL create table and insert to it - Mike
  • one
    Specify why the answer for n2 is not (6,0,7,1)? We chtoli in the search should move along the Y axis, then along the X? - artoodetoo
  • Oh, my mistake !! Actually there will be the second obtitet !! missed !! and it makes sense to find everything that fits on the upper horizontal from left to right, if not, go down below and also from left to right. Updated post referring to the patient - Sergey V.
  • Still looking for an algorithm, options with the search for intersections between the two tables in view of the large number of options are most likely not suitable. - Sergey V.

2 answers 2

Try this:

 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 are 3x3 squares.

SQLFiddle

  • Ok, I'll try .. THX - Sergey V.
  • and id is null - what table? otherwise I changed to different spelling in different tables to simplify the experiments - for m_items, not id but m_id ... if so that is 2.0118 seconds when searching the 1000x1000 grid, i.e. Table C contains 1kk rows)) for some reason dumped all the results of 16000 cubes (only 805000 rows) and not the extreme one from the upper left corner ... - Sergey V.
  • one
    id is null can be replaced by x1 or any other field from m_items , this condition for "no intersection found for a square with existing rectangles". If you need one, then add limit 1. In the response, the query displays all the free squares, yes. - Yura Ivanov
  • but pretty straight! so far it seems like everything is looking right ... I wonder how you made it up? what designer? here it is necessary to visually present and correlate with the requests ... the experiment showed that a square or a rectangle does not matter, right? Well, the coordinates respectively set, ie, x + 130 and y + 340, yes? The only thing that does not please is that the request from 1.2 to 2.5 seconds .. how can you overcome this? - Sergey V.
  • one
    A condition is a condition of the intersection of polygons, or rather the intersection of segments (projections on the axes). Yes, you can search not only squares. I do not know what the original task, optimization methods may be different. caching, clustering (what @mnv suggested is partitioned into segments), storing vice versa unoccupied areas instead of occupied ones ... since the comparison is done with each one, it is unlikely that the request itself can be accelerated, the algorithm must be changed or data reduced. Threat index can help (range is still better than no index at all, for example), but you have to watch ... - Yura Ivanov

You can do so. We build a label of all possible combinations of x and y (from 1 to 10). To make the query easier to understand, we make this into a temporary table:

 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 ); 

In @size we set the size of the free square. Here 0 means a 1x1 square. For a 2x2 square, do this:

 SET @size = 2 - 1; 

Now everything is ready to find the nearest free square. The following query finds all the free squares, sorts the results in the desired order and selects the first one that is required by the condition. The meaning of the query is the search for areas that do not overlap with what is on the field:

 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; 

You can see an example and experiment here .

UPDATE

The query is higher for the case when it is necessary to move first along the y axis, then along the x (the question was originally posed). If you need an answer for the edited version of the question, then just change the sorting condition:

 ORDER BY y, x 
  • You have 4 lines in the example - lines and not rectangles ... ?? - Sergey V.
  • In the example on sqlfiddle in table t? There are rectangles. Each line is one rectangle defined by two points {(x1, y1), (x2, y2)}. - mnv
  • @ Sergey V. I also noticed that the question was slightly corrected. I added to the answer how to implement it. - mnv
  • one
    You can think of it as a line and a rectangle, as you prefer. Here is an illustration of this snippet: pix.toile-libre.org/upload/original/1473537024.png . I checked the result on sqlfiddle, for your example the correct answer is given - the left upper point of the square. If the answer also needs the coordinate of the lower right point, just write in select instead of * : x, y, x + @size, y + @size . - mnv
  • one
    I think that the search will accelerate for cases when there are few unoccupied areas and slow down for cases when there are many unoccupied areas. If I were you, I would simply try to add a composite index on y, x in the solution from @Yura Ivanov. - mnv