Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

Is there a convenient way to split a polygon into n parts, more-or-less equal in size in PostGIS?

share|improve this question
    
Equal area or equal size (i.e. similar width and height)? –  Anthony -GISCOE- Feb 3 '11 at 14:21
    
Area, regardless of proportions. –  Adam Matan Feb 3 '11 at 14:22
1  
related post gis.stackexchange.com/questions/5300/… –  Kirk Kuykendall Feb 3 '11 at 15:26
    
I am suprised there is not a solution for this in R spatial –  Brad Nesom Feb 4 '11 at 21:21

2 Answers 2

up vote 6 down vote accepted

This is an old problem with no simple solution. The only approach that I came across is to make a function that you give a heading and the number of parts and the computer make trials until it gets equal areas. There is a LISP function with that in AutoCAD. In postgis it works the same, here is an excerpt of PostGIS in Action from Manning, this code splits a polygon in two equal parts:

WITH RECURSIVE
ref(the_geom, env) AS (
SELECT the_geom,
ST_Envelope(the_geom) As env,
ST_Area(The_geom)/2 As targ_area,
1000 As nit
FROM us.states
WHERE state = 'Idaho'
),

T(n,overlap) AS (
VALUES (CAST(0 As Float),CAST(0 As Float))
UNION ALL
SELECT n + nit, ST_Area(ST_Intersection(the_geom, ST_Translate(env, n+nit, 0)))
FROM T CROSS JOIN ref
WHERE ST_Area(ST_Intersection(the_geom, ST_Translate(env, n+nit, 0)))> ref.targ_area
) ,  

bi(n) AS
(SELECT n
FROM T
ORDER BY n DESC LIMIT 1)  

SELECT bi.n,
ST_Difference(the_geom, ST_Translate(ref.env, n,0)) As geom_part1,
ST_Intersection(the_geom, ST_Translate(ref.env, n,0)) As geom_part2
FROM bi CROSS JOIN ref;
share|improve this answer

One approach might be to split the polygon completely into triangles, each with a given area. Then it would be a matter of trying to group those (adjacent) triangles back into polygons of (more-or-less) size area/n. This would be a sort of customized version of "subset sum" or "knapsack" problem (and I wouldn't know how to start with that with PostGIS).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.