[postgis-users] Cutting a Polygon into Pieces with maximum Vertex number

[Andy Anderson]

How about this:

1) Construct the exterior boundary linestring of the polygon with  
ST_ExteriorRing(polygon).
    If ST_NumPoints(boundary) <= N, quit.
2) Set n = N.
3) Construct a linestring from the first and nth points of the boundary.
4) Test if the linestring intersects the polygon boundary at more than  
those two points,
    e.g. ST_Crosses(line, polygon) = true.
	a) If it crosses, reduce n by one.
	   (i) If n = 1, then shift to the second point in the polygon and  
repeat step (2).
	   (ii) Otherwise, repeat step (3).
	b) If it doesn't cross, it forms the boundary of a small enough  
polygon with no extra points.
	   Construct it and find its difference from the starting polygon.
	   With the result, repeat step (1).

This should work even with interior rings, but probably isn't the  
quickest implementation. In step (4)(a)(i), it might help to jump more  
than one point, since there's probably a concavity nearby. An  
incoherent jump is probably best e.g. the largest integer < N/2 that's  
not a divisor of N, to stagger the positions around the boundary.

If it's really important to minimize the number of polygons, you'll  
need to construct all sets of non-crossing linestrings and compare  
their number. In this case, you'd apply this algorithm for every  
point, without constructing the polygons as you go in step (4)(b). If  
the original polygon has M points, then if you find a linestring set  
whose number is Ceiling(M/N) that's a minimal set. When you find the  
smallest set you can construct the polygons.

-- Andy

On Jun 6, 2008, at 7:35 AM, Markus Schaber wrote:

> Hi,
>
> Currently, I have the Problem that I have to cut Polygons with more
> than N points in their outer ring into adjacent pieces with a maximum
> of N points each. (Inner rings are not present, currently, but may be
> later).
>
> The current (simple) approach is that we recursively split the  
> bounding
> box into 4 quarters, until each remaining piece has less than N  
> points.
>
> Advantage:
> - Easy to implement.
>
> Disadvantages:
> - Introduces new points (rounding errors etc.)
> - Splits polygons into more pieces than necessary
>
> We have some ideas of some better algorithm, but I wanted to check  
> here
> whether someone already has implemented something like this.
>
> Thanks,
> Markus
>
> -- 
> Markus Schaber | Logical Tracking&Tracing International AG
> Dipl. Inf.     | Software Development GIS
>
> Fight against software patents in Europe! www.ffii.org
> www.nosoftwarepatents.org
> _______________________________________________
> postgis-users mailing list
> postgis-users at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-users