Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??

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.


In reply to Re: reordering segments to form a polygon by Corion
in thread reordering segments to form a polygon by dada

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • 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.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others rifling through the Monastery: (3)
As of 2024-03-29 01:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found