Compute distances between cities using c++

[jmvr_danga_14]

Hello! im new here and i have a problem regarding programming. We are required to compute for the distance of a certain city to another city...for example whats the distance of new york to los angeles..then the program will compute its distance... the output of the said program should be like this..

From: /name of city/
To: /name of city/
Total distance between cities: /value/

or

1st city:
2nd city:
distance between 2 cites:

it can be any method as much as possible a simple one that even a noob like me can understand..it could not necessarily be an array or struct as long as it is a c++ program...:)
i really need help in this..i would appreciate any help from you guys... you can message me, reply to this post or email me at <email snipped per forum rules> . thank you very much!

[sarehu]

You'll need a database of cities and their latitude-longitude coordinates, or access to an online database, and you'll need an algorithm for finding the distance between two points on a sphere, given their latitude/longitude coordinates. The latter is done by the haversine formula.

[rajatC]

You'll need a database of cities and their latitude-longitude coordinates, or access to an online database, and you'll need an algorithm for finding the distance between two points on a sphere, given their latitude/longitude coordinates. The latter is done by the haversine formula.

exactly...
this is what i was going to post...

[VernonDozier]

Does he really need to have a database? You mean like setting up an SQL database or something, then inserting and querying from the C++ program using SQL commands? I guess we need more details, jmvr_danga_14. Is that what your boss/teacher is looking for? That seems like a larger undertaking than reading the data in from a file into an array of structs, like the OP from the earlier thread needed.

Or am I misinterpreting your references to databases?

[jmvr_danga_14]

where could i find that kind of database and what kind of algorithm should i get? what's a haversine formula and what i basically does? sorry if im such a noob...

Also what's an SQL database? and what do you mean by further querying and inserting? As far as i remember thats what our professor is asking about... he also required us to show a map of a particular place then if your done inputting the names of the 2 cities you want to know the distance, the program will draw a line pointing out where it will go...for example if i input LA and i want to go to Miami..the program will compute that distance then it will show that it will pass thru arizona, texas, georgia then to miama...got it? tnx for the help...

[VernonDozier]

The Haversine Formula is a formula to measure the distance between two points on the globe. SQL is a language used to manage relational databases. Googling them gets you some pretty good descriptions. What level course is this? Have you taken a database course yet? You mentioned you weren't too familiar with arrays and structs, which are normally covered before databases in most curriculums. For sure you need to find out if your instructor is expecting you to design a relational database before you can move on too far. Also, drawing lines on a map from L.A. to Miami? Figuring out what states you are going through? This sounds like a pretty involved project and a far bigger project than the person who started the last thread. Is this a console application or a graphical one? I think I need more information.

[ithelp]

A simple file with latitute and longitude information will be sufficient.

[jmvr_danga_14]

we already took basic c language programming as well as basic c++ but i really suck at programming and doesnt know anything about it and now i want to learn how it actually works...anyway, yup its a console application...one of my classmates used an MFC application, for him to be able to represent the graphical part, meaning the map with a pathway represented by a line...about the SQL i really dont have any idea about it, compared it with structs and arrays at least i have heard and encountered these things but dont understand much...so where can i look for an online database that will give me latitudes and longitudes of certain places? so basically, what i should i do is make a text file out of this, put it in the program then use the haversine formula to compute the distance is that it? can anyone put a sample code for this or at least to help me start with it...thanks...

[VernonDozier]

Don't do the database/SQL if it is not required, and it doesn't sound like it is. Either do a text file or have the user type in two or more cities. If you you want to avoid arrays, just have the user type in two cities with their latitudes and longitudes. I suppose you don't have to use a struct, but it will make things look nicer. For the lats and longs, here's a decent link:

http://www.bcca.org/misc/qiblih/latlong_us.html

Try to think up a plan of attack, describe the way you want to do it and maybe post a rough skeleton of code here, and we can try to help you from there.

[jmvr_danga_14]

a ok ok..so ill just use the basics of c++ programming if im not going to use arrays or structs? can i do a switch or a loop here? how about a class? so if ill let the user put the lat and long, more or less i should provide them with one right? depending on what city they would..however, our professor demonstrated an output already, he only typed the name of the 2 cities to be computed then the output shows a track, wherein it will show what cities it will pass through to get you to the location you inputed then the total travel distance...

[VernonDozier]

You can do all of those things; there are numerous ways to do this. Here is what I believe would be the easiest. Create a struct called "city" that contains the name of the city, its latitude, and its longitude. How you represent latitude and longitude is up to you. They could be represented with doubles, or you could have a struct called "latitude" and a struct called "longitude" and design it in the Degrees/Minutes/Seconds format, along with a North/South or East/West component. Either way is fine, but pick one and stick with it. The link I gave was a Degrees/Minutes one, I think, so if you go the "double" route in your "city" struct, you would need to convert that data to doubles.

Define two variables of type city called "city1" and "city2". Prompt the user for the names and latitudes/longitudes of these cities and store them in city1 and city2. Create a function that takes two parameters of type "city" and returns the distance between them, using the haversine formula. Then display the results.

I would do this and get it working first before doing anything with arrays, drawing lines, figuring out what states you go through, etc. You can change it to read through a file later, if desired, as well as the other stuff. You can certainly use switch statements, loops, or classes, and you may end up with those, but I don't think you need to with this particular implementation at this point.

Also, check out the other poster's original thread. Some people had some ideas over there and I think someone offered a design of a struct in that thread. Can't remember for sure.

[Sandman13]

The haversine formula is an equation important in navigation, giving great-circle distances between two points on a sphere from their longitudes and latitudes. It is a special case of a more general formula in spherical trigonometry............For two points on a sphere (of radius R) with latitudes φ1 and φ2, latitude separation Δφ = φ1 − φ2, and longitude separation Δλ, where angles are in radians, the distance d between the two points (along a great circle of the sphere; see spherical distance) is related to their locations by the formula:
(the haversine formula)

\operatorname{haversin}\left(\frac{d}{R}\right) = \operatorname{haversin}(\Delta\phi) + \cos(\phi_1) \cos(\phi_2) \ \operatorname{haversin}(\Delta\lambda) ........Let h denote haversin(d/R), given from above. One can then solve for d either by simply applying the inverse haversine (if available) or by using the arcsine (inverse sine) function:

d = R \, \operatorname{haversin}^{-1}(h) = 2 R \arcsin\left(\sqrt{h}\,\right)

[jmvr_danga_14]

a ok ok..now i got the idea already..yeah, i did check that post already..ill just do first what you suggest and then if i encountered an error ill just post it here and help me debug it..thanks a lot! i really appreciate all your help..

[zandiago]

I'm personally going to recommend the use of latitude and longitude as mentioned above...i did this a few weeks ago, so i'll guide you as you go along!

[jmvr_danga_14]

really? ok tnx...i already got the longitudes and latitudes of the places that i want to compute...and put it in a text file..so how am i going to start this?

[VernonDozier]

Well, I would start by writing the "city" struct, including the libraries you are going to use, setting up the function prototype for getting the distance between two cities, writing the function so that it just returns 0.0 or something (you can fill in the function calculations later), setting up two variables of type "city", calling that function, and displaying the results. The results will be inaccurate, of course, but it'll show us the program skeleton. I wouldn't read in the data from the user yet (or from a file), just put some comments in the program explaining where you plan on putting stuff. Then post the that code and we can all go from there. Basically just a light skeleton with comments, a function prototype with the function call, even though that function won't really do much, and a simple one line display of the "results". How's that sound?

[jmvr_danga_14]

ok ok...i guess i just need to do my own thing first..thanks a lot everybody! i appreciate all your help...il post my code later if im done with it..tnx...

[jmvr_danga_14]

i have another problem...! do you know about a star algorithm? our professor required us to put this kind of algorithm to our program..so does any one know what's this algorithm and how it works? also how will i incorporate this algorithm to our program..tnx...

[VernonDozier]

The A-Star algorithm is a way of getting from point A to point B in an efficient way, or in your case city A to city B. Wikipedia has some decent links/examples/implementations. You'd have a bunch of cities, with roads between them. The roads would be, I assume, straight lines (well, arcs since it is a globe and you're using the haversine formula). It seems to me that your teacher is assuming that not every pair of cities would have a road in between. Otherwise you would just go directly from city A to city B and there's no need from an algorithm. It's a graph theory algorithm. You have a bunch of nodes and a bunch of edges connecting the nodes, and each edge has a cost. You're trying to find a good, but not necessarily the best, path from node A to node B. I've never used A-Star, but I have heard it comes up a lot in games with obstacles. There are other graph theory algorithms to get from point A to point B, like Djikstra's Algorithm. I'm more familiar with that one. Again, I've never used A-Star, so I have no idea how hard it is to implement.

So to have any use for A-Star, it would seem to me that you not only have to enter in a bunch of cities, but somehow have a bunch of edges too. The "cost" of each edge could be the distance, so that would be calculated rather than entered. This can be as elaborate and involved as you want to by randomly generating edges, by putting in obstacles, etc., but do you really want to do that? Regardless, I still think you should tackle the easier problem first, get that working first flawlessly, then add in these other features. If you are going to try to implement an A-Star or Djikstra type solution, for sure work it out on paper first to get the math/graph theory down before trying to code it.

[WaltP]

i have another problem...! do you know about a star algorithm? our professor required us to put this kind of algorithm to our program..so does any one know what's this algorithm and how it works? also how will i incorporate this algorithm to our program..tnx...

If he requires it, he should describe it. So ask your professor. :icon_rolleyes:

[jmvr_danga_14]

he did not describe it to us..he just told us to use that kind of algorithm to our program. he did not even describe how it works or showed us an example of it...he just showed us how he's program works then that's it...

[WolfPack]

Didn't your professor or anybody else at least tell you about this awfully fun site called http://www.google.com/ where you can type A-Star Algorithm in that cute little white box and press search to get some really nice links with more than enough information?