<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
Brent, good to see someone else having fun with this issue! We worked
through it a couple of months ago, established a procedure, but had
some continuing issues with robustness and performance with large
datasets. <br>
<br>
What I wanted out of the analysis was a 'flat' geometry table with a
one to many join back to attributes from the input geometries. The
approach we used was to first find the overlaps (using a method similar
to the left join below), then apply this process:<br>
1) Converting polygons -> lines
<br>
2) Converting lines -> points
<br>
2) Add intersecting nodes where lines cross.
<br>
3) Build lines from points & nodes
<br>
4) Polygonize new lines.<br>
<br>
We also experimented with using a UNION of the lines followed by the
POLYGONIZE (similar to the methodology that JUMP uses I believe).
There are generally some robustness issues with either of these
processes. We have also used the intersection and difference method
you describe, which has worked well on small subsets, but is
problematic on large sets. <br>
<br>
We ended up utilizing Grass to complete the analysis, as it was faster
and more dependable. Good luck, if you want the sql that we used, let
me know and I can send it to you. <br>
<pre class="moz-signature" cols="72">Dan Erikson
</pre>
Obe, Regina wrote:
<blockquote
cite="mid:53F9CF533E1AA14EA1F8C5C08ABC08D20197A130@ZDND.DND.boston.cob"
type="cite">
<title>Re: [postgis-users] Transform overlapping polygons to
non-overlapping?</title>
<meta http-equiv="Content-Type" content="text/html; ">
<meta content="MSHTML 6.00.2900.3354" name="GENERATOR">
<div id="idOWAReplyText25254" dir="ltr">
<div dir="ltr"><font color="#000000" face="Arial" size="2">Brent,</font></div>
<div dir="ltr"> </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"> </div>
<div dir="ltr"><font face="Arial" size="2">Create new table</font></div>
<div dir="ltr"> </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>
<a class="moz-txt-link-abbreviated" href="mailto:postgis-users-bounces@postgis.refractions.net">postgis-users-bounces@postgis.refractions.net</a> 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: <a class="moz-txt-link-abbreviated" href="mailto:postgis-users-bounces@postgis.refractions.net">postgis-users-bounces@postgis.refractions.net</a><br>
>> [<a moz-do-not-send="true"
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: <a class="moz-txt-link-abbreviated" href="mailto:postgis-users-bounces@postgis.refractions.net">postgis-users-bounces@postgis.refractions.net</a><br>
>> [<a moz-do-not-send="true"
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:* <a class="moz-txt-link-abbreviated" href="mailto:postgis-users-bounces@postgis.refractions.net">postgis-users-bounces@postgis.refractions.net</a>
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>
>>>>> <a class="moz-txt-link-abbreviated" href="mailto:postgis-users@postgis.refractions.net">postgis-users@postgis.refractions.net</a><br>
>>>>> <a moz-do-not-send="true"
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>
>>>> <a class="moz-txt-link-abbreviated" href="mailto:postgis-users@postgis.refractions.net">postgis-users@postgis.refractions.net</a><br>
>>>> <a moz-do-not-send="true"
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>
>>>> <a class="moz-txt-link-abbreviated" href="mailto:postgis-users@postgis.refractions.net">postgis-users@postgis.refractions.net</a><br>
>>>> <a moz-do-not-send="true"
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>
>>> <a class="moz-txt-link-abbreviated" href="mailto:postgis-users@postgis.refractions.net">postgis-users@postgis.refractions.net</a><br>
>>> <a moz-do-not-send="true"
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>
>> <a class="moz-txt-link-abbreviated" href="mailto:postgis-users@postgis.refractions.net">postgis-users@postgis.refractions.net</a><br>
>> <a moz-do-not-send="true"
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>
>> <a class="moz-txt-link-abbreviated" href="mailto:postgis-users@postgis.refractions.net">postgis-users@postgis.refractions.net</a><br>
>> <a moz-do-not-send="true"
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>
>> <a class="moz-txt-link-abbreviated" href="mailto:postgis-users@postgis.refractions.net">postgis-users@postgis.refractions.net</a><br>
>> <a moz-do-not-send="true"
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>
> <a class="moz-txt-link-abbreviated" href="mailto:postgis-users@postgis.refractions.net">postgis-users@postgis.refractions.net</a><br>
> <a moz-do-not-send="true"
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>
<a class="moz-txt-link-abbreviated" href="mailto:postgis-users@postgis.refractions.net">postgis-users@postgis.refractions.net</a><br>
<a moz-do-not-send="true"
href="http://postgis.refractions.net/mailman/listinfo/postgis-users">http://postgis.refractions.net/mailman/listinfo/postgis-users</a><br>
</font></p>
</div>
<pre wrap="">
<hr size="4" width="90%">
_______________________________________________
postgis-users mailing list
<a class="moz-txt-link-abbreviated" href="mailto:postgis-users@postgis.refractions.net">postgis-users@postgis.refractions.net</a>
<a class="moz-txt-link-freetext" href="http://postgis.refractions.net/mailman/listinfo/postgis-users">http://postgis.refractions.net/mailman/listinfo/postgis-users</a>
</pre>
</blockquote>
</body>
</html>