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";
};
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.
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.