[postgis-users] Find none overlapping spot

[Nicklas Avén]

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 okto find a placement like that you can 2) union the polygons 3) create a polygon bigger than all of your polygons4) 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 polygon6) 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
>http://postgis.refractions.net/mailman/listinfo/postgis-users
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-users/attachments/20100129/d239c4f1/attachment.html>