That is an example of a theoretical solution that may be overkill in practice, especially if you are stuck in JS. Unless you send window positions back to the server for analysis.
And can you code an AABB tree on a whiteboard? :-)
One could try placing the new window at (100x, 200y) for integer x,y, and check for intersection each time with all the existing windows. 3600 overlap tests in the worst case, but you get huge benefits in practice by hinting the location of the last new window.
Optimize a bit by sorting lists of windows by x and y, so you can binary search for the few candidates to overlap test, and you are down to about 1000 window checks. You miss some cases if windows are very maliciously aligned off grid, but you can mitigate that by using a slightly finer grid.
Or test the 8 neighbors (edges and corners) of each existing window (if any), as it is nearly impossible for available space to be not one of those positions.
(You can compute the next window position after the previous window creation or move, so there is no latency when rendering a new window.)
And can you code an AABB tree on a whiteboard? :-)
One could try placing the new window at (100x, 200y) for integer x,y, and check for intersection each time with all the existing windows. 3600 overlap tests in the worst case, but you get huge benefits in practice by hinting the location of the last new window.
Optimize a bit by sorting lists of windows by x and y, so you can binary search for the few candidates to overlap test, and you are down to about 1000 window checks. You miss some cases if windows are very maliciously aligned off grid, but you can mitigate that by using a slightly finer grid.
Or test the 8 neighbors (edges and corners) of each existing window (if any), as it is nearly impossible for available space to be not one of those positions.
(You can compute the next window position after the previous window creation or move, so there is no latency when rendering a new window.)