Measuring time

Discuss Programming
worker201
guru
guru
Posts: 668
Joined: Sun Jun 13, 2004 6:38 pm
Location: Hawaii

Measuring time

Post by worker201 » Tue Aug 01, 2006 4:01 pm

Void (and others), I need a little help with writing a program. Here's what it ought to do:

Be able to read a data file. The file is a set of coordinates defining a line segment or polygon, with each segment separated by a >. The number of segments should not be limited, nor should segment length. Here's a sample input file:

Code: Select all

>
-95.168785	29.082421
-95.169151	29.082421
-95.169298	29.082421
-95.169151	29.082274
-95.168711	29.082274
-95.168785	29.082421
>
-95.167465	29.082568
-95.167831	29.082421
-95.167831	29.082201
-95.167611	29.082128
-95.167245	29.082128
-95.167098	29.082201
-95.167465	29.082568
>
-95.171792	29.082714
-95.172085	29.082861
-95.172012	29.082494
-95.171645	29.082054
-95.171425	29.082201
-95.171792	29.082714
>
So, what needs to be done is to read in the first two points and calculate the distance between them. Then read in the next point and calculate distance between third and fourth points, etc. At the end of the segment, it should print/store the total length of that segment. After the whole file is processed, all the subtotals should be added together and printed.

As far as computing the geographic distance goes, I think I can work up a function that does that. I have samples in C++ and PHP to follow. So that part isn't the big deal. Where I need help is in reading the file and stepping through the points.

So, what language is this project suited to? I need trig functions, so it has to be a somewhat powerful language - sed and JavaScript probably won't cut it! And it should be somewhat efficient - I have 25,000 points to process. Can perl do this? Are C or C++ overkill? Would a bash script be able to handle it? I just don't know. (I can write simple loops in bash, awk, C, perl, C++, and JavaScript)

And if anyone has any ideas on how to set up the input processing, that would be great. I'm not an experienced programmer, and wrapping my head around the concept isn't going very well. Stepping over the > separators is quite difficult, especially since they mark the end and beginning of a line segment.

ZiaTioN
administrator
administrator
Posts: 460
Joined: Tue Apr 08, 2003 3:28 pm
Contact:

Post by ZiaTioN » Tue Aug 01, 2006 4:44 pm

I would recommend perl or python.

shell scripting would be too limited and I think C or C++ would be overkill for this basic functionality.. Not to mention the large amount of code this would take in a low level language like C compared to a higher level language like perl or python.

User avatar
Void Main
Site Admin
Site Admin
Posts: 5716
Joined: Wed Jan 08, 2003 5:24 am
Location: Tuxville, USA
Contact:

Post by Void Main » Tue Aug 01, 2006 4:51 pm

I would do it in FORTRAN. :) Actually I used to do a LOT of that exact type of stuff using FORTRAN on mainframes about 15 years ago. But it would be extremely simple to do in Perl. This is not part of a school assignment is it? I don't want to do the work for you if it is. If it's not I would be more than happy to whip of a few lines of code that would do exactly what you need (it shouldn't take much more than a few lines in Perl).

ZiaTioN
administrator
administrator
Posts: 460
Joined: Tue Apr 08, 2003 3:28 pm
Contact:

Post by ZiaTioN » Tue Aug 01, 2006 5:11 pm

Ooh good call, this does sound like a homeowrk assignment. I wrote something up in perl but will not post it until I hear back about the homework assignment.

worker201
guru
guru
Posts: 668
Joined: Sun Jun 13, 2004 6:38 pm
Location: Hawaii

Post by worker201 » Tue Aug 01, 2006 5:16 pm

Not for school, for work. I have to measure the coastline. I accepted the project assuming that it could be done, even though I didn't have the skills to write the program. It's a 4 week project, and I gave myself 2 weeks for the program. But so far, I have been woefully unable to transfer the human instructions into something the computer can deal with efficiently.

Perl is fine. Unfortunately, my Perl understanding is kinda limited to the first 2 chapters of the Llama book. Actually, if this is so simple, maybe you could write the main structure in pseudo-code - without actual syntax, just something that sorta describes the process. Something that tells me how the program is going to look at the end, but make me write the actual code. It's the input-organizing algorithm that's giving me the headache, after all. --If that wouldn't be too much trouble. :wink:

User avatar
Void Main
Site Admin
Site Admin
Posts: 5716
Joined: Wed Jan 08, 2003 5:24 am
Location: Tuxville, USA
Contact:

Post by Void Main » Tue Aug 01, 2006 5:37 pm

Sounds like ZiaTioN already has some code ready for you. I guess I can go change the fork seals on my dirt bike then. :)

ZiaTioN
administrator
administrator
Posts: 460
Joined: Tue Apr 08, 2003 3:28 pm
Contact:

Post by ZiaTioN » Tue Aug 01, 2006 6:02 pm

well what I will do is show you the actual code and then describe what it is doing. I think this will be a better learning experience than giving you psuedo code.

Code: Select all

#!/usr/bin/perl -w

use strict;

$/ = '>';
my $total = 0;
while(<DATA>) {
   chomp();
   next unless($_);
   my $subtotal;
   for(split(/\n/)) {
      next unless($_);
      my ($first, $second) = split(/\s+/);
      $subtotal += ($second - $first);
   }
   print "Subtotal: ".sprintf("%.2f",$subtotal),"\n";
   $total += $subtotal;
}
print "Total: ".sprintf("%.2f", $total),"\n";

__DATA__
>
-95.168785   29.082421
-95.169151   29.082421
-95.169298   29.082421
-95.169151   29.082274
-95.168711   29.082274
-95.168785   29.082421
>
-95.167465   29.082568
-95.167831   29.082421
-95.167831   29.082201
-95.167611   29.082128
-95.167245   29.082128
-95.167098   29.082201
-95.167465   29.082568
>
-95.171792   29.082714
-95.172085   29.082861
-95.172012   29.082494
-95.171645   29.082054
-95.171425   29.082201
-95.171792   29.082714
>
Ok first off:

Code: Select all

#!/usr/bin/perl -w
is called the shebang line and is what tells the system where to look for the interpretor to interpret the following code. It is pointed at the perl binary and is invoking warnings (that is the -w part).

Code: Select all

use strict;
Is a module that is included with the perl standard library and forces strict references and lexical localization amongst other things (like quoted strings and what not).

Now the fun stuff...
$/ and $\ are the input and output record seperators. By default on most systems they are set equal to newlines "\n". This is what tells perl what is defined as a "record". Basically, by default perl reads records as a single line of text (because \n is the default record seperator).

Here I change that to be the '>' character so that in my while() loop, each iteration is processing what I define as a record and not what perl defaults to a record. it allows the app to grab all of the lines of data between the '>' characters as a single record for processing.

Code: Select all

   chomp();
   next unless($_);
   my $subtotal;
The above code does the initial processing on the record. It first chomp()'s the data. What chomp() does is removes the record seperator (newline by default or whatever you change it to) off the end of the record. Then it checks to see if $_ is NULL or not and if it is it skips to the next iteration oft he while loop. if it is not NULL then it continues to process it. The "my $subtotal" is called a variable instantiation and is required when using strict.

Code: Select all

   for(split(/\n/)) {
Here I do two things. I setup a for loop and feed it the output of the split() function which splits each record of the while loop into seperate lines for further processing. I probably should have used a foreach() loop here for better readability but a for loop used in this fashion acts in the same manner. A standard for loop usually has it's instantiation, conditional statement and increment all in the decleration of the loop (for(my $i=0; $i < 10; $i++){}). This usage does not.

Code: Select all

      next unless($_);
      my ($first, $second) = split(/\s+/);
      $subtotal += ($second - $first);
This is the guts of the for loop and what it does is check again to see if this local $_ is NULL ($_ is lexically scoped by default) and if it is not NULL it continues and if it is, then it skips to the next iteration of the for loop (not the while loop).

Then we split the contents of each line into two variables, $first and $second. Then we add the value of $subtotal to the difference between the two values.

Code: Select all

   print "Subtotal: ".sprintf("%.2f",$subtotal),"\n";
   $total += $subtotal;
Here we print each records calculated subtotal according to what you said you wanted this app to do and then we add each records subtotal to the overall total which we print out after each record has been processed through the while loop.

My usage of sprintf() was only to pretty the integers up a bit and only show 2 places past the decimal. if you wanted these rounded to whole numers there are ways of doing that too, just let me know.

I hope I am taking the difference of the right two numbers. I was not quiet sure what you meant when you said you wanted it to read in the first and second numbersand then the third and fourth and so on..

Oh yeah and everything after __DATA__ is just the input data I used to parse. I created a filehandle in the actual script for easy processing but you can feed your filehandle to this routine however you get it (open() call etc..)

User avatar
Void Main
Site Admin
Site Admin
Posts: 5716
Joined: Wed Jan 08, 2003 5:24 am
Location: Tuxville, USA
Contact:

Post by Void Main » Tue Aug 01, 2006 6:08 pm

I think you have the reading of the data worked out OK but I believe what worker is actually trying to calculate is distance. Are those not lat/lon points? So, you have to calculate the distance between each point and then add those distances together. The flow of the script is correct, just have to add a little trig:

http://www2.nau.edu/~cvm/latlon_formula.html
http://www2.nau.edu/~cvm/latlongdist.html

To be honest, I believe there are Perl modules out there that have lat/lon functions already built but the above links have all that is needed.

ZiaTioN
administrator
administrator
Posts: 460
Joined: Tue Apr 08, 2003 3:28 pm
Contact:

Post by ZiaTioN » Tue Aug 01, 2006 7:34 pm

yeah that is what I did not understand, what numbers he was looking for distance in between. I was not even sure if those first integers are negative or not, LOL...

Anyway, yes the flow of the program is correct, just substitute any math that is needed to make the correct calculations.

User avatar
Void Main
Site Admin
Site Admin
Posts: 5716
Joined: Wed Jan 08, 2003 5:24 am
Location: Tuxville, USA
Contact:

Post by Void Main » Tue Aug 01, 2006 7:46 pm

Each line is a lon/lat coordinate pair so you have to figure the distance between each line and add those distances up. That means the flow isn't quite what it needs to be. You have to read the first 2 lines before a calculation can be made.

e.g. pseudo code:
$sub = dist(line1,line2)
$sub += dist(line2,line3)
$sub += dist(line3,line4)
print $sub
$total += $sub;

$sub = dist(line6,line7)
$sub += dist(line7,line8)
$sub += dist(line8,line9)
print $sub
$total += $sub
print $total

This assumes each section (separated by '>') are not connected (don't use any line from one section in another section for figuring distance). In this example there would be a '>' on line 5.

ZiaTioN
administrator
administrator
Posts: 460
Joined: Tue Apr 08, 2003 3:28 pm
Contact:

Post by ZiaTioN » Tue Aug 01, 2006 10:52 pm

Try this:

Code: Select all

#!/usr/bin/perl -w

use strict;

$/ = '>';
my $total = 0;
while(<DATA>) {
   chomp();
   next unless($_);
   my $subtotal = 0;
   my @list = split(/\n/);
   for(0..$#list) {
      next unless($list[$_]);
      if ($list[$_+1]) {
         my ($first, $second)   = split(/\s+/, $list[$_]);
         my ($nfirst, $nsecond) = split(/\s+/, $list[$_+1]);
         $subtotal += calculate($first, $second, $nfirst, $nsecond);
      }
   }
   print "Subtotal: ".sprintf("%.4f",$subtotal),"\n";
   $total += $subtotal;
}
print "Total: ".sprintf("%.4f", $total),"\n";

sub calculate {
   my ($a1, $b1, $a2, $b2) = @_;
   my $pi = atan2(1, 1) * 4;
   $a1 *= ($pi/180);
   $b1 *= ($pi/180);
   $a2 *= ($pi/180);
   $b2 *= ($pi/180);

   # Value for $r = 3963.1 statute miles -- 3443.9 nautical miles -- 6378 km
   my $r = 3963.1; # statute miles, for feet multiply this by 5,280
   my $x = (cos($a1)*cos($b1)*cos($a2)*cos($b2))+
           (cos($a1)*sin($b1)*cos($a2)*sin($b2))+
           (sin($a1)*sin($a2));
   return (atan2(sqrt(1 - $x**2), $x) * $r);
}
I think the math is good but check it...

User avatar
Void Main
Site Admin
Site Admin
Posts: 5716
Joined: Wed Jan 08, 2003 5:24 am
Location: Tuxville, USA
Contact:

Post by Void Main » Tue Aug 01, 2006 11:28 pm

Here's my version that I think works:

$ mapmiles.pl coords.dat

Code: Select all

#!/usr/bin/perl -w

# Program: mapmiles.pl
# Syntax: mapmiles.pl coordfile.dat

use strict;
use Math::Trig qw(great_circle_distance deg2rad);

sub NESW { deg2rad($_[0]), deg2rad(90 - $_[1]) }

my $dist = 0;
my $total = 0;
my $subtotal = 0;
my $lat = 0;
my $lon = 0;
my @P1 = 0;
my @P2 = 0;

open(FILE,"<$ARGV[0]");

while(<FILE>) {

   chomp();

   if (/\>/) {

      printf("Subtotal: %.4f miles\n",$subtotal) if $subtotal;
      $total += $subtotal;
      @P1 = @P2 = $subtotal = 0;

   } else {

      @P2 = @P1;
      ($lon, $lat) = split(/\s+/);
      @P1 = NESW($lon,$lat);

      if ($P2[0]) {
         $dist = great_circle_distance(@P1,@P2,3963.1);
         $subtotal += $dist;
         print "lat: $lat, lon: $lon, dist: $dist\n";
      }

   }

}

close(FILE);

$total += $subtotal;
printf("Total: %.4f miles\n", $total);
Looks like we come up with different answers when running his data so either one or both of us are wrong. Looks like we're both using statute miles so that's not it.

EDIT: I just ran my program on some of my GPS track data dumps and mine seems to be right on the money.

JoeDude
administrator
administrator
Posts: 355
Joined: Sun Feb 08, 2004 1:41 pm
Location: Sutton Coldfield, UK
Contact:

Post by JoeDude » Wed Aug 02, 2006 1:28 am

I finally figured it out...

VOID IS BATMAN!!!

Who else has all those kewl gadgets and stuff!!

ZiaTioN
administrator
administrator
Posts: 460
Joined: Tue Apr 08, 2003 3:28 pm
Contact:

Post by ZiaTioN » Wed Aug 02, 2006 7:08 am

EDIT: I just ran my program on some of my GPS track data dumps and mine seems to be right on the money.
Yeah, the math I was not sure about. How far off was it? I will have to look at the source for that module and see what numbers they used.

User avatar
Void Main
Site Admin
Site Admin
Posts: 5716
Joined: Wed Jan 08, 2003 5:24 am
Location: Tuxville, USA
Contact:

Post by Void Main » Wed Aug 02, 2006 8:11 am

Your calculations were slightly lower, around 9/10s or so of what I was getting. It almost looked like the difference in statute and nautical miles but we both should be working with statute so that couldn't be it. I didn't look closely at it as I was juggling a couple of different things at the time. I set up some weather graphs by scraping accuweather.com:

http://voidmain.is-a-geek.net/cacti/gra ... ta_query:0

Post Reply