Hi Ferddle,

First of all, I think that the question is nice but there's something missing: some code. People will help you kindly with any perl-related question there, but they will not do the homework for you, of course! ;).

Just try to update your question and put your code as clean as possible. Perhaps people will be able to help you (it looks more like an algorithm problem). Just for some help, check which kind of iterative structure fits you more.

Looking by google you will find things like this: algorithm polygon -> Determining Whether A Point Is Inside A Complex Polygon

Hope it helps!
Sandboxed

Where's the problem? You wrote already condition, now write

for $pid (0..$num_of_points-1)
{
  for $polyid (0..$num_of_polygons-1)
  {
    'do something' if <your condition>
  }
}
[download]

Maybe there is a problem with speed? Or really great number of data? Some sorting would help here? Please write more info if you need more help.

If you have large numbers of point to look up and/or large numbers of polygons to match against, then you may find Re: Speeding up ... (O(N) determination of point in polygon regardless of complexity) of interest. It demonstrates a method of O(1) lookup (per point) regardless of how many polygons you are matching against. Well, up to 4 billion polygons.

That is, to lookup any 2D point and determine which of upto 2**32 polyons it is in, takes one memory read.

In that case it was finding the zipcode for a grid reference anywhere in the US. Which doesn't sound too dissimilar to the sketchy details you've given. It's quite simple to program and very fast.

You speak of points and polygons but give 3d sample data and a 2d illustration. You mention GoogleEarth files which implies geographic data which implies spherical coordinates. I'm confused! What is it that you are really dealing with? If it is spherical data then the math is a pile more "fun" than if you are really dealing with 2d data, or even with 3d data.

No, this is not 3d sample. Look at names of structures:

@pnt_x_values = (-12, 0, 23)
@pnt_y_values = (-83, 34, -76)
[download]

In the first table x coordinates of points are stored, in the second - y coords. And for polygons 1st table stores x min coordinates, 2nd table stores x max coords, and so on.

Yes, it is funny and (in some cases) unconvenient way of storing 2d data...

Doh!

The following code may be of interest:

use strict;
use warnings;

my @pnt_x_values = (-12, 0, 23);
my @pnt_y_values = (-83, 34, -76);

my @poly_x_min = (-13, 45, 22);
my @poly_x_max = (-11, 49, 24);
my @poly_y_min = (-82, 33, -2);
my @poly_y_max = (-84, 35, -6);

for my $polyI (0 .. $#poly_x_min) {
    my $x1 = $poly_x_min[$polyI];
    my $x2 = $poly_x_max[$polyI];
    my $y1 = $poly_y_min[$polyI];
    my $y2 = $poly_y_max[$polyI];
    my @poly = map {{x => $_->[0], y =>$_->[1]}}
        ([$x1, $y1], [$x2, $y1], [$x2, $y2], [$x1, $y2]);

    for my $pi (0 .. $#pnt_x_values) {
        my %point = (x => $pnt_x_values[$pi], y => $pnt_y_values[$pi])
+;

        next unless PointInPoly (\%point, \@poly);
        print 'Point ' . ($pi + 1) . ' inside poly ' . (1 + $polyI) . 
+"\n";
    }
}


sub PointInPoly {
    my ($point, $poly) = @_;
    my $wCount = 0;

    for my $i (0 .. $#$poly - 1, -1) {
        # edge from$poly->[$i] to$poly->[$i + 1]
        if ($poly->[$i]{y} <= $point->{y}) {
            # start y <= $P->{y}
            if ($poly->[$i + 1]->{y} > $point->{y}) {
                # an upward crossing
                if (isLeft ($poly->[$i], $poly->[$i + 1], $point) > 0)
+ {
                    # $P left of edge
                    ++$wCount;    # have a valid up intersect
                }
            }
        } else {
            # start y > $P->{y} (no test needed)
            if ($poly->[$i + 1]->{y} <= $point->{y}) {
                # a downward crossing
                if (isLeft ($poly->[$i], $poly->[$i + 1], $point) < 0)
+ {
                    # $P right of edge
                    --$wCount;    # have a valid down intersect
                }
            }
        }
    }
    return $wCount;
}


sub isLeft {
    my ($P0, $P1, $P2) = @_;

    return ($P1->{x} - $P0->{x}) * ($P2->{y} - $P0->{y})
            - ($P2->{x} - $P0->{x}) * ($P1->{y} - $P0->{y});
}
[download]

Prints:

Point 1 inside poly 1
[download]

---

Perl is environmentally friendly - it saves trees