[postgis-users] Deleting an arbitrary polygon

[Martin Davis]

Yah, recursive CTEs should allow solving this problem in a single 
(complicated) SQL statement.  It's going to be great having them in 
PostgreSQL.   More complex spatial problems often seem to wind up 
reducing to graph traversal problems, which recursive CTEs should be 
able to express nicely.

It will also be interesting to see how the performance compares to 
manually coding iteratively in pgplsql...

Obe, Regina wrote:
> I'm hoping these tricks (well maybe not this particular example) will be
> much easier when 8.4 comes out and supports WITH RECURSIVE CTEs.  I
> think the 8.4 beta already has a good chunk of the WITH RECURSIVE
> functionality in it, but sadly haven't had a chance to test drive it.
> It would be interesting to see how it performs in these type of use
> cases.
>
> For those wondering - WITH RECURSIVE is along the lines of what I think
> Martin said he loved about Oracle their CONNECT BY 
>
> http://lin-ear-th-inking.blogspot.com/2007/09/grokking-hierarchical-quer
> ies-in-oracle.html
>
> though Oracle is badly none ANSI compliant granted it may be arguably
> more succinct in many cases
>
> http://asktom.oracle.com/pls/asktom/f?p=100:11:0::::P11_QUESTION_ID:5313
> 9879276132
>
> But it PostgreSQL 8.4 follows the ANSI standard CTE convention supported
> by SQL Server 2005+ 
>
> http://www.4guysfromrolla.com/webtech/071906-1.shtml#postadlink
>
> And DB II
> http://wiki.ibmdatabasemag.com/index.php/Celko_SQL_Puzzle
>
> Thanks,
> Regina
>
> -----Original Message-----
> From: postgis-users-bounces at postgis.refractions.net
> [mailto:postgis-users-bounces at postgis.refractions.net] On Behalf Of
> Burgholzer,Robert
> Sent: Friday, September 26, 2008 9:04 AM
> To: PostGIS Users Discussion
> Subject: RE: [postgis-users] Deleting an arbitrary polygon
>
> This is interesting, so I am kind of thinking in email ...
>
> Assumptions:
> - a good goal would be to eliminate the least number of polygons to
> create a non-overlapping set
> - polygons which overlap multiple polygons would therefore be better
> candidates, or at least
> - Martin is probably right that this will take multiple passes
>
> Query components:
> - Find # of polygons overlapped by each:  
>    SELECT a.poly_id, count(b.poly_id) as overlap 
>    FROM geo_table AS a, geo_table AS b 
>    WHERE st_intersects(a.the_geom, b.the_geom)
>       AND a.poly_id <> b.poly_id 
>    GROUP BY a.poly_id 
>    ORDER BY overlap DESC
>
> So, I repeat the following until my set has no more overlapping polygons
> DELETE from geo_table where poly_id in (
> SELECT poly_id FROM 
>    ( SELECT a. poly_id, count(b. poly_id) as overlap 
>      FROM geo_table AS a, geo_table AS b 
>      WHERE intersects(a.the_geom, b.the_geom)
>         AND a. poly_id <> b. poly_id
>      GROUP BY a. poly_id
>      ORDER BY overlap DESC
>    ) as foo
> LIMIT 1 
> );
>
> -- and I check to see how many remain with:
> SELECT a. poly_id, count(b. poly_id) as overlap 
> FROM geo_table AS a, geo_table AS b 
> WHERE intersects(a.the_geom, b.the_geom)
>    AND a. poly_id <> b. poly_id
> GROUP BY a. poly_id
> ORDER BY overlap DESC
>
>
> The ORDER BY clause is a crucial part of this I think.  If you order
> DESC, as I have done, then you favor leaving small "islands" in your
> space, since you would most likely (but not certainly) be targeting
> large polygons that contained the smaller ones.  If you were to choose
> the opposite approach, deleting polygons with smaller numbers of
> overlaps, you may tend to weed out small islands, and leave large
> "continents".  However, there would be cases in which these
> probabilities were not true.  Regardless, there would most likely be a
> different resulting set of remaining, non-overlapping polygons from
> either approach.
>
> HTH,
> r.b.
>
> Robert W. Burgholzer
> Surface Water Modeler
> Office of Water Supply and Planning
> Virginia Department of Environmental Quality
> rwburgholzer at deq.virginia.gov
> 804-698-4405
> Open Source Modeling Tools:
> http://sourceforge.net/projects/npsource/
>
> -----Original Message-----
> From: postgis-users-bounces at postgis.refractions.net
> [mailto:postgis-users-bounces at postgis.refractions.net] On Behalf Of
> Martin Davis
> Sent: Thursday, September 25, 2008 8:13 PM
> To: PostGIS Users Discussion
> Subject: Re: [postgis-users] Deleting an arbitrary polygon
>
> AFAIK there is no way to do this in a single pass. 
>
> One way to do it iteratively is:
> - add a column which will flag features which are "nonoverlapping" (and 
> which will be kept)
> - choose one feature and flag it as nonoverlapping
> - iterate {
>     - delete all features which overlap some "nonoverlapping" feature
>     - pick an unmarked feature and flag it as "nonoverlapping"
>     - exit if all features are flagged as "nonoverlapping"
> }
>
> This is probably going to be slow...
>
> Dylan Lorimer wrote:
>   
>> Hey PostGIS Friends, here's a problem that's stumping me, hoping you
>>     
> can help:
>   
>> I have a bunch of polygons, many of which overlap with each other. I
>> would like to trim down the set of polygons to only those that do not
>> overlap. I'm not particular about which I delete, so long as they
>> overlap by a certain %.
>>
>> Any thoughts on how to do this? I was trying for a self join but can't
>> figure out how to not to delete all polygons that overlap.
>>
>> Cheers,
>> dylan
>> _______________________________________________
>> postgis-users mailing list
>> postgis-users at postgis.refractions.net
>> http://postgis.refractions.net/mailman/listinfo/postgis-users
>>
>>   
>>     
>
>   

-- 
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022