Building polygons from a polylines

[Stephen Woodbridge]

Tyler Mitchell wrote:

> Anyone have nifty tricks for some basic building of polygons from lines in a
> shape file?  Let's assume my data is good and clean - any tips?

The (an) algorithm for this is as follows:

1) convert end points into nodes with unique ids based on unique points
in space (define unique points in space based on a tolerance to avoid
numerical rounding issues.

2) build a connectivity graph, i.e.. for any node A it is connected to
B,C,... by taking each line (node A to node B) and associating A is
connected to B and B is connected to A.

3) pick and arbitrary node (like node A) and build a chain A connected
to  N, remove A-N and N-A from the graph, then N connected to X, remove
N-X and X-N

NOTE: you can have more then one connections between nodes, so you
should be prepared to handle multiple X-N instances.

When you run out of connection in the chain above. Scan the graph for
Additional start nodes (as you may have more than one loop. and generate
additional loops. If there are no additional loops then you are done.

This does not account for right-handed or left-handed ordering of the
polygons, so if you care you will need to add a step to order them
before you output them.

There are also some degenerate cases that this will handle but that you
might want to deal with, like:

What is a polygon with one edge? what is the shape doing?
Holes in polygons?
Two polygons connected at a single point like a doughnut with the hole
touching the outer edge or a figure eight.

In general mapserver handles these pretty well but you should test these
to make sure you are building usable polygons.

Hope this helps,
   -Steve W.