AboutNick Expertise I can answer questions regarding C#, C , SQL, Visual Basic, .Net Framework 2.0, general programming technique, and general algorithm development. My current area of focus is C#.
Experience C /VB programmer since 10th grade. I used to love video game development (still do, just don't do it anymore). Have real world experience in 3 companies for a total of about 2 years non-academic experience.
Organizations Keneisys (a security software company)
Education/Credentials BS in Computer Science with minor in Entertainment Technology.
Awards and Honors "The Next Bill Gates" gag award :-). College: Summa Cum Laude.
Expert: Nick Date: 1/30/2008 Subject: how to calculate distance
Question QUESTION: Hi,
My client will input two values say A and B.
Here A and B represent cities. The source is A and the Destination is B
Now i have to find the shortest route for these two cities
One is using Dijktra's algorithm. But there one has two provide the other values too.
eg He starts from A and reaches to B, via A1,A2,A3, B1,B2,B3
we get all the distances from one place to all the above mentioned places and can find out the shortest path.
But my prblem is how shall i find what are the places that lies between these two cities A and B and other distances.
If I take the latitude/longitude of A and B, how shall I find the cities that lies between these two places and then calculate the distance.
Any suggestions pls
Hema
ANSWER: If I understand you correctly, you have two questions. The first is how to calculate the distance between two positions on the Earth's surface (given longitude & latitude) when travelling across the Earth's surface to get from one to the other. This webpage should answer that: http://mathforum.org/library/drmath/sets/select/dm_lat_long.html
The second question is how do you find cities that are "between" two other cities. To define "between", lets say you have two arcs across the Earth. Each of these arcs is the same size and shape. One end of each arc connects to City A. The other end of each arc connects to City B. These arcs can be whatever shape you like, although I would suggest you use circular arcs to make things easy on yourself. Now that you have these circular arcs, continue drawing each arc across the surface of the Earth so that each arc creates a circle. The arcs will be called Arc A and Arc B, which will correspond to the circles they create, Circle A and Circle B. Now, these circles can be seen as the equator of two spheres, Sphere A and Sphere B. Loop through each of the cities. Calculate each city's distance from the center of Sphere A and Sphere B. If a given city's distance from Sphere A is less than the radius of Sphere A and if the city's distance from Sphere B is less than the radius of Sphere B, then you know the city is in the region shared by both Sphere A and Sphere B. That region includes the area across the surface of Earth that is "between" City A and City B, so the given city is "close" to both cities. The only time you can avoid this calculation is when City A and City B are on exactly opposite sides of Earth, in which case all other cities are "between" them. If you want to make things really easy on yourself, make City A and City B points on opposite ends of a circle that travels across the surface of the Earth. That circle would then be the equator of a single sphere, which you could then use to see if cities are inside of it (and therefore, "close" to the other cities). I've never created a program like this before or done any of these calculations, so my explanation is entirely theoretical, which means you'll want to verify my explanation before using it. Hope that helps.
-Nick
---------- FOLLOW-UP ----------
QUESTION: Thanks Nick for your kind reply.
Now when u say draw an arc between the city and find all the cities which lies within that radius.
Don't u think one should have a database of finding out the cities lying within this radius
Or one can get the no. of cities without database
regards
Hema
Answer That depends. If you are trying to find the shortest distance between two cities, you need only the arc between the two of them and you have that distance. If, however, you have to travel on roads between the two cities, that may mean you will have to travel to some other cities before getting to your destination (ie, there are not straight roads between every two cities). If that is a case, it would possibly be useful to have a database of all cities on the planet (or at least the cities near your two locations). However, if you don't have road information, then having the cities will be of little use. Getting road data could make this problem quite a bit more challenging. Is this what you intend to do? If you let me know a little more about your problem, perhaps I could assist you further.
By the way, if all you need is the approximate number of cities between two other cities, there may be a way of doing that without a database. First, you get the total number of cities on the planet. Next, you calculate the area that is considered "between" the cities. Then, you find the ratio of the "between cities" area to the area of the entire planet's surface. You then use that ratio and the total number of cities on the planet to calculate how many cities on average would be in an area the size of the area that is "between" the cities.
As you can see, I am quite unsure of what problem you are exactly trying to solve, so more information would be of use.
