# [postgis-users] Find none overlapping spot

Nicklas Avén nicklas.aven at jordogskog.no
Fri Jan 29 12:28:06 PST 2010

```Hallo again Inspired by Kevins split polygon example earlier today I also want to give an example of my suggestion :-) first a table to use. the squares are not "scattered" but the same princip should work. create table t as
select st_expand(st_point(a,b),2) as the_geom from
generate_series(0,100,10) a,
generate_series(0,200,10) b
then we add a new square (same size in this example) into this t table whitout the new one overlapping the new ones
insert into t
select st_expand(st_pointonsurface(the_geom),2) as the_geom from
(select st_difference(st_envelope(the_geom),the_geom)as the_geom from
(select st_union(st_expand(the_geom,2)) as the_geom from t) a) b
/Nicklas
2010-01-29 Nicklas Avén wrote:

>Maybe something like this:> >If your polygons are not rotated this should be fast.>1) expand all old polygons with half the size of the new polygon in your example 10> >now, if your new polygon have any part in the empty room between the expanded polygons it should be ok>to find a placement like that you can> >2) union the polygons> >3) create a polygon bigger than all of your polygons>4) use st_difference(new_big_polygon, expanded_unioned_polygon)>    then you should have a polygon or multipolygon with the areas nor overlapped by the expanded squares.>5) use ST_Pointonsurface to find a point on thes polygon>6) build a square from this point. It shouild be ok in any direction.
>
If the squares are rotated you can do the same but then you will haveto extend the polygons by the distance from the middle to the corner of the new square instead and you will then not find any possible placements.>
>
I haven't thought about every aspect of this, but I think it should work and be quite fast solution.
>
Hope that helps>
Nicklas>

>
> 2010-01-29 tommy408 wrote:
>
>
> >I have a bunch of square polygons scattered everywhere. Whats the fastest
> >way for me to place another square polygon say 20x20 size into this area
> >that won't overlap any other polygons?
> >
> >The only way I can think of is start the input square at a spot, and move it
> >by 1 unit at a time and keep checking ST_Overlap.
> >--
> >View this message in context: http://old.nabble.com/Find-none-overlapping-spot-tp27366934p27366934.html
> >Sent from the PostGIS - User mailing list archive at Nabble.com.
> >
> >_______________________________________________
> >postgis-users mailing list
> >postgis-users at postgis.refractions.net
> >postgis.refractions.net/mailman/listinfo/postgis-users
> >
> >
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-users/attachments/20100129/680709d2/attachment.html>
```