<html>
<head>
        <title></title>
        
<meta name="GENERATOR" content="MSHTML 8.00.6001.18876"></meta>
        
<meta name="SKYPE_FRAMEID" content="UKSDOXEVME"></meta>
        
<meta id="skype_v3_tb_marker_id" name="SKYPE_PARSING_HAS_FINISHED" content="metacontent"></meta>
</head>

<body>
        
<div align="left">Hallo again</div>
        
<div align="left"> </div>
        
<div align="left">Inspired by Kevins split polygon example earlier today I also want to give an example of my suggestion :-)</div>
        
<div align="left"> </div>
        
<div align="left">first a table to use. the squares are not "scattered" but the same princip should work.</div>
        
<div align="left"> </div>
        
<div align="left">create table t as <br />
                select st_expand(st_point(a,b),2) as the_geom from<br />
                generate_series(0,100,10) a,<br />
                generate_series(0,200,10) b<br />
                </div>
        
<div align="left">then we add a new square (same size in this example) into this t table whitout the new one overlapping the new ones</div>
        
<div align="left"><br />
                insert into t<br />
                select st_expand(st_pointonsurface(the_geom),2) as the_geom from<br />
                 (select st_difference(st_envelope(the_geom),the_geom)as the_geom from<br />
                  (select st_union(st_expand(the_geom,2)) as the_geom from t) a) b<br />
                </div>
        
<div align="left"> </div>
        
<div align="left">/Nicklas</div>
        
<div align="left"> </div>
        
<div align="left"> </div>
        
<div align="left"><br />
                2010-01-29 Nicklas Avén wrote:<br />
                <br />
                ></div>
        
<div align="left"><span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt">Maybe something like this:</span></div>>
        
<div align="left"><span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt"> </span></div>>
        
<div align="left"><span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt">If your polygons are not rotated this should be fast.</span></div>>
        
<div align="left"><span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt">1) expand all old polygons with half the size of the new polygon in your example 10</span></div>>
        
<div align="left"><span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt"> </span></div>>
        
<div align="left"><span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt">now, if your new polygon have any part in the empty room between the expanded polygons it should be ok</span></div>>
        
<div align="left"><span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt">to find a placement like that you can</span></div>>
        
<div align="left"><span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt"> </span></div>>
        
<div align="left"><span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt">2) union the polygons</span></div>>
        
<div align="left"><span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt"> </span></div>>
        
<div align="left"><span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt">3) create a polygon bigger than all of your polygons</span></div>>
        
<div align="left"><span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt">4) use st_difference(new_big_polygon, expanded_unioned_polygon)</span></div>>
        
<div align="left"><span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt">    then you should have a polygon or multipolygon with the areas nor overlapped by the expanded squares.</span></div>>
        
<div align="left"><span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt">5) use <span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt"><span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt">ST_Pointonsurface to find a point on thes polygon</span></span></span></div>>
        
<div align="left"><span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt">6) build a square from this point. It shouild be ok in any direction.</span></div>
        
<p><span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt"> </span></p>>
        
<div><span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt">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.</span></div>>
        
<div><span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt"> </span></div>>
        
<div><span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt">I haven't thought about every aspect of this, but I think it should work and be quite fast solution.</span></div>
        
<p><span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt"> </span></p>>
        
<div><span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt">Hope that helps</span></div>>
        
<div><span style="FONT-FAMILY: 'Times New Roman'; FONT-SIZE: 12pt">Nicklas</span></div>>
        
<div><br />
                ><br />
                > 2010-01-29 tommy408 wrote:<br />
                ><br />
                ><br />
                > >I have a bunch of square polygons scattered everywhere. Whats the fastest<br />
                > >way for me to place another square polygon say 20x20 size into this area<br />
                > >that won't overlap any other polygons?<br />
                > ><br />
                > >The only way I can think of is start the input square at a spot, and move it<br />
                > >by 1 unit at a time and keep checking ST_Overlap.<br />
                > >-- <br />
                > >View this message in context: http://old.nabble.com/Find-none-overlapping-spot-tp27366934p27366934.html<br />
                > >Sent from the PostGIS - User mailing list archive at Nabble.com.<br />
                > ><br />
                > >_______________________________________________<br />
                > >postgis-users mailing list<br />
                > >postgis-users@postgis.refractions.net<br />
                > >postgis.refractions.net/mailman/listinfo/postgis-users<br />
                > ><br />
                > ></div>
</body>
</html>