<HTML dir=ltr><HEAD><TITLE>Re: [postgis-users] Transform overlapping polygons to non-overlapping?</TITLE>
<META http-equiv=Content-Type content="text/html; charset=unicode">
<META content="MSHTML 6.00.2900.3354" name=GENERATOR></HEAD>
<BODY>
<DIV id=idOWAReplyText25254 dir=ltr>
<DIV dir=ltr><FONT face=Arial color=#000000 size=2>Brent,</FONT></DIV>
<DIV dir=ltr><FONT face=Arial size=2></FONT> </DIV>
<DIV dir=ltr><FONT face=Arial size=2>This might help reduce your problem set a bit. You don't care about the ones that don't overlap anything right. Hopefully there are a lot of those. So use the old LEFT JOIN trick</FONT></DIV>
<DIV dir=ltr><FONT face=Arial size=2></FONT> </DIV>
<DIV dir=ltr><FONT face=Arial size=2>Create new table</FONT></DIV>
<DIV dir=ltr><FONT face=Arial size=2></FONT> </DIV>
<DIV dir=ltr><FONT face=Arial size=2>INSERT INTO newtable(gid,the_geom)</FONT></DIV>
<DIV dir=ltr><FONT face=Arial size=2>SELECT a.gid, a.the_geom</FONT></DIV>
<DIV dir=ltr><FONT face=Arial size=2>FROM oldtable a LEFT JOIN oldtable b ON (a.gid <> b.gid AND ST_Overlaps(a.the_geom, b.the_geom))</FONT></DIV>
<DIV dir=ltr>WHERE b.gid IS NULL</DIV>
<DIV dir=ltr> </DIV>
<DIV dir=ltr>Next step create unique index on gid on new table</DIV>
<DIV dir=ltr> </DIV>
<DIV dir=ltr>DELETE FROM oldtable</DIV>
<DIV dir=ltr>WHERE gid IN(SELECT gid FROM newtable)</DIV>
<DIV dir=ltr> </DIV>
<DIV dir=ltr>Now all you are left to work with are your polygons that overlap each other.</DIV>
<DIV dir=ltr> </DIV>
<DIV dir=ltr>With those follow Kevin's lead by creating an intermediary workspace table</DIV>
<DIV dir=ltr> </DIV>
<DIV dir=ltr>Hope that helps,</DIV>
<DIV dir=ltr>Regina</DIV></DIV>
<DIV dir=ltr><BR>
<HR tabIndex=-1>
<FONT face=Tahoma size=2><B>From:</B> postgis-users-bounces@postgis.refractions.net on behalf of Kevin Neufeld<BR><B>Sent:</B> Wed 7/16/2008 2:24 PM<BR><B>To:</B> PostGIS Users Discussion<BR><B>Subject:</B> Re: [postgis-users] Transform overlapping polygons to non-overlapping?<BR></FONT><BR></DIV>
<DIV>
<P><FONT size=2>Ah, another reason to have topology finished in PostGIS. If only, eh?<BR><BR>Brent, what if you created a plpgsql script that simply iterated through<BR>a table of source polygons and slowly inserted them one at a time into a<BR>target table by:<BR><BR>foreach poly in source table<BR><BR> 1. move all bounding box overlaps in target table with current poly<BR>into a temp table.<BR> 2. take all polygons from your temp table and union the current poly<BR>using the techniques described on the wiki and what Regina suggested.<BR> 3. insert the individual polygons from the overlay back into the<BR>target table using ST_Dump.<BR><BR>end foreach.<BR><BR>It might take a while, but in the end, you would have a single<BR>topologically correct (non-overlapping) polygonal table.<BR><BR>You may want to insert the geometries ordered by some x,y grid so that<BR>your working area will more likely be cached in memory.<BR><BR>Also, you may want to perform vacuum once in while on your target table.<BR> It could bloat really quickly. So don't iterate through all the<BR>source polygons all at once.<BR><BR>Cheers,<BR>Kevin<BR><BR><BR>Brent Fraser wrote:<BR>> Regina,<BR>><BR>> I'm not convinced ST_Union is the way to go (using ST_Overlaps OR<BR>> ST_Intersects as a condition). Basically I want to iterate over the<BR>> collection (recursively?) clipping one polygon to another until I'm left<BR>> with no overlapping (or intersecting) polygons (planar topology). This<BR>> is sightly more complicated than the way I originally posed the problem<BR>> (I wanted to created slivers from the overlapping areas to get planar<BR>> topology).<BR>><BR>> A little background:<BR>><BR>> My polygons represent a classification of vegetation of a large area<BR>> of interest. In theory any point in the area of interest must fall in<BR>> one and only one polygon. Due to an artifact of my image segmentation<BR>> process, my polygons currently have slight overlap which I need to<BR>> "dissolve" (and I don't care which polygon the overlap sliver gets<BR>> dissolved into).<BR>><BR>> Thanks!<BR>> Brent.<BR>> Paragon Corporation wrote:<BR>>> One more question - you sure you want ST_Overlaps and not ST_Intersects.<BR>>> If one geometry sits completely inside another, it is not considered to<BR>>> overlap, but they do intersect.<BR>>> -----Original Message-----<BR>>> From: postgis-users-bounces@postgis.refractions.net<BR>>> [<A href="mailto:postgis-users-bounces@postgis.refractions.net">mailto:postgis-users-bounces@postgis.refractions.net</A>] On Behalf Of<BR>>> Paragon<BR>>> Corporation<BR>>> Sent: Wednesday, July 16, 2008 12:41 PM<BR>>> To: 'PostGIS Users Discussion'<BR>>> Subject: RE: [postgis-users] Transform overlapping polygons to<BR>>> non-overlapping?<BR>>><BR>>> Brent,<BR>>><BR>>> INSERT INTO temp3_lines (the_geom) SELECT ST_ExteriorRing(<BR>>> ST_GeometryN(the_geom, generate_series(1,<BR>>> ST_NumGeometries(the_geom)))) AS the_geom FROM temp2_polys;<BR>>><BR>>> Can be done more efficiently using ST_Dump<BR>>><BR>>> INSERT INTO temp3_lines (the_geom) SELECT<BR>>> ST_ExteriorRing((ST_Dump(the_geom)).geom) AS the_geom FROM<BR>>> temp2_polys;<BR>>><BR>>><BR>>> Regarding the unioning I mentioned - I thought about more why what I<BR>>> proposed had still overlapping polygons and I realized its because the<BR>>> grouping I proposed needs to be A recursive query (which means you'd<BR>>> need to<BR>>> wrap it in an sql or plpgsql<BR>>> function) since as it stands it would only find the first root<BR>>> overlaps and<BR>>> not the A overlap B overlap C (e.g. c would not be in the same<BR>>> grouping and<BR>>> A,B if it doesn't also overlap with A) .<BR>>><BR>>> So two ways<BR>>> 1) Write recursive query (using a plpgsql or sql helper function) -<BR>>> which I<BR>>> haven't given much thought to the most efficient way of doing that<BR>>><BR>>> Or<BR>>><BR>>> 2) Repeat the union thing I mentioned over and over again until you<BR>>> have a<BR>>> set that has no more overlapping polygons.<BR>>><BR>>> Then you do a ST_Dump to get back individual polygons.<BR>>><BR>>> Hope that helps,<BR>>> Regina<BR>>><BR>>><BR>>> -----Original Message-----<BR>>> From: postgis-users-bounces@postgis.refractions.net<BR>>> [<A href="mailto:postgis-users-bounces@postgis.refractions.net">mailto:postgis-users-bounces@postgis.refractions.net</A>] On Behalf Of Brent<BR>>> Fraser<BR>>> Sent: Wednesday, July 16, 2008 12:13 PM<BR>>> To: PostGIS Users Discussion<BR>>> Subject: Re: [postgis-users] Transform overlapping polygons to<BR>>> non-overlapping?<BR>>><BR>>> To all,<BR>>><BR>>> My quest for non-overlapping polygons continues:<BR>>><BR>>> I started with a table (temp_polys) of 3253 polygons (with some overlap)<BR>>> with a "class" attribute.<BR>>><BR>>> To get rid of overlapping polys with the same class value:<BR>>> CREATE TABLE temp2_polys as SELECT class, ST_UNION(the_geom) from<BR>>> temp_polys GROUP BY class;<BR>>><BR>>> This created a table of 32 multi-polygons (grouped by class). I still<BR>>> have<BR>>> to remove the overlap between polygons with different class values, so my<BR>>> plan is to convert to linestrings, node the linestrings, polygonize, and<BR>>> (re)assign the class value using StarSpan. So first:<BR>>><BR>>> Convert to linestrings:<BR>>> INSERT INTO temp3_lines (the_geom) SELECT ST_ExteriorRing(<BR>>> ST_GeometryN(the_geom, generate_series(1,<BR>>> ST_NumGeometries(the_geom)))) AS<BR>>> the_geom FROM temp2_polys;<BR>>><BR>>> This produced 1768 linestring records. Attempting to node the<BR>>> linestrings:<BR>>> INSERT INTO temp4_lines (the_geom) SELECT St_Union(the_geom) AS<BR>>> the_geom FROM temp3_lines;<BR>>><BR>>> Yikes! This query ran for 4.5 hours and crashed Postgres (1.8 gHz<BR>>> Windows<BR>>> XP, Postgres 8.3.3, PostGIS 1.3.3).<BR>>><BR>>> I dumped the temp3_lines table into a shapefile and asked OpenJump to<BR>>> node<BR>>> AND polygonize. That took 24 seconds.<BR>>><BR>>> Since the above data is a small sub-set of my 1.2 million polygons,<BR>>> OpenJump<BR>>> is not really a solution for cleaning the data all at once. Looks<BR>>> like some<BR>>> scripting is in order...<BR>>><BR>>> Brent<BR>>><BR>>><BR>>> Brent Fraser wrote:<BR>>>> Regina,<BR>>>><BR>>>> The "SELECT MAX..." query didn't work on my sub-set of 12800<BR>>>> polygons. It created 12643 polygons some of which overlap (I<BR>>>> expected more, not less, than the original).<BR>>>><BR>>>> I may try converting to linestrings, creating one "minimum bounding<BR>>>> rectangle" for the entire dataset, then doing an intersect of the<BR>>>> lines with the MBR. In my case this would be ok as there are not<BR>>>> attributes on the polygons yet.<BR>>>><BR>>>> Thanks!<BR>>>> Brent<BR>>>><BR>>>> Obe, Regina wrote:<BR>>>>> Brent,<BR>>>>> <BR>>>>> I guess it really depends on how exactly you want to achieve<BR>>>>> non-overlapping.<BR>>>>> If for example you are basing it on some sort of attribute and all<BR>>>>> your overlapping polygons are valid<BR>>>>> <BR>>>>> Then a simple<BR>>>>> <BR>>>>> SELECT ST_Union(the_geom) As newgeom, field1 FROM sometable GROUP BY<BR>>>>> field1<BR>>>>> <BR>>>>> I think will guarantee non-overlapping polygons because as part of<BR>>>>> the process of ST_Union - it would irradicate the overlapping<BR>>>>> regions to just create one. That is part of the reason why its so<BR>>>>> much slower than ST_Collect for example.<BR>>>>> <BR>>>>> For your exact case below - you would union all the overlapping<BR>>>>> polygons together which could be really slow depending on how many<BR>>>>> overlap. The query I would write to achieve that would be something<BR>>>>> like this<BR>>>>> <BR>>>>> SELECT MAX(a.gid) As newgid, ST_Union(a.the_geom) As the_geom FROM<BR>>>>> poly a GROUP BY (SELECT MAX(r.gid) FROM poly r<BR>>>>> WHERE (a.gid = r.gid OR ST_Overlaps(r.the_geom, a.the_geom)));<BR>>>>> <BR>>>>> Hope that helps,<BR>>>>> Regina<BR>>>>><BR>>>>> ---------------------------------------------------------------------<BR>>>>> ---<BR>>>>> *From:* postgis-users-bounces@postgis.refractions.net on behalf of<BR>>>>> Brent Fraser<BR>>>>> *Sent:* Fri 7/11/2008 12:14 PM<BR>>>>> *To:* PostGIS Users Discussion<BR>>>>> *Subject:* Re: [postgis-users] Transform overlapping polygons to<BR>>>>> non-overlapping?<BR>>>>><BR>>>>> To All,<BR>>>>><BR>>>>> There doesn't seem to be an obvious answer to the problem given<BR>>>>> below (aka cleaning polygons, creating planar polygons, etc). I did<BR>>>>> see a note on the PostGIS wiki wishlist to "Add a geometry cleaner".<BR>>>>> There is also a suggestion to convert to linestrings, node, then<BR>>>>> polygonize (while that may work for a small set of polygons, I've got<BR>>>>> 1.1 million to clean). JTS, Geos, etc will likely fail due to the<BR>>>>> large number of polygons so I'll need a different approach.<BR>>>>><BR>>>>> I'm considering writing some code to iterate through my table of<BR>>>>> polygons, cleaning a small subset at a time. I think using PostGIS<BR>>>>> for the geometry storage and spatial query/selection makes sense.<BR>>>>> Any suggestions on which API to use?<BR>>>>> GDAL's OGR<BR>>>>> PostgreSQL's libpq<BR>>>>> other?<BR>>>>><BR>>>>> Thanks!<BR>>>>> Brent Fraser<BR>>>>><BR>>>>> Brent Fraser wrote:<BR>>>>>> PostGIS'ers,<BR>>>>>><BR>>>>>> I've got a table of overlapping polygons. How can I make it a<BR>>>>>> table of non-overlapping polygons?<BR>>>>>><BR>>>>>> For example, if table "polys2" contains two polygons A1 and B1<BR>>>>>> which overlap. I'd like to create table "polys3" with polygons<BR>>>>>> A2, B2, C2, where C2 is the overlap region of A1 and B1, and A2 =<BR>>>>>> A1 - C2, and B2 =<BR>>>>>> B1 - C2.<BR>>>>>><BR>>>>>> Looking at the overlay operations in the JTS doc it looks like<BR>>>>>> doing an Intersection (to get only the overlapping area) then<BR>>>>>> adding the Symmetric Difference (to get the non-overlapping areas)<BR>>> might work.<BR>>>>>> Am I on the right track or is there an easier way (since all the<BR>>>>>> polygons are in one table)?<BR>>>>>><BR>>>>>> Thanks!<BR>>>>>> Brent Fraser<BR>>>>>> _______________________________________________<BR>>>>>> postgis-users mailing list<BR>>>>>> postgis-users@postgis.refractions.net<BR>>>>>> <A href="http://postgis.refractions.net/mailman/listinfo/postgis-users">http://postgis.refractions.net/mailman/listinfo/postgis-users</A><BR>>>>>><BR>>>>> _______________________________________________<BR>>>>> postgis-users mailing list<BR>>>>> postgis-users@postgis.refractions.net<BR>>>>> <A href="http://postgis.refractions.net/mailman/listinfo/postgis-users">http://postgis.refractions.net/mailman/listinfo/postgis-users</A><BR>>>>><BR>>>>> ---------------------------------------------------------------------<BR>>>>> ---<BR>>>>><BR>>>>> * The substance of this message, including any attachments, may be<BR>>>>> confidential, legally privileged and/or exempt from disclosure<BR>>>>> pursuant to Massachusetts law. It is intended solely for the<BR>>>>> addressee. If you received this in error, please contact the sender<BR>>>>> and delete the material from any computer. *<BR>>>>><BR>>>>> ---------------------------------------------------------------------<BR>>>>> ---<BR>>>>><BR>>>>> * Help make the earth a greener place. If at all possible resist<BR>>>>> printing this email and join us in saving paper. *<BR>>>>><BR>>>>> * *<BR>>>>><BR>>>>> * *<BR>>>>><BR>>>>><BR>>>>> ---------------------------------------------------------------------<BR>>>>> ---<BR>>>>><BR>>>>> _______________________________________________<BR>>>>> postgis-users mailing list<BR>>>>> postgis-users@postgis.refractions.net<BR>>>>> <A href="http://postgis.refractions.net/mailman/listinfo/postgis-users">http://postgis.refractions.net/mailman/listinfo/postgis-users</A><BR>>>> _______________________________________________<BR>>>> postgis-users mailing list<BR>>>> postgis-users@postgis.refractions.net<BR>>>> <A href="http://postgis.refractions.net/mailman/listinfo/postgis-users">http://postgis.refractions.net/mailman/listinfo/postgis-users</A><BR>>>><BR>>> _______________________________________________<BR>>> postgis-users mailing list<BR>>> postgis-users@postgis.refractions.net<BR>>> <A href="http://postgis.refractions.net/mailman/listinfo/postgis-users">http://postgis.refractions.net/mailman/listinfo/postgis-users</A><BR>>><BR>>><BR>>> _______________________________________________<BR>>> postgis-users mailing list<BR>>> postgis-users@postgis.refractions.net<BR>>> <A href="http://postgis.refractions.net/mailman/listinfo/postgis-users">http://postgis.refractions.net/mailman/listinfo/postgis-users</A><BR>>><BR>>><BR>>> _______________________________________________<BR>>> postgis-users mailing list<BR>>> postgis-users@postgis.refractions.net<BR>>> <A href="http://postgis.refractions.net/mailman/listinfo/postgis-users">http://postgis.refractions.net/mailman/listinfo/postgis-users</A><BR>>><BR>> _______________________________________________<BR>> postgis-users mailing list<BR>> postgis-users@postgis.refractions.net<BR>> <A href="http://postgis.refractions.net/mailman/listinfo/postgis-users">http://postgis.refractions.net/mailman/listinfo/postgis-users</A><BR>_______________________________________________<BR>postgis-users mailing list<BR>postgis-users@postgis.refractions.net<BR><A href="http://postgis.refractions.net/mailman/listinfo/postgis-users">http://postgis.refractions.net/mailman/listinfo/postgis-users</A><BR></FONT></P></DIV></BODY></HTML>