ICS 45C Spring 2022, Project #1: Stay (Faraway, So Close!)

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 and header 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

You'll need to complete some chores before you can start working on this project. Be sure you read these instructions and follow them completely before proceeding.

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, so that you have a copy of the project1 project template that you'll need for this project.

Log into your VM and issue the 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.

2022-04-05 11:57:53
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; note that you'd need to be in the same directory where the file is when you run the command.

ics45c-2022spring-environment.tar.gz

Creating your project directory on your ICS 45C VM

A project template has been created specifically for this project and should already be available on your ICS 45C VM. 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):

The first line of the input describes a starting location, from which you'll determine distances to other locations.
The second line of the input specifies a positive number of target locations to which you'll determine distances from the starting location. Note that there is no limit on the number of locations — it could be 1, 10, 100, or even one billion.
Subsequent lines will describe each target location, with one target location specified on each line. You can safely assume that the number of target locations described in the input will match the number specified on the second line.
Locations are specified as a latitude, followed by a space, followed by a longitude, followed by a space, followed by the name of the location. The name of the location is all of the text on the line that follows the space after the longitude.
Latitudes are specified as a non-negative decimal number of degrees between 0 and 90, followed immediately by a slash, followed immediately by a direction (N for north or S for south). Note that the latitudes 0/N and 0/S are equivalent.
Longitudes are specified as a non-negative decimal number of degrees between 0 and 180, followed immediately by a slash, followed immediately by a direction (W for west or E for east). Note that the longitudes 0/W and 0/E are equivalent, as are 180/W and 180/E.

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 your 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):

The words Start Location, followed by a colon and a space, followed by the start location's latitude, followed by a space, followed by the start location's longitude, followed by a space, followed by the name of the start location in parentheses.
The words Closest Location, followed by a colon and a space, followed by the closest location's latitude, followed by a space, followed by the closest location's longitude, followed by a space, followed by the name of the closest location in parentheses, followed by a space, followed by the distance from the start location to the closest location in miles (surrounded by parentheses).
The words Farthest Location, followed by a colon and space, followed by a description of the farthest location in the same format as the closest one.

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:

A straight line traveling through the interior of the sphere, with the two locations as the endpoints of the line. We might call this the straight-line distance between the locations.
The shortest arc that travels along the surface of the sphere that has the two locations as the endpoints of the arc. The length of such an arc is called the great-circle distance between the two locations.

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 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 = sin²(dlat/2) + cos(lat1) * cos(lat2) * sin²(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:

The mathematical operations you'll need — trigonometric functions, calculating square roots, etc. — are declared in the standard header <cmath>.
The I/O operations you'll need, when you want to read console input or write console output, are declared in the standard header <iostream>.
When you want to represent strings in C++, the simplest way is to use the type std::string, which is declared in the standard header <string>.

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.

The C Standard Library includes a standard header <math.h>, which includes many of the same functions as appear in the C++ standard header <cmath>. However, the C++ standard header declares the functions a bit differently — notably, they include std:: in their names, so, for example, the function to calculate a sqrt is std::sqrt. Be sure you're using <cmath> and not <math.h>. (In general, an easy way to tell the difference between standard C++ headers and standard C headers is that C headers have names that end in .h, while C++ headers have no extension on their names at all.)
The C language doesn't have a std::string type. Instead, it represents strings in a much more difficult-to-use way, as pointers to arrays of characters. In this course, we'll prefer std::string, though there will occasionally be times when we have to use C-style strings; I'll point out the need when it arises, but, for now, you should be using std::string.

Avoiding shorthands that reduce program quality

One question I'm often asked early in a C++ course is whether there's a way to eliminate having to specify std:: on every type from the standard library. A lot of students would rather be able to say something like this:

string s = "Alex";

as opposed to something like this instead:

std::string s = "Alex";

It turns out that there's a way to do that, which is to add this line somewhere near the top of your source file (usually right after you've #included the headers you need):

using namespace std;

This line is called a using directive, and what it says is "Hey, compiler, if you've ever seen (or ever see!) any name that's part of the std namespace, I want to be able to use it in this source file without qualification." On a small scale, what we've done is require less typing, because we can now say string instead of std::string. But this is not a tradeoff that stands the test of time:

Suppose that you've #included three standard library headers: <iostream>, <string>, and <cmath>. At this point, you've actually brought in the declarations of an enormous number of names, some that you'll know about (such as cout or endl) and many, many others that you won't.
If you then say using namespace std;, you're telling the compiler that you're comfortable not being allowed to use any of those names yourself without introducing a conflict. That's a fine tradeoff to make for one or two names, but a terrible tradeoff to make for every name in the standard library.
If you say using namespace std; in a header file, then you've made this same tradeoff on behalf of every source file that ever includes that header file!
Note, too, that it might be fine today. But the next time you introduce a new name in that source file, you run the risk of it conflicting with a name from the standard library that you didn't know about. And the next time things are added to the standard library — which is occurring about once every three years as new C++ standards are completed — those names may conflict with names you already chose for your own variables or functions.

Do not use using namespace std; in this course, and you should really consider not using it in your own programs either. Namespaces like std exist for a reason; they make long-lived programs less susceptible to changes in one place causing errors in unrelated places.

It should be noted that there is a middle ground here: Declaring a particular name from the std namespace into the global one. That's actually fairly safe — because you aren't affected when new names are added to the C++ Standard Library going forward — and also pretty straightforward by writing what's called a using declaration.

using std::cout;

If you add that line within a scope (globally, within a function, or wherever), then you've added std::cout to the namespace of things accessible within that scope without requiring qualification. I don't find myself doing that very often, but that's at least a safe way to reduce typing, if that's your goal. (In a more complex program, though, you're reducing typing, but also readability.) I wouldn't ever do it globally (i.e., outside of the scope of anything else) in a header file, because I'm then modifying the meaning of every source file that includes the header file, and that's not a tradeoff I'm ever willing to make.

Note that if you've learned Python previously, what we're talking about here is really the same thing as the difference between these two statements in Python:

from math import *
from math import sqrt

The first of these is something I basically never do in Python (for the same reasons I described with using namespace std in C++ above); the second of these is something I am willing to do, but often don't bother (as I'm perfectly happy to just type math.sqrt, which reads more clearly than the alternative of sqrt).