Nearest free coordinates in database

Question

I have X and Z coordinates in my database. Coordinates are INTegers.

Each coordinate is bigger or equal then 0.

I need to get nearest free (not in database) coordinates to 0;0 but I don't want to limit one coordinate to specified number.

Again, I don't want to get nearest coordinate in database, I want to get nearest FREE coordinate.

This is what I did myself. But it only tells me where is free space in my coordinates square (limited by maximum X and maximum Z coordinates in database).

Problem is that I cannot select free coordinates from that. I only get distance where are free coordinates but not that coordinates.

SELECT distance
FROM (
    SELECT (x+z) AS distance,COUNT(owner) AS count
    FROM coordinates 
    GROUP BY x+z ASC
) AS coor
WHERE coor.distance != coor.count-1

Answer 1

I'd try something like that:

select x, z
from (
    select x, z+1 as z from coordinates union all
    select x+1, z from coordinates union all
    select x+1, z+1 from coordinates union all
    select 0, 0
) as q
where
    concat(x,'_',z) not in (select concat(x,'_',z) from coordinates)
order by (x+z) asc
limit 1

Answer 2

The biggest problem is that you're dealing with a sparse table, i.e., you don't have any data when the coordinate is free. If you had a tuple with a "free" flag set to true, you could just do

SELECT x, z FROM coordinates WHERE flagFree ORDER BY (x*x+z*z) LIMIT 1;

but to do that, you'd need maximumX*maximumZ records.

To find data when you have actually no data you need a LEFT/RIGHT JOIN.

One way to do that would be to prepare two tables holding the numbers from 0 to maximumX and those from 0 to maximumY. At this point,

 SELECT coordinates.* from maxx JOIN maxz 
      LEFT JOIN coordinates ON ( ix = x AND iz = z );

will yield NULL for all missing coordinates. So:

 SELECT ix, iz from maxx JOIN maxz 
      LEFT JOIN coordinates ON ( ix = x AND iz = z )
      WHERE x IS NULL AND z IS NULL
      ORDER BY ix*ix + iz*iz
 LIMIT 1;

will get you the coordinates you need.

Borrowing from Lashane's solution, you can do the same without other tables, reasoning that any nearest empty cell you find to the origin will be either the origin itself (0,0) or adjacent to another filled cell. And filled cells are in coordinates. So:

SELECT p.x, p.z FROM ( 
    SELECT 0 AS x, 0 AS z 
    UNION
    SELECT x+1, z FROM coordinates
    UNION
    SELECT x+1, z+1 FROM coordinates
    UNION
    SELECT x, z+1 FROM coordinates
) AS p 
LEFT JOIN coordinates AS a ON (p.x = a.x AND p.z = a.z)
WHERE a.x IS NULL AND a.z IS NULL
ORDER BY p.z*p.z + p.x*p.x
LIMIT 1;