Better Logic?

[orbital]

Currently I am working on writing a Perl Mod that will calculate the elevation of a specific point. The reason why I am doing this is, I don't have the cash to throw down on a DGPS unit, all I can afford is just your consumer end GPS models. The problem with this is even though Selective Avaliablity was removed by Clinton, my altitude reading are not very accurate. This is due largely from the fact that it takes at least 4 known points to calculate your altitude, being in tree cover can break the signal for just a split second, causing errors because of the 3 sec latency to the sat. Also, moisture in the tops of trees can have a big impact on the results as well. I would like a more percise reading because I would like to start creating elevation profiles of my hikes (Planning on climbing ~20 fourteeners in CO this summer).

My plan is to take the SDTS data (read Coordinate for more info.) from the USGS and calculate each specific waypoint of my GPS data, and find which 4 known coordinates are closest to my current point. Once I have these points I will then be able to get a pretty go estimate of what my specific altitude is.

This Mod is going to tie into another Mod that I am currently working on called Convert::SDTS which dynamically find the known quadrant the data resides in, by looking through the USGS data tables, I am also using Coordinate to figure out which USGS file I exactly need to grab.

My question is there a better way to write the following snippet of code?

@nw=qw(0 30);   #North West corner
@ne=qw(30 30);  #North East corner
@se=qw(30 0);   #South East corner
@sw=qw(0 0);    #South West corner

@find=qw(10 5); #Point I am trying to find

# my current logic to establish if my point
# does indeed exist inside my four defined
# points.

    if ((($find[0]<($nw[0]<=$sw[0]?$nw[0]:$sw[0])) or #inside of west?
        ($find[0]>($ne[0]>=$se[0]?$ne[0]:$se[0])))or  #inside of east?
        (($find[1]<($sw[1]<=$se[1]?$sw[1]:$se[1])) or #inside of south
+?
        ($find[1]>($ne[1]>=$nw[1]?$ne[1]:$nw[1])))) { #inside of north
+?
       die "data is outside of the quadrant\n";
      }

This just seems very clumbsy, and I am sure I am missing something easy to clean this up a bit. Please help me out all wise ones.

[I0]

#assuming nw,ne,se,sw are convex and clockwise
sub c{
  my($x0,$y0,$x1,$y1,$x2,$y2) = @_;
  $x0 -= $x2;
  $x1 -= $x2;
  $y0 -= $y2;
  $y1 -= $y2;
  return $x1*$y0 > $x0*$y1;
}


unless( c(@nw,@ne,@find)
     && c(@ne,@se,@find)
     && c(@se,@sw,@find)
     && c(@sw,@nw,@find)
){
   die "data is outside of the quadrant\n";
}

[thabenksta]

This is a bit shorter. It requires you change your cooridnate system though.

### x, y, width, height ###
@box = qw(0, 0, 30, 30);

@find = qw(10, 5);

if (($find[0] > $box[0] && $find[0] < $box[0] + $box[2]) && ($find[1] 
+> $box[1] && $find[1] < $box[1] + $box[3])) {
    print "It's in the box!";
}

my $name = 'Ben Kittrell'; $name=~s/^(.+)\s(.).+$/\L$1$2/g; my $nick = 'tha' . $name . 'sta';

[orbital]

No I can't, because the quadrant doesn't neccessarily have to be or will be for that matter a perfect square. maybe I should have used different data with my example, I need to support this type as well:

@nw=qw(5,35);
@ne=qw(30,42);
@se=qw(28,3);
@sw=qw(1,2);

[merlyn]

So would something along the line between nw and sw be in or out? What if it's just a bit west of the line but not west of both nw/sw? What if it's a bit east, but still west of either sw or nw?

In other words, are you now doing real math to see if it's inside? Because your last example wouldn't work with this dataset either. {grin}

-- Randal L. Schwartz, Perl hacker

[gryng]

my @slope = (($ne[1]-$nw[1])/($ne[0]-$nw[0]),
             ($se[1]-$sw[1])/($se[0]-$sw[0]),
             ($se[0]-$ne[0])/($se[1]-$ne[1]),
             ($sw[0]-$nw[0])/($sw[1]-$nw[1]));
my @start = ($ne[1]-$ne[0]*$slope[0],
             $se[1]-$se[0]*$slope[1],
             $nw[0]-$nw[1]*$slope[2],
             $ne[0]-$ne[1]*$slope[3]);
my $in_quad = $find[0]*$slope[0]+$start[0]>=$find[1]
          and $find[0]*$slope[1]+$start[1]<=$find[1]
          and $find[1]*$slope[2]+$start[2]>=$find[0]
          and $find[1]*$slope[3]+$start[3]<=$find[0];

I've only checked this in my head -- hope it helps. It's easy to bomb this for slopes that divide by zero, but you can easily check for that. You can also put that last line in a loop if you would like, but I think this is cleaner.

Anyway, back to work,
Gryn

Update: Just incase you're wondering, you should be able to avoid the divided by zero's by multiply'ing each subexpression by the appropriate divided term. That is, in case my current code is actually correct, change the first condition to:
$find[0]*$slopetop[0]+$start[0]>=$find[1]*$slopebot[0] And the def of $start[0] changes to:
$ne[1]*$slopebot[0]-$ne[0]*$slopetop[0]

(@slopetop and @slopebot are now the top and bottom parts of @slope of course).

Ok, honest... back to work :)

[orbital]

Damn, your right!

What I need to do is calculate the slope of the line first then establish whether or not the data is on the correct side of the slope.

Thanks for pointing out my huge logical flaw... Brain Fart of the week :)

[merlyn]

There are some Mighty Quick Algorithms for this. I think I remember seeing one in the Algorithms In Perl book. "Don't divide" is an imporant part of that.

-- Randal L. Schwartz, Perl hacker

[Albannach]

As it happens, the sample chapter of Mastering Algorithms with Perl is all about geometry, and it includes a discussion of the standard ray method for the point-in-polygon problem.

--
I'd like to be able to assign to an luser

[merlyn]

Can you guarantee that the two "north" components are the same? I don't see why it wouldn't, but that would cut the number of comparisons by far. Maybe just make that a limitation of your routine, and die if the assertion fails.

-- Randal L. Schwartz, Perl hacker