Subroutine Subtrefuge

AF_One has asked for the wisdom of the Perl Monks concerning the following question:

Perl Wizards,

I've written an algorithm that finds the intersection of two lines. I am desperately trying to pass scalar values as arguments to this subroutine from a hash of arrays. Each array contains vertices for a four-sided polygon.

Here's what I got:


$myPolygons = 

"<tag>
<name>A</name>
     <points>-1.1,2,0 -3.1,4,0 -5.1,6,0 -7.1,8,0 1,2,0</points>
<name>C</name>
     <points>9,-8.1,0 7,-6.1,0 5,-4.1,0 3,-2.1,0 9,-8.1,0</points>
</tag>";

while ($myFile =~ m{<tag>(.*?)</tag>}gs)
     {
     $tag = $1;
     if ($tag =~ m{<name>(.*?)</name>}gs)
          {
          $name = $1;
      if ($tag =~ m{<points>(.*)</points>}g)
           {
           $points = $1;
           while ($points =~ m{\G(-?\d*\.?\d*),0*\s*}gs)
                      {
                      push @{$points_by_name{$name}}, $1;
                      }
                }
           }
      }
[download]

Each hash key has values in the form of an array reference which stores the associated numbers. Each element contains a single value and the zeros were omitted. I would like to pass these values to the subroutine that accepts eight scalars, each of which are the endpoints of the two lines that are being evaluated.

@_ = ($x0, $y0, $x1, $y1, $x2, $y2, $x3, $y3)
[download]

However, in order for the subroutine to work correctly, it can only accept the first four values from this hash:

$x0, $y0, $x1, $y1
[download]

How do I step through the first hash, passing only four values from each key at a time? In other words, the following will be passed as arguments to the subroutine:

@{$points_by_name{$key}}[0..3];
@{$points_by_name{$key}}[2..5];
@{$points_by_name{$key}}[4..7];
@{$points_by_name{$key}}[6..9];
[download]

...until all the values from the current key have been passed, then on to the next key's array; these values will advance by two until the end of each array that is associated with each key. This is my best attempt:

foreach my $key (keys %points_by_name)
    {
    foreach (@{$points_by_name{$key}}
        {
        for (my $i=0; $i<=$#{$points_by_name{$key}} $i+=2)
            {
            sub(@{$points_by_name{$key}}[$i..$i+3], $x2, $y2, $x3, $y3
+)
            }
        }
    }
[download]

Additionally, the last four arguments of the subroutine will be passed from a seperate, but similar hash as the one used above. In order to find an intersection of lines, the first four arguments from the hash above must be measured against ALL values in the other hash's arrays before the first four values may advance to the next two pairs from within each array.

The "other hash" should push its arguments something like the following:

foreach my $key (keys %other_hash)
    {
    foreach (@{$other_hash{$key}}
        {
        for (my $i=0; $i<=$#{$points_by_name{$key}} $i+=2)
            {
            my @temp = @{$other_hash{$key}}[$i..$i+3]
            foreach (@temp)
                {
                sub($x0, $y0, $x1, $y1, @temp)
                }
            }
        }
    }
[download]

The only problem with these approaches (aside from the obvious) is that there is no way to keep track of what key is being evaluated (...I think). The ingestion of the first and last four arguments must start and stop as each key's arrays begin and end. Otherwise, a line will be drawn from the last two points to the first two points of each array.

Any help would be greatly appreciated :)

Comment on Subroutine Subtrefuge Select or Download Code

Replies are listed 'Best First'.
Re: Subroutine Subtrefuge by jethro (Monsignor) on Jun 07, 2008 at 02:51 UTC
First of all the following doesn't make sense. sub is called with the same parameters every time. `foreach (@temp) { sub($x0, $y0, $x1, $y1, @temp) } }` [download] But lets see if I understand your problem. It seems you have an unnecessary loop there. I commented that out. Also I changed your inner loops slightly, they have to stop looping after they get to the last 4 values. Now all there is left to do is to take your best attempt and wrap the corrected code for the other hash around it, substituting $x2...$y3 with @temp. I put the inner loop into a sub, makes it easier to compare to your version `foreach my $key (keys %other_hash) { # foreach (@{$other_hash{$key}} # { for (my $i=0; $i<=@{$points_by_name{$key}}-4; $i+=2) { innerloop( @{$other_hash{$key}}[$i..$i+3] ); } # } }` [download] and `sub innerloop { my ($x2,$y2,$x3,$y3)= @_; foreach my $key (keys %points_by_name) { # foreach (@{$points_by_name{$key}} # { for (my $i=0; $i<=@{$points_by_name{$key}}-4; $i+=2) { sub(@{$points_by_name{$key}}[$i..$i+3], $x2, $y2, $x3, + $y3) } # } } }` [download] Note I didn't test this. Might still be some bug in it. About your 'keeping track' problem: You have $key, you have $i, what else do you need to know about the line you are evaluating? Pass them into the sub if the sub needs to know	[reply] [d/l] [select]
Re: Subroutine Subtrefuge by pc88mxer (Vicar) on Jun 07, 2008 at 06:22 UTC
Let me see if I can grok your problem. 1. The data in the `<points>...</points>` element is a list of points in 3-space. You are only interested in the first two coordinates, so you are treating them as points in 2-space (or ordered pairs). These coordinates represent the vertices of a polygon (inferred by the name of your variable.) 2. Each `<tag>...</tag>` element specifies two polygons (or perhaps even more than two), and they are given names specified by the `<name>...</name>` element. 3. Given two polygons, p1 and p2, you want to call a function, f(e1, e2), on all pairs of edges where e1 is an edge of p1 and e2 is an edge of p2. An edge of a polygon is defined by two adjacent vertices of the polygon. Is this essentially what you are trying to do?	[reply] [d/l] [select]
Re^2: Subroutine Subtrefuge by AF_One (Novice) on Jun 08, 2008 at 03:40 UTC
pc88mxer, You've got it. <tag> would normally contain many polygons. Every edge is compared to all others. Cartographers and surveyors use this method of analysis. It's native to a methodology that is universally employed by a Geospatial Information System (GIS). The file being sucked-in is a Google Earth KML (Keyhole Markup Language). GE is known in the GIS industry as a "geo-browser" because it does not offer the above proximity analysis, among other things. Come to think of it...I should have asked if it were possible to have the sub return true on the first occurrence of intersection within each key's values. Thanks for the reply, This newbie appreciates it!	[reply]
Re^3: Subroutine Subtrefuge by jethro (Monsignor) on Jun 08, 2008 at 13:24 UTC
I think it would be easier to have the sub return true on every occurrence of intersection and let the caller sort that out, because there the necessary information is at hand `foreach my $key (keys %points_by_name) { my $intersectionfound=0; for (my $i=0; $i<=@{$points_by_name{$key}}-4; $i+=2) { if (sub(@{$points_by_name{$key}}[$i..$i+3],$x2, $y2, $x3, $y3) and not $intersectionfound) { # found the first intersection of $key } } }` [download] If you really need the info in the sub, just pass $intersectionfound to the sub, as long as it is 0 (false) an intersection is the first intersection of a key (provided that the sub really returns true on found intersections and false otherwise). PS: I dropped your "excessive" indentation, so that the code fits into the editor window of the website ;-).	[reply] [d/l]