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

Andy Anderson aanderson at amherst.edu
Sun Jun 8 21:12:07 PDT 2008

```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.
>
> - Easy to implement.
>
> - 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

```