processing gps data

[waleed.makarem]

Dear all ,

I am trying to develop code that will check for each location (latitude and longitude) for a nmea file ( contains over 200,000 point) to check if this file contains some points that was close to a certain location or not . How can we do this in such a way that will make the code fast . we have a nmean file with over 200,000 waypoints and have a list of locations with 140 location name and position (latitude and longitude and permitted distance) . I need to develop a code that will pass through all of the 200000 way points to list which waypoints where close to the listed locations by this distance (eg 10 meter).

I have the code but it seems to be very slow , taking 0.75 second for 2000 waypoints only .
it loops through all way points and for each , it calculates the distance to the set value adn if it is less than the set value , it records that the place is ok .

are there any ideas.

Thanks,

[Momerath]

Step 1: Create a list of all your points that are within 10 just comparing the x-coordinate.
Step 2: From those, create a list of all your points that are within 10 just comparing the y-coordinate.
Step 3: From those, create a list of all your points that are actually within 10 using the standard distance formula.

Test runs using 2 million locations takes over a second doing it the way you are, and less than 1 millisecond doing it my way. If you are near a second just doing 2000 waypoints, you are doing something odd :)

Post your code that does the distance check, and any relevant class information that might be needed to understand what you are doing, and we can hopefully optimize this for you.

[kvprajapati]

What I am saying that you need to more concentrate on your code. Use different programming techniques/tricks.

[waleed.makarem]

Dear All ,

Thanks so much for your support , I really appreciate it so much .

Regarding your comments , I suggest that there must be a smarter approach that the way I used. But I do not know how to get it .

my code is into this link :

http://www.4shared.com/file/Ksl1j9Lm/WindowsApplication9.html

I think it is better to download the files and check them because the class is long to somewhat.

The base concept is to parse the NMEA files to get the location data (longitude , latitude, time) and store them into a data table (eg RawDataTable).
Then , the "processtrip" function passes the location that we need to check (as LocationDataTable) , then this function will compare the generated RawDateTable line by line to check if this location is the same in each of the LocationDataTable .

I am sure that my code is not that proffessional as yours , so you kin feedback is highly evaluated .

Thank you in advance for you support.

in case you need to check the code here , here is the class

[waleed.makarem]

are there any feedback .

Thanks, all

[waleed.makarem]

I also appreciate if you describe the trick approach to make the code faster.
If you make a sample code to describe the idea , I appreciate this so much .

[nick.crane]

Firstly, the code is VB and this is the C# forum.
However, there are a couple of points that I can see where improvements can be made.
(Apart from changing to C#:D)

Ways to improve performance

1) Minimise the times you scan your data.

Currently you call your GetWords method twice for every line.
You could hold the words in an array and pass this in to the ParseGPRMC and ParseGPGSV instead of the original line. This will save the second call to GetWords.

2) Reduce the number of tests you do.

If you use the System.StringSplitOptions.RemoveEmptyEntries option when splitting the string you can test for the number of words to confirm you have all the data you need instead of testing each word for empty string.

This could reduce the number of test conditions you have in ParseGPRMC and ParseGPGSV. That depends on the format of any other data in your source file.

3) Remove any unnecessary duplication of work.

In ParseGPGSV you do Count * 4 many times.
You could use the Step function to do this for you.
E.g. Use For Count = 1 To 16 Step 4 then just use Count.

Also, personally I prefer to use String.Empty instead of "" as using "" generates a new string constant in your code (or at least it used to in earlier VB versions).
Not sure if this will have a speed impact (unlikely).

Also, try not to use the Form1.<property> global variable.
This is a VB only thing and is something that encourages bad non OOD code.
In your current app Form1 is used to write the process timing to the form title.
Do the timing in Form1 instead, outside the method call. That way you will not need to use Form1.

[waleed.makarem]

Dear Nic.crane ,

Thanks for your valuable feedback . I really appreciate it so much .

First Sorry for this code as vb.net not C# , however , I thought that both languages are the same and very close to each other . I even use both in the my program interchangeably. If you had a code in C# that will make the process faster , I can mange to use your smart c# code .

For the comments , You will see that first the class will parse the nmea file into a datatable . then the process function does the whole job for comparing different locations to the existing datatable. the problem i face (the slow process) is found at the second part which is the comparison part . So , regarding your comments , i guess the only solution I shall focus on (if you kindly agree with me) is string.empty issue .

I appreciate if you feedback the "processtrip" function which I pass to it a datatable containing all of the location data (name and coordinates) , then it compares it to the previously generated datatable (from parsing the nema file). I think this function takes much time that worth to work on . It takes 1.75 seconds for only 2000 NMEA points checking only 8 locations. I am sure that there should be a smarter code that can perform much better.

Another thing , I added the time to the form title just for display how long the code takes only , but in the real program , it will not be present.

By the way , the code in C# is below

public bool processtrip(ref DataTable locationlist)
{
	DateTime cu = DateTime.Now;



	bool bInLocation = false;
	double LocID;
	string LocName = "";
	DateTime LocVisitDateIn;
	int LocRowCount = 0;
	int LocRowCurPostoStart = 0;



	foreach ( rowRaw in dtTable.Rows) {


		// go directly to the last person who has the visit
		for (LocRowCount = LocRowCurPostoStart; LocRowCount <= locationlist.Rows.Count - 1; LocRowCount++) {
			if (Calc(rowRaw(latitRaw), rowRaw(longitRaw), locationlist.Rows(LocRowCount).Item(MasterLocLatit), locationlist.Rows(LocRowCount).Item(MasterLocLongit)) < locationlist.Rows(LocRowCount).Item(MasterLocDist)) {
				// first time to enter this location
				if (bInLocation == false) {
					LocRowCurPostoStart = LocRowCount;
					// store this as the person who has the viist

					LocID = locationlist.Rows(LocRowCount).Item(MasterLocID);
					LocName = locationlist.Rows(LocRowCount).Item(MasterLocName);
					LocVisitDateIn = rowRaw(Date_TimeRaw);
					bInLocation = true;
					break; // TODO: might not be correct. Was : Exit For
				//dtAnalysis.Rows.Add(LocID, LocName, LocVisitDateIn)
				// person has been at the same place before
				} else {
					break; // TODO: might not be correct. Was : Exit For
				}
			// outside area
			} else {
				if (bInLocation == true) {
					dtAnalysis.Rows.Add(LocID, LocName, LocVisitDateIn, ((System.DateTime)rowRaw(Date_TimeRaw)).Subtract(LocVisitDateIn).Seconds);
					bInLocation = false;
					LocRowCurPostoStart = 0;
					break; // TODO: might not be correct. Was : Exit For
				}

			}
		}


	}


	DateTime cn = DateTime.Now;
	TimeSpan j;
	j = cn.Subtract(cu);
	Form1.Text = (j.TotalMilliseconds);

}

public double Calc(double Lat1, double Long1, double Lat2, double Long2)
{
	//I found an article on codeproject.com by Gary Dryden, written in C#.
	//Remember to convert your position to Decimals first.
	//I converted it to VB.NET like so:
	double dDistance = double.MinValue;
	double dLat1InRad = Lat1 * (Math.PI / 180);
	double dLong1InRad = Long1 * (Math.PI / 180);
	double dLat2InRad = Lat2 * (Math.PI / 180);
	double dLong2InRad = Long2 * (Math.PI / 180);
	double dLongitude = dLong2InRad - dLong1InRad;
	double dLatitude = dLat2InRad - dLat1InRad;
	double a = Math.Pow(Math.Sin(dLatitude / 2), 2) + Math.Cos(dLat1InRad) * Math.Cos(dLat2InRad) * Math.Pow(Math.Sin(dLongitude / 2), 2);
	double c = 2 * Math.Atan2(Math.Sqrt(a), Math.Sqrt(1 - a));
	const double kEarthRadiusKms = 6376.5;
	dDistance = kEarthRadiusKms * c;
	return dDistance * 1000;

}

.

Thanks,

Waleed