Your problem description is a bit vague, or rather, I see a problem with the direction of the lines. If you can guarantee that all lines will be clockwise (or counterclockwise), then my approach will work. If you cannot guarantee that, or a point has more than one line ending or starting at it, you will need to modify the algorithm to use two hashes or to record both directions of each line.

The basic idea is as follow:

Currently, you are rescanning the whole list of lines every time you want to add a new point to your polygon. My approach is to scan the whole list two times. In the first pass, you record every line in a hash, mapping the start point to its end point. In the second pass, you iterate through the hash from any point, and follow wherever the value of that point leads (as a key in the hash).

my %end_point;

# First, scan the list for all start points:
foreach my $line (@seg) {
  my $start = join "|", $line->[0], $line->[1];
  my $end = join "|", $line->[2], $line->[3];
  die "Point ($start) has more than one line starting at it: ($start) 
+-> ($end_point{$start}) and ($start) -> ($end)"
    if $start_point{$start};
  $end_point{$start} = $end;
};

# Now, jut select an arbitrary point, and trace our 
# polygon. If there are keys left after the target
# of our current point does not exist anymore, the list
# of points does not describe one closed polygon
my $start = join "|", $seq[0]->[0], $seq[0]->[1];
my $cur = $start;
while (exists $end_point{$cur}) {
  print "($cur) -> $end_point{$cur}\n";
  $cur = delete $end_point{$cur};
};
if (keys %end_point) {
  warn "The list did not describe one closed polygon:\n";
  warn "Started at ($start), got to ($cur)\n";
  warn "Left over vertices:\n";
  warn "$_ -> $end_point{$_}\n"
    for (keys %end_point);
  die "Error in polygon list";
};
[download]

The code is untested, but I guess that's the closest you'll get with an unsorted list. If your list is (partially) sorted in a good way, you might be able to skip the first scan which creates the lookup hash. It also might be faster to use a multi-dimensional hash depending on $;, but I prefer to build the hash keys myself.