*almost

There are are still occasional "extra" points being included, but I believe these are being output (wrongly) from M::G::V, as with the duplicated points I noted here. And once that problem has been solved, the spurious edges that show up occasionally will go away.

How it works

If you look at the example (requires FireFox) that samtregar posted, and consider just the edges that form the overall outline of the shaded polygons. In the set of all the edges of all the small polygons, all the "internal edges", that is edges that are not part of the bounding polygon, will appear in two of the smaller polygons. But those edges making up the bounding polygon will only appear in one.

By processing all the edges from all the small polygons through a filter selecting just those edges that only appear once in the total set of edges, you will be left with just those edges that make up the bounding polygon. So, the problem then becomes one of simply (!) re-constructing the boundary polygon from that disordered set of edges.

The exclamation mark is because although the final cut of the reconstruction (reordering) process is actually quite simple, arriving at the algorithm was anything but.

The problem on a simple scale, is that you end up with an array of arrays of arrays like this:

[
  [[177, 518], [205, 353]],
  [[259, 614], [177, 518]],
  [[205, 353], [383, 489]],
  [[259, 614], [380, 498]],
  [[367, 274], [415, 456]],
  [[464, 246], [367, 274]],
  [[380, 498], [486, 622]],
  [[383, 489], [415, 456]],
  [[452, 160], [464, 246]],
  [[490, 135], [452, 160]],
  [[486, 622], [579, 606]],
  [[490, 135], [586, 244]],
  [[579, 606], [632, 643]],
  [[586, 244], [717, 227]],
  [[632, 643], [719, 549]],
  [[717, 227], [746, 269]],
  [[719, 549], [775, 555]],
  [[746, 269], [856, 312]],
  [[775, 555], [856, 312]],
]
[download]

And you need to re-order them so that the (right-most) end of one edge mates up with the start (left-most) end of the next. And do this all the way down the list until the end of the last edge matches the start of the first. You can then take the set of starts (or ends) and the first (or last) point from the other end, and you end up with an ordered set of points to construct the closed polygon.

The problem is that the end of the first point could match up with any of the subsequent edges. Start or end. Having tried half a dozen combinations of: sorting and then swapping; or swapping then sorting; or sorting, swapping some and then resorting (rinse, repeat); I finally arrived at the algorithm by working through the above dataset manually and noting what I did. I then reproduced that in code. The result is the following subroutine:

sub edges2poly {
    my $edges = shift; ## Ref to the AoAoA above.

    ## For each edge in the list (which is reordered as this loop prog
+resses)
    for my $i ( 0 .. $#$edges - 1 ) {

        ## Stringyfy the end-point
        my $target = "@{ $edges->[ $i ][ 1 ] }";

        ## And scan the remain edges
        for my $j ( $i + 1 .. $#$edges ) {
            ## Comparing the target, 

            ## first against the start
            if( $target eq "@{ $edges->[ $j ][ 0 ] }" ) { 
                ## found the next edge correctly oriented.
                last if $j == $i + 1; ## nowt to do if its already the
+ next edge
            }
            ## and then the end of each
            elsif( $target eq "@{ $edges->[ $j ][ 1 ] }" ) { 

                ## Found it, but its ends need swapping
                @{ $edges->[ $j ] } = reverse @{ $edges->[ $j ] };

                last if $j == $i + 1; ## nowt more to do if its the ne
+xt edge
            }
            else {
                next; ## try the next edge
            }
            ## If we got here, we found it (and possible swapped then 
+ends,
            ## But it is in the wrong place in the list, so swap the e
+dges.
            @{ $edges }[ $i+1, $j ] = @{ $edges }[ $j, $i+1 ];
            last; ## And skip to the next target
        }

    }
    ## return an AoA of just the required points for the bounding poly
+gon.
    return( $edges->[ 0 ][ 0 ], map{ $_->[ 1 ] } @$edges );
}
[download]

The POC code uses GD to plot the points (in red), the Voronoi diagram (in green), and the boundary polygon (in blue). (Update: Added the pre-filtered polygons in grey to show that incomplete polygons are being removed prior to the 1-edging process).

There are three operational modes: -PAT=[square|diamond|random]. The square and diamond options show up the duplicate vertices problem noted elsewhere, (but I filter these out) and show that the algorthm works.

The random (default) pattern takes another option (-N=nnn) which is the number of randomly generated points passed to M::G::V to start the thing off. This demonstrates that the algorithm is very fast, but also shows up the fact that my filtering process is not succeeding in filtering all the spurious elements.

If you run with the default (-PAT=random -N=20), then most of the time everything is fine. If you increase that to -N=100, it will sometimes be fine, but will often show the effects of the spurious points. Run with -N=1000 and it will (mostly) draw the full bounding polygon, but usually with a few "extra" edges.

Update Added a couple of extra test modes: -PAT=hex|hex2 which more clearly demonstrate the "spurious points" problem.

(If you run this on linux, you'll need to tweak the line:system 'voronoi.png'; to cause the program to display the resulting .png)

The code: ('scuse the mass of debug comments)