ICS 45C Fall 2016
Project #1: Stay (Faraway, So Close!)

Due date and time: Monday, October 17, 11:59pm


Background

Like many things that have been automated in recent decades, most of us no longer use maps printed on paper when we want to get from one place to another. Instead, maps exist online in a searchable form, and GPS systems can help us to track our physical position as we move around. Software then can automatically tell us the shortest route between two locations, track our position along that route, and indicate how we should proceed along the way. Air travel is similarly automated, though, of course, the restriction that one should drive only on existing roads is lifted; aircraft can follow something more akin to a "straight-line" route from one place to another, except to the extent that they are required to follow certain regulations, such as staying out of airspace in which they're not permitted (e.g., directly over the White House or crossing an international border without permission) and maintaining a safe distance from one another.

At the core of any kind of automation like this lies the ability to determine one's current position on the surface of the Earth. There has long existed a way to describe such a position, using latitude and longitude. For example, if we wanted to calculate the distance along a direct route from Los Angeles International Airport and Kahului Airport in Hawaii, we would need to know two things: (1) the latitude and longitude of each of these airports, and (2) a formula for calculating a distance given those latitudes and longitudes.

This project asks you to explore this problem a bit, by implementing a program that calculates distances between locations on the surface of the Earth. Along the way, you'll gain some experience using the C++ Standard Library, discovering how to use some of its functions by reading their documentation, and writing C++ programs comprised of multiple source files. I fully expect that this is a program that everyone in this course is quite capable of writing, but the goal here is to embrace good techniques, so how you solve the problem will be at least as important as whether you solve it.


Getting started

Before you begin work on this project, there are a couple of chores you'll need to complete on your ICS 45C VM to get it set up to proceed.

Refreshing your ICS 45C VM environment

Even if you previously downloaded your ICS 45C VM, you may need to refresh its environment before proceeding with this project. Log into your VM and issue the shell command ics45c version to see what version of the ICS 45C environment you currently have stored on your VM. Note, in particular, the timestamp; if you see a version with a timestamp older than the one listed below, you'll want to refresh your environment by running the command ics45c refresh to download the latest one before you proceed with this project.

2016-10-02 15:47:23
Project #1 template added

If you're unable to get outgoing network access to work on the ICS 45C VM — something that afflicts a handful of students each quarter — then the ics45c refresh command won't work, but an alternative approach is to download the latest environment from the link below, then to upload the file on to your ICS 45C VM using SCP. (See the Project #0 write-up for more details on using SCP.) Once the file is on your VM, you can run the command ics45c refresh_local NAME_OF_ENVIRONMENT_FILE, replacing NAME_OF_ENVIRONMENT_FILE with the name of the file you uploaded.

Creating your project directory on your ICS 45C VM

A project template has been created specifically for this project. Though it is largely identical to the basic template, there are a few minor things that change from one project to another (such as the name of the file generated by the gather script). You should definitely use the project1 template for this project, as opposed to the basic one.

Decide on a name for your project directory, then issue the command ics45c start YOUR_CHOSEN_PROJECT_NAME project1 to create your new project directory using the project1 template. (For example, if you wanted to call your project directory proj1, you would issue the command ics45c start proj1 project1 to create it.) Now you're ready to proceed!


The program

Your program will read the following input from the standard input (i.e., from std::cin):

It's safe to assume that you'll always be given input in the format described above; you are not required to detect erroneous input and report errors, and it's fine if you're program handles incorrect input in any way you'd like, up to and including your program crashing. We will only be testing your program with valid inputs — though you should certainly assume that we'll be testing it using inputs other than the example provided below.

Your program will determine which of the target locations is closest to (i.e., the smallest number of miles away from) the start location, as well as the which target location is farthest from (i.e., the largest number of miles away from) the start location.

After reading all of the input and determining the closest and farthest location, your program will write the following output to the console (i.e., std::cout):

It's not important to limit your output to a particular number of decimal places; feel free to output whatever C++ writes to the output by default, though you should note that latitudes, longitudes, and distances are intended to be numbers with fractional parts (i.e., they are not integers).

An example of the program's execution

The following is an example of the program's execution, as it should appear in the shell. Boldfaced, italicized text indicates input, while normal text indicates ouptut.

33.9425/N 118.4081/W Los Angeles International Airport
3
20.8987/N 156.4305/W Kahului Airport
47.4647/N 8.5492/E Zurich Airport
23.4356/S 46.4731/W Sao Paolo-Guarulhos International Airport
Start Location: 33.9425/N 118.408/W (Los Angeles International Airport)
Closest Location: 20.8987/N 156.43/W (Kahului Airport) (2483.3 miles)
Farthest Location: 23.4356/S 46.4731/W (Sao Paolo-Guarulhos International Airport) (6164.9 miles)

Notice, again, that there are no prompts or other output, other than the output that is required as specified above. This may seem strange, but it's safe to assume that this program is not ultimately intended to have a human user; we'll be running automated tests against it, so welcome prompts, etc., will get in the way of us determining whether your program is correct, and will cause your program to fail every one of our tests.

Also, you may get output that differs in the number of digits after decimal places; in general, that's fine, so long as all of your output is within 0.1% of what we expect in every case (which is more than enough of a buffer to account for inaccuracies introduced by the use of floating-point types like float or double).

(And, for what it's worth, the output above is correct; if you're getting significantly different answers, particularly for the distances between airports, it means that your formulas or your implementation are incorrect.)


Determining the distances between locations

The fundamental operation your program needs is to be able to determine the distance between two locations on Earth. Before you can do that, though, we first need to agree on what is meant by "distance." The Earth is (more or less) spherical and a particular location (i.e., a latitude and longitude) specifies a point somewhere on its surface. When we consider the distance between two such locations, there are two ways to think about it:

As is often the case, there's a tension between what's easier to implement and what's actually required. The straight-line distance would presumably be simpler to calculate, but if our goal is to calculate distances that people might travel, it's a misleading answer — it assumes that people travel from one location on Earth to another by boring a hole in the Earth! The great-circle distance makes a lot more sense when we consider the distances between locations on Earth, because people would tend to travel either along the Earth's surface (e.g., in a car) or roughly parallel to it (e.g., in an airplane).

So, when calculating the distance between two locations, your program's goal is to calculate the great-circle distance between them.

Understanding your problem domain

Before you get too much farther, if you don't know about how the latitude and longitude system works — don't feel bad if you don't, but you do need to understand this in order to solve this problem! — take a look at the section titled Geographic latitude and longitude at this Wikipedia link. In particular, note the limits on allowable latitudes and longitudes and on the difference between North and South latitude and between West and East longitude.

A formula for calculating great-circle distance

Mathematics provides us with multiple formulas for solving a problem like this. Some of these are a better fit for a computer program than others. Since we're dealing with circles, arcs, and angles, it's reasonable to expect that trigonometric functions would be involved; as we'll see, C++ contains a collection of built-in trigonometric functions in its Standard Library, so these will be no problem to incorporate in your program.

Different computational formulas for approximating these distances will give slightly different results, so we'll need to agree on one particular formula. We'll use a formula called the haversine formula, which gives a reasonably precise result even for relatively small distances. An algorithm for calculating the haversine formula, not written in any particular programming language, follows:

let lat1 be the latitude of the first location
let lat2 be the latitude of the second location
let lon1 be the longitude of the first location
let lon2 be the longitude of the second location
let dlat be the difference in latitudes between the locations
let dlon be the difference in longitudes between the locations
let a = sin2(dlat/2) + cos(lat1) * cos(lat2) * sin2(dlon/2)
let c = 2 * atan2(sqrt(a), sqrt(1 - a))
let d = R * c        R, in this part of the formula, is the radius of the Earth

At the conclusion of the algorithm, d is the great-circle distance between the two locations.

(Just to be clear, in the formula above, sin is the trigonometric function sine, cos is the trigonometric function cosine, atan2(y, x) is the arc tangent of y/x, and sqrt means "square root.")

What is the radius of the Earth?

Since we're measuring our distances in miles, we'll need to know the Earth's radius measured in miles. It turns out that the Earth isn't quite spherical, meaning that the radius (as measured by the distance from the center of the Earth to a particular location the Earth's surface) isn't quite the same from one location to another. To keep things simple, though, we'll have to use an approximation; ours will be 3,959.9 miles.


Organizing your program

One of the hallmarks of well-written software is what is sometimes called separation of concerns, the principle that you should handle separate issues in separate parts of a program, rather than munging everything together into fewer, larger, more complex functions. Given your background in programming from previous coursework, even a program as seemingly simple-sounding as this one is one you should be reflexively approaching by dividing it up, whether you're explicitly asked to or not; I imagine you've already developed the ability to work incrementally and test the individual pieces. However, just to be clear, there are some design requirements here.

In general, functions should be relatively short, each having a single job, with the functions' names (and the names of their parameters) clearly and succintly describing their purpose. Source files, too, should be reasonably self-contained, with what software engineers call high cohesion (i.e., the things defined within a source file are strongly related to the others in the same source file) and low coupling (i.e., different source files depend on as few details as possible of the others).

While there is not one particular design that we're requiring, we will be grading partly on your ability to cleanly divide the problem into separate functions, and we would expect to see multiple source files, each with a header file that declares the things that are "public" (i.e., the things you would reasonably expect other source files to use), while keeping other details hidden. Your goal should be to make as few things "public" as possible, though there will obviously need to be some things defined in one source file and used in another.

It's possible to write this program as a single main() function, but you should be aware that a solution like that will be viewed unfavorably; you will likely get a much lower score on this project than you might expect if you go that route. As in real-world software development, your goal is not just to write programs that work, but to write programs well, and that includes style and organization.


Using the C++ Standard Library

Some of the things you'll need to implement in this project are not part of the C++ language, but are instead part of its standard library. There are at least three standard headers you'll need in some parts of your program:

You may find the need for others, but I'd expect any solution to require at least those three.

Where to find documentation on the C++ Standard Library

Other than the document describing the C++ standard, there is no "official" central repository of searchable documentation on the C++ Standard Library, as you would find for languages like Python or Java. However, one very good set of documentation is maintained at cppreference.com. (There are others, too, though I've found that they generally are less complete or more annoying — e.g., by serving up advertisements.)

Being sure to use C++ and not C

This is a course that decidedly focuses on C++ instead of C, but it's important to note that our compiler, Clang, is capable of compiling both C++ and C, so it includes both the C++ and C standard libraries. This introduces a bit of an issue, as some of what's in the C++ Standard Library also appears in C's library. If you're not careful — especially if you seek advice online — you may find yourself using the C library instead of the C++ one.

In the context of this project, there are a couple of things to watch out for.


Deliverables

After using the gather script in your project directory to gather up your C++ source and header files into a single project1.tar.gz file (as you did in Project #0, submit that file (and only that file!) to Checkmate. Refer back to Project #0 if you need instructions on how to do that.

Follow this link for a discussion of how to submit your project via Checkmate. Be aware that I'll be holding you to all of the rules specified in that document, including the one that says that you're responsible for submitting the version of the project that you want graded. We won't regrade a project simply because you submitted the wrong version accidentally. (It's not a bad idea to look at the contents of your tarball on your host operating system before submitting it.)

Can I submit after the deadline?

Yes, it is possible, subject to the late work policy for this course which is described in the section titled Late work at this link.