The simplest algorithm I'm aware of is to successively

• construct the smallest polygon enclosing n-1 points
• check if point n is inside the polygon
• if YES then it's already the smallest polygon enclosing n points
• if NO then include it as a new corner

The check is crucial, you need a scalar product of the point vector with orthogonal vectors on all edges pointing inside.

If the product is positiv it means the point is "inside" the edge.

Iff the point is inside all edges, it's inside the polygon.

Otherwise you extend the polygon by replacing all "outside" edges.

(Most probably you'll also need to move the points before doing the product, such that the edge goes thru (0,0) )

HTH and you get the idea.

I'm pretty tired, lacking the right vocabulary and typing into my mobile without possibility to scetch it on paper. :)

Thanks, LanX,

I agree with you that what I want is a "smallest convex hull". I'll see if I can get my head around the math involved.

say  substr+lc crypt(qw $i3 SI$),4,5

> I agree with you that what I want is a "smallest convex hull". 

Looking at the other answers I'm not sure anymore. A convex hull means a banana shape would be represented as a semicircle.

You seem to want a tight (not necessarily convex) vector graphic enclosing a sprite.

I think you could achieve this by improving the convex hull (by replacing long edges with concave triangles until all edges are sufficiently "short" or "tight")

Another problem I see are non-connected segments/territories . The shape of the USA would look very different if Alaska and Hawaii were included into just one hull ...

update

Found this http://stackoverflow.com/questions/7408470/given-a-vector-of-points-possibly-out-of-order-find-polygon-not-convex-hull

Pointing to the next problem There is no unique solution for a concave polygon

So starting from a convex hull and improving it till criteria are met is sensible.

Cheers Rolf
_{(addicted to the Perl Programming Language and ☆☆☆☆ :)
Wikisyntax for the Monastery}

I can't post images here but I came around this wikipedia article which should be of help understanding how the do product helps identifying distance and orientation of a point in respect to an edge Scalar_projection

Cheers Rolf
_{(addicted to the Perl Programming Language and ☆☆☆☆ :)
Wikisyntax for the Monastery}

update

added clarification

Here's an attempt using strings ( so I can do "inner" point removal with just one s/// ) and using vr's triple idea Re: Polygon Creation -- Request for Algorithm Suggestions ( so I can "walk" the perimeter by finding the closest unused point to the previous point.

#!/usr/bin/perl

# http://perlmonks.org/?node_id=1204060

use strict;
use warnings;

my @points = points();
my ($minx, $miny, $maxx, $maxy) = (
  $points[0][0], $points[0][1], $points[0][0], $points[0][1]);

for (@points)
  {
  my ($x, $y) = @$_;
  $minx > $x and $minx = $x;
  $miny > $y and $miny = $y;
  $maxx < $x and $maxx = $x;
  $maxy < $y and $maxy = $y;
  }

my $width = $maxx - $minx + 1;
my $width3 = $width * 3;
my $gridwidth = $width3 + 1;
my $height = $maxy - $miny + 1;
my @letters = ('A' .. 'Z', 'a' .. 'z'); # label points by letter seque
+nce

my $grid = ( '---' x $width . "\n" ) x $height x 3;

for (@points)
  {
  my ($x, $y) = @$_;
  for my $xx (0..2) # triple
    {
    for my $yy (0..2) # triple
      {
      substr $grid,
        (($y - $miny) * 3 + $yy) * $gridwidth + ($x - $minx) * 3 + $xx
+,
        1, 'O';
      }
    }
  }

#print $grid, "\n\n";

$grid =~ s/          # remove "inside" points
  (?<=O)
  (?<=O.{$width3})
  O
  (?=O)
  (?=.{$width3}O)
  / /gsx;

#print $grid, "\n";

my $output = (' ' x $width . "\n") x $height;

my $i = 0;
my @answerpoints;
my @available;

push @available, $-[0] while $grid =~ /O/g;
my $previous = shift @available;
place($previous);

while( @available )
  {
  (my $closest, @available) = map $_->[0],
    sort { $a->[1] <=> $b->[1] }
    map [ $_, distance($_, $previous) ],
    @available;
  $previous = $closest;
  place($closest);
  }

print "$output\n"; # for show

#use Data::Dump 'pp'; pp \@answerpoints; # the real answer :)

sub place
  {
  my $pos3 = shift;
  my ($x3, $y3) = ( $pos3 % $gridwidth, int $pos3 / $gridwidth );
  my ($x, $y) = (int $x3 / 3, int $y3 / 3);
  pos($output) = $y * ($width + 1) + $x;
  $output =~ s/\G /$letters[$i++ % @letters]/ and
    push @answerpoints, [ $x + $minx, $y + $miny ];
  }

sub distance # between two pos values
  {
  my ($from, $to) = @_;
  my ($x1, $y1) = ( $from % $gridwidth, int $from / $gridwidth );
  my ($x2, $y2) = ( $to % $gridwidth, int $to / $gridwidth );
  sqrt( ($x2 - $x1)**2 + ($y2 - $y1)**2 ); # sqrt may not be needed
  }

sub points
  {
  ... data points removed to shorten listing
  }
[download]

Outputs (using letters in sequence to show the order of the points):

                             A          
                      MNOPQRSB          
                    KL       C          
                    J        D          
                    I        E          
 k                 H          FG       O
j l               G             HIJKLMNP
i m              F                     Q
 h no            E                     R
  g  pq          D                     S
   f   rs        C                     T
   e     tuvw    B                     U
   d         xyzA                      V
   c                                   W
   baZ                                 X
      Y                                Y
      X                                Z
      W                                a
       V                               b
       U                               c
       T                               d
        S                              e
        R                              f
        Q                              g
         P                            h 
          ONMLK                       i 
               JIHGFED                j 
                      CBAz            k 
                          yxwvut      l 
                                s    m  
                                rqpon
[download]

Of course, the "real" answer is in @answerpoints (not shown because of length)

Well, it's too late/early today for any code (sorry), perhaps tomorrow if it won't look too stupid in the morning, and it appears like roboticus knows much better, but I started with this answer before his, so FWIW:

0. Slightly modify your algorithm to eliminate corner points (see below why).

1. Starting with original image, triple it, i.e. each pixel (point).

2. Apply your algorithm.

Original fragment:

# # # # .
# # # . .
# # . . .
# # # # .
# # . . .

After your algorithm:

# # # # .
o o # . .
o # . . .
o o # # .
# # . . .

Original was tripled, algorithm applied (corners eliminated),

###########.
...........#
.........##.
      ..#
      ..#
     .##.
   ..#
   ..#
   ..#
......#####.
...........#
......#####.
   ..#
   ..#
#####.

So, now every marked pixel is guaranteed to have only 2 neighbours.

4. Then it's trivial to start anywhere and just pick unused neighbour until polyline closed.

5. Scale polyline to original (integer division?).

6. Reduce it to eliminate same points as begin-end.

Here's some code. It occurred to me, that algorithm eliminating shape interior, in original post by golux, is actually simple kernel convolution in 2D, rolled out manually. Because of that, and because I don't like the idea of manipulating points one by one, I decided to process them "en masse", starting from original "image".

It looks like Imager can only do 1D convolution, PerlMagick is in somewhat sad state. So it's back to PDL again.

I tried to invent a kernel that would allow both to eliminate interior and to "round" corners in one pass, but unsuccessfully. Further, I couldn't invent such 2nd kernel, so that only one (instead of 2) comparison is required afterwards.

Interesting: walking direction along the outline happened to be counter-clockwise. Perhaps algorithm can be improved to allow to choose direction, from starting point.

use strict;
use warnings;
use feature    qw/ say /;
use List::Util qw/ first uniqnum /;
use PDL;
use PDL::Image2D;

# It's important that shape doesn't touch boundaries.
# Otherwise neighbours could be found across image edges,
# or substr (below) can look outside argument.

my ( $w, $h ) = ( 42, 33 );
my $str = << 'END';
..........................................
..............................#...........
.......................########...........
.....................##########...........
.....................##########...........
.....................##########...........
..#.................#############.......#.
.###...............######################.
.###..............#######################.
..####............#######################.
...#####..........#######################.
....######........#######################.
....##########....#######################.
....#####################################.
....#####################################.
....#####################################.
.......##################################.
.......##################################.
.......##################################.
........#################################.
........#################################.
........#################################.
.........################################.
.........################################.
.........################################.
..........##############################..
...........#############################..
................########################..
.......................#################..
...........................#############..
.................................######...
.................................#####....
..........................................
END
$str =~ tr/.#\n/01/d;

my ( $w_, $h_ ) = ( 3 * $w, 3 * $h );
my $in  = pdl([ split '', $str ])-> reshape( $w, $h );
my $img = zeroes( $w_, $h_ );
rescale2d( $in, $img );

my $kernel_1 = pdl([ qw/
 0 -1  0
-1  4 -1
 0 -1  0
/])-> reshape( 3, 3 );

my $kernel_2 = pdl([ qw/
 0 -2  0
-1  5 -1
 0 -2  0
/])-> reshape( 3, 3 );

$img = conv2d( $img, $kernel_1 ) > 0;
$img = conv2d( $img, $kernel_2 );
$img = ( $img == 1 ) + ( $img >= 3 );

# Dump image any time for inspection,
# terminal must be wider than $w_ (126).
#
# my @lst = $img-> list;
# say splice @lst, 0, $w_ while @lst;

# Back to Perl from PDL-land.

my $s = ${ $img-> byte-> get_dataref };

my @checks = (                  # 8 neighbours
-$w_ - 1,  -$w_, -$w_ + 1,
      -1,               1,
 $w_ - 1,   $w_,  $w_ + 1,
);

my $i = CORE::index $s, "\1";   # 1st point
my @list = ( $i );
substr $s, $i, 1, "\0";

while () {
    my $j = first { "\1" eq substr $s, $i + $_, 1 } @checks;
    last unless defined $j;
    $i += $j;
    push @list, $i;
    substr $s, $i, 1, "\0";
}

die if CORE::index( $s, "\1" ) >= 0;        # can't be

# Scale point coordinates back to original,
# squash duplicates.

@list = uniqnum map {
    use integer;
    my $x = $_ % $w_ / 3;
    my $y = $_ / $w_ / 3;
    $x + $y * $w
} @list;

# @list uniquely identifies sequence to create polyline,
# can be converted to (x,y) pairs if required.
# Below is simple transformation to 2D picture.

my $out = '.' x ( $w * $h );
my $n   = 0;
for ( @list ) {
    substr $out, $_, 1, $n ++;
    $n %= 10;
}
say substr $out, 0, $w, '' while $out;
[download]

And then:

..........................................
..............................0...........
.......................76543212...........
.....................98.......1...........
.....................0........0...........
.....................1........9...........
..5.................2..........87.......9.
.6.4...............3.............65432108.
.7.3..............4.....................7.
..8.21............5.....................6.
...9..09..........6.....................5.
....0...87........7.....................4.
....1.....6543....8.....................3.
....2.........2109......................2.
....3...................................1.
....456.................................0.
.......7................................9.
.......8................................8.
.......9................................7.
........0...............................6.
........1...............................5.
........2...............................4.
.........3..............................3.
.........4..............................2.
.........5..............................1.
..........6............................0..
...........78901.......................9..
................2345678................8..
.......................9012............7..
...........................345678......6..
.................................9....5...
.................................01234....
..........................................
[download]

P.S. And isn't it great that regex engine has finally a day off?

Update. Damn... Of course 2nd convolution and kernel weren't necessary. Convex corners are "2"s after the 1st one. A replacement for fragment from applying a kernel till die statement, with other (I hope so) improvements:

$img  = conv2d( $img, $kernel ) == 1;
$img += 48;

my $s = ${ $img-> byte-> get_dataref };

my @checks = (              # increments to
-$w_ - 1 ,1, 1,             # 8 neighbours
 $w_ - 2,    2,
 $w_ - 2, 1, 1,
);

my $i = CORE::index $s, 1;  # 1st point
my @list = ( $i );
substr $s, $i, 1, 0;

push @list, $i
    while first { substr $s, $i += $_, 1, 0 } @checks;
[download]

Update 2. Oh, DAMN... What a frustration. The uniqnum description says:

Filters a list of values to remove subsequent duplicates

(emphasis mine), and I didn't test it.

>perl -MList::Util=uniqnum -E "say for uniqnum 1,1,2,1
1
2
[download]

Ah? I thought, like:

>perl -E "say '1121'=~tr/12/12/sr"
121
[download]

Then, are any duplicates removed? Why wasting time on word "subsequent"? Part of my code to be replaced, uniqnum dumped for good, core module or not:

my $prev = -1;
@list = grep { 
    my $res = $prev != $_; 
    $prev = $_; 
    $res 
} map {
    use integer;
    my $x = $_ % $w_ / 3;
    my $y = $_ / $w_ / 3;
    $x + $y * $w
} @list;
[download]

damn...

I wanted to see what an edge walker looked like in the "strings/regex" domain...

#!/usr/bin/perl

# http://perlmonks.org/?node_id=1204060

use strict;
use warnings;

my @points = points();
my ($minx, $miny, $maxx, $maxy) = (
  $points[0][0], $points[0][1], $points[0][0], $points[0][1]);

for (@points)
  {
  my ($x, $y) = @$_;
  $minx > $x and $minx = $x;
  $miny > $y and $miny = $y;
  $maxx < $x and $maxx = $x;
  $maxy < $y and $maxy = $y;
  }

my $height = $maxy - $miny + 3;  # some useful stuff
my $width = $maxx - $minx + 3;
my $gw = $width + 1; # grid width (distance to down one row)
my $gwm3 = $gw - 3;
my @letters = ('A' .. 'Z', 'a' .. 'z'); # label points by letter seque
+nce
my @steps = (1, $gw+1, $gw, $gw-1, -1, -$gw-1, -$gw, -$gw+1); # by dir
+ection
my $grid = ( ' ' x $width . "\n" ) x $height;
my @answerpoints; # coordinates around edge

for (@points) # put points on grid (multiline string :)
  {
  my ($x, $y) = @$_;
  substr $grid, (($y - $miny + 1)) * $gw + ($x - $minx + 1), 1, '#';
  }

my $direction = 0; # start facing east (increases clockwise)
my $start = my $at = $grid =~ /(?<= )#/ ? $-[0] : die "empty"; # at to
+pleft

do # clockwise walk around edge
  {
  push @answerpoints, [ $at % $gw - 1 + $minx, int $at / $gw - 1 + $mi
+ny ];
  pos($grid) = $at - $gw - 1; # northwest corner neighbor
  $grid =~ /\G(.)(.)(.).{$gwm3}(.).(.).{$gwm3}(.)(.)(.)/s; # all neigh
+bors
  ("$1$2$3$5$8$7$6$4" x 2) =~ /^.{$direction} *(#)/ and # rotate & sca
+n
    $at += $steps[ $direction = ( $-[1] - 3 ) % 8 ]; # step in new dir
+ection
  }
until( $at == $start );

my $i = 0;
for (@answerpoints) # add letters for display if wanted
  {
  my ($x, $y) = @$_;
  pos($grid) = $x - $minx + 1 + ($y - $miny + 1) * $gw;
  $grid =~ s/\G#/$letters[$i++ % @letters]/; # label point if not
  }
print $grid;

#use Data::Dump 'pp'; pp \@answerpoints; # the real answer :)

sub points
  {
  [527,83],[527,84],[526,84],[525,84],[524,84],[523,84],[522,84],
  ... some points deleted to shorten listing ...
  [534,113],[533,113],[532,113],[531,113],[530,113],
  }
[download]

Outputs:

                              A           
                       MNOPQRSB           
                     KL#######C           
                     J########D           
                     I########E           
  k                 H##########FG       O 
 j#l               G#############HIJKLMNP 
 i#m              F#####################Q 
  h#no            E#####################R 
   g##pq          D#####################S 
    f###rs        C#####################T 
    e#####tuvw    B#####################U 
    d#########xyzA######################V 
    c###################################W 
    baZ#################################X 
       Y################################Y 
       X################################Z 
       W################################a 
        V###############################b 
        U###############################c 
        T###############################d 
         S##############################e 
         R##############################f 
         Q##############################g 
          P############################h  
           ONMLK#######################i  
                JIHGFED################j  
                       CBAz############k  
                           yxwvut######l  
                                 s####m   
                                 rqpon
[download]

Sure saves a lot of that ugly subscripting :)

UPDATE: New and Improved!! Now with Tk!! see Re^2: Polygon Creation -- Request for Algorithm Suggestions

New and Improved! Now with Tk !!

#!/usr/bin/perl

# http://perlmonks.org/?node_id=1204060

use strict;
use warnings;

my @points = points();

#@points = map [int rand 27, int rand 25 ], 1..700; # random test case

my ($minx, $miny, $maxx, $maxy) = (
  $points[0][0], $points[0][1], $points[0][0], $points[0][1]);

for (@points)
  {
  my ($x, $y) = @$_;
  $minx > $x and $minx = $x;
  $miny > $y and $miny = $y;
  $maxx < $x and $maxx = $x;
  $maxy < $y and $maxy = $y;
  }

my $height = $maxy - $miny + 3;  # some useful stuff
my $width = $maxx - $minx + 3;
my $gw = $width + 1; # grid width (distance to down one row)
my $gwm3 = $gw - 3;
my @letters = ('A' .. 'Z', 'a' .. 'z'); # label points by letter seque
+nce
my @steps = (1, $gw+1, $gw, $gw-1, -1, -$gw-1, -$gw, -$gw+1); # by dir
+ection
my $grid = ( ' ' x $width . "\n" ) x $height;

for (@points) # put points on grid (multiline string :)
  {
  my ($x, $y) = @$_;
  substr $grid, (($y - $miny + 1)) * $gw + ($x - $minx + 1), 1, '#';
  }

while( $^R = 0,                     # reset, find valid starting point
     $grid =~ /(?<=   .{$gwm3} )#(?= .{$gwm3} . )/s # top end - spikes
  or $grid =~ /(?<=   .{$gwm3} )#(?=..{$gwm3}   )/s # left end
  or $grid =~ /(?<=   .{$gwm3}.)#(?= .{$gwm3}   )/s # right end
  or $grid =~ /(?<= . .{$gwm3} )#(?= .{$gwm3}   )/s # bottom end
  or $grid =~ /(?<=   .{$gwm3} )#(?= .{$gwm3}(  #|#  ))/s # ul | ur en
+d
  or $grid =~ /(?<=(#  |  #).{$gwm3} )#(?= .{$gwm3}   )/s # ll | lr en
+d

  or $grid =~ /(?<=   .{$gwm3} )#(?=#.{$gwm3}(.#|  #))/s # top left
  or $grid =~ /(?<=   .{$gwm3}#)#(?= .{$gwm3}(#| #))/s # top right
  or $grid =~ /(?<=(.#.|  #).{$gwm3} )#(?=#.{$gwm3}   )(?{4})/s # bott
+om left
  or $grid =~ /(?<=(.#.|#..).{$gwm3}#)#(?= .{$gwm3}   )(?{4})/s # bott
+om right
  )
  {
  my $direction = $^R; # 0 is east (increases clockwise)
  my @answerpoints; # coordinates around edge
  my $start = my $at = $-[0]; # at topleft

  do # clockwise walk around edge
    {
    push @answerpoints, [ $at % $gw - 1 + $minx, int $at / $gw - 1 + $
+miny ];
    pos($grid) = $at - $gw - 1; # northwest corner neighbor
    $grid =~ /\G(.)(.)(.).{$gwm3}(.).(.).{$gwm3}(.)(.)(.)/s; # all nei
+ghbors
    $at += ("$1$2$3$5$8$7$6$4" x 2) =~ /^.{$direction} *(#)/ # rotate 
+& scan
      ? $steps[ $direction = ( $-[1] - 3 ) % 8 ] # step in new directi
+on
      : $start - $at; # force loop exit because scan failed
    }
  until( $at == $start );

  #use Data::Dump 'pp'; pp \@answerpoints; # the real answer :)

  my $i = 0;
  for (@answerpoints) # add letters for display if wanted
    {
    my ($x, $y) = @$_;
    pos($grid) = $x - $minx + 1 + ($y - $miny + 1) * $gw;
    $grid =~ s/\G#/$letters[$i++ % @letters]/; # label point if not
    }
  print $grid;

  draw(@answerpoints); # for Tk
  }

sub draw
  {
  use Tk;
  my $size = 700;
  my @pts = map { ($_->[0] - $minx + 1) * $size / $gw + 1,
    ($_->[1] - $miny + 1) * $size / ($maxy - $miny + 2) + 1 } @_;
  @pts > 50 or return;
  my $mw = MainWindow->new;
  $mw->geometry('+600+2');
  my $c = $mw->Canvas(-width => $size, -height => $size)->pack;
  $c->createPolygon(@pts, -fill => 'green',
    -width => 7, -outline => 'black');
  $c->createOval($pts[0] - 10, $pts[1] - 10, $pts[0] + 10, $pts[1] + 1
+0);
  $mw->Button(-text => 'Exit', -command => sub {$mw->destroy},
    )->pack(-fill => 'x', -expand => 1);
  MainLoop;
  }

sub points
  {
  [527,83],[527,84],[526,84],[525,84],[524,84],[523,84],[522,84],
  ... some points not shown to shorten listing ...
  [534,113],[533,113],[532,113],[531,113],[530,113],
  }
[download]

tybalt89:

Very neat! I'll have to study it and see how it works. I've had to put in a few more bounds-checks in mine to remove some problems, adding even more annoying subscripts...

...roboticus

When your only tool is a hammer, all problems look like your thumb.

Ultimately this will be used in a web page (for shapes representing towns in different counties)

Interesting. Many years ago, I developed Acme::EyeDrops -- which similarly had to solve the problem of how to represent arbitrary shapes for use in ascii art. If you look at Acme::EyeDrops Shape Reference, you'll see it defines two kinds of shapes:

• Built-in shapes. An algorithm is used to generate these types of shapes, for example a Sierpinski triangle. (Note that A::E has precious few built-in shapes; ideas for new built-in shapes welcome).
• ".eye file" shapes. These shapes are defined by a (simply formatted) .eye file, for example, a map of italy.

Two simple examples to give you a feel for how this works.

Running this program:

use Acme::EyeDrops qw(sightly);
print sightly({ Text            => 1,
                TextFiller      => '/\\',
                Shape           => 'siertri',
                # For 'siertri' built-in shape, Width=>5 means:
                #   height is 2**5 lines
                #   width  is 2 * 2**5 characters
                Width           => 5 });
[download]

                               /\
                              /\/\
                             /\  /\
                            /\/\/\/\
                           /\      /\
                          /\/\    /\/\
                         /\  /\  /\  /\
                        /\/\/\/\/\/\/\/\
                       /\              /\
                      /\/\            /\/\
                     /\  /\          /\  /\
                    /\/\/\/\        /\/\/\/\
                   /\      /\      /\      /\
                  /\/\    /\/\    /\/\    /\/\
                 /\  /\  /\  /\  /\  /\  /\  /\
                /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
               /\                              /\
              /\/\                            /\/\
             /\  /\                          /\  /\
            /\/\/\/\                        /\/\/\/\
           /\      /\                      /\      /\
          /\/\    /\/\                    /\/\    /\/\
         /\  /\  /\  /\                  /\  /\  /\  /\
        /\/\/\/\/\/\/\/\                /\/\/\/\/\/\/\/\
       /\              /\              /\              /\
      /\/\            /\/\            /\/\            /\/\
     /\  /\          /\  /\          /\  /\          /\  /\
    /\/\/\/\        /\/\/\/\        /\/\/\/\        /\/\/\/\
   /\      /\      /\      /\      /\      /\      /\      /\
  /\/\    /\/\    /\/\    /\/\    /\/\    /\/\    /\/\    /\/\
 /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
[download]

Running this program:

use Acme::EyeDrops qw(sightly);
print sightly({ Text            => 1,
                TextFiller      => 'Azzurri',
                Shape           => 'map_italy' });
[download]

                       Azzurr
                    iAzzurriAzz
                  urriAzzurriAzzurr
        iA   zzurriAzzurriAzzurriAzz
      urriAzzurriAzzurriAzzurriAzzur
  riAzzurriAzzurriAzzurriAzzurriAzz
  urriAzzurriAzzurriAzzurriAzzur
 riAzzurriAzzurriAzzurriAzzurr
 iAzzurriAzzurriAzzurriAzzurriA
zzurriAzzurriAzzurriAzzurriAzzu
rriAzzurriAzzurriAzzurriAzzurr
    iAzzurr    iAzzurriAzzurri
     Azzu        rriAzzurriAzzu
     rr           iAzzurriAzzurri
                  AzzurriAzzurriAzz
                   urriAzzurriAzzurr
                   iAzzurriAzzurriAzz
              u     rriAzzurriAzzurriA
           zzur       riAzzurriAzzurriA
          zzurr         iAzzurriAzzurriAz
          zurri           AzzurriAzzurriAzz
          urriA             zzurriAzzurriAzzurriA
           zzu                rriAzzurriAzzurriA
                                zzurriAzzurriAzzur
             ri                     AzzurriAzzurriAzz
        urriAzzu                      rriAzzurriAzzurriA
        zzurriAz                        zurriAzzurriAzzurri
         Azzurri                          AzzurriAzzu  rriAz
         zurriAz                            zurriAzz      urr
         iAzzurr                               iAzz        ur
         riAzzur                                riA
         zzurriA                                zzurr
         iAzz ur                                 riAzz
          ur                                     riAzz
                                                urri
                                               Azzu
                               r ri          Azzur
                              riAzzurriAzzurri Az
                              zurriAzzurriAzz
                                 urriAzzurri
                                    AzzurriA
                                       zzurr
                                         iAz
[download]

The primary purpose of Acme::EyeDrops is to auto-generate obfuscated, working Perl code ... so its shape pouring capabilities are fairly primitive. I'm just bringing it to your attention in case it gives you ideas for your current project, or in case it generates ideas for enhancing the shape pouring capabilities of Acme::EyeDrops.

You say enclosing polygon, by which I'd assume you need a bounding convex polyhedron; the embedded example however shows a non-convex shape. I don't think this makes much of a sense unless the points were ordered (lines) to begin with. In the example, you could reduce the volume by cutting wedges into the shape, thereby making some of the pruned "internal" points appear in the final shape.

I'm not sure what you mean by polyhedron. It's not a 3-dimensional shape, which a polyhedron is by definition.

And no, the points were not ordered to begin with -- they were taken from an image which had no extra information other than (X,Y) pairs of points, and an associated color for each point.

I did look at the module Math::ConvexHull, but determined it didn't do what I needed because if I go with the convex polygon defined for the set of points, it adds more to the shape than necessary, and eats into neighboring shapes to which the algorithm will also eventually be applied.

say  substr+lc crypt(qw $i3 SI$),4,5

Aye, a polygon, I stand corrected. It looks to me you have a set of pixels (small squares), or a sprite, and you want vector graphics out of it? The shapes are all solid, with no holes?

If you have pixels, they should fall on a grid. You could just walk the outline on the grid and be done with it.

I have only scanned the whole thread and I do not want to spoil your programming project but there is a nice list of algorithms on Wikipedia and a Perl implementation on CPAN. (Apologies if this has been mentioned somewhere but I failed to spot it...)

I don't think the OP really wants a hull and if then it wouldn't be convex. (Though stated otherwise)

It seems to be about tracing the - often concave - outline of a compact set of points - the pixel image of a county.

A hull is more general, it doesn't require that the enclosed points are connected.

Cheers Rolf
_{(addicted to the Perl Programming Language and ☆☆☆☆ :)
Wikisyntax for the Monastery}

Thanks for the clarification. I guess at latest while looking at the map of Italy I should have realized that "convex" is not a good description...