Project 4: BruinNav Solution

Introduction







The NachenSmall Maps & Navigation Corporation, owner of the popular turn-by-turn navigation website WeHaveTheBestNavigationSoftwareInTheWorldIfYouCanJustRememberTheURL.com, has decided to stop licensing a 3rd-party turn-by-turn navigation system (from a company who’s name rhymes with "frugal") and instead build their own navigation engine in-house. Given that the NachenSmall leadership team is comprised entirely of UCLA alums, they’ve decided to offer the job to build a prototype of the new navigation system the students of CS32. Lucky you!




So, in your last project for CS32, your goal is to build a simple navigation system that loads and indexes a bunch of Open Street Map geospatial data (which contains latitude and longitude data for thousands of streets and attractions) and then build a turn-by-turn navigation system on top of this data. Your completed Project 3 solution should be able to deliver optimal directions like the following, which detail how to get from 1031 Broxton Ave. (in Westwood) to The Maltz Park in (Beverly Hills):




You are
starting
at: 1031 Broxton Avenue
Proceed
0.09
miles southeast
on Broxton Avenue
Take a left turn
on Kinross Avenue
Proceed
0.07
miles east on Kinross Avenue
Take a right
turn on Glendon
Avenue
Proceed
0.08
miles southeast
on Glendon Avenue
Take a left turn
on Lindbrook Drive
Proceed
0.93
miles east on Lindbrook Drive
Take a right
turn on Holmby Avenue
Proceed
0.08
miles southeast
on Holmby Avenue
Take a left turn
on Wilshire
Boulevard
Proceed
0.92
miles east on Wilshire Boulevard
Take a left turn
on Whittier
Drive
Proceed
0.74
miles north on Whittier Drive
You have reached
your destination: The Maltz Park
Total travel
distance: 2.9 miles



If you’re able to prove to NachenSmall’s reclusive and bizarre CEO, Carey Nachenberg, that you have the programming skills to build a simple navigation engine, he’ll hire you to build the full navigation website, and you’ll be rich and famous.






















3

Anatomy of a navigation engine







All navigation systems operate on geolocation data, like the data you can find at Open Street Maps project:




https://www.openstreetmap.org




Open Street Maps (OSM) is an open-source collaborative effort where volunteers can submit street map data to the project (e.g., the geolocations of various streets and attractions), and OSM incorporates this data into its ever-evolving street map database. Companies like Google and TomTom have their own proprietary street map data as well. In this project, we’ll be using data from Open Street Maps, because it’s freely available.




The OSM data has geolocation (latitude, longitude) data for each street in its map, as well as for attractions (e.g., The Maltz Park, Barney’s Beanery, or Engineering VI) in its map. The OSM data also has geolocation data for some street addresses (e.g., 1031 Broxton Ave), although since each address must be added manually by a contributor, the database contains few such street addresses. Each street is broken up into multiple line segments to capture the contours of the street. As you’ll see, even a simple street like Glenmont Ave (which is a short street that is just one block long) may be broken up into many segments. This is done to capture the curvy contours of the street, since each individual segment can only represent a straight line. For example, here are the segments from OSM for Glenmont Avenue in Westwood - each row has the starting and ending latitude/longitude of a street segment that makes up a part of the overall street:




34.0671191, -118.4379955 34.0670930,-118.4377728




34.0670930, -118.4377728 34.0670621,-118.4376356




34.0670621, -118.4376356 34.0669753,-118.4374785




34.0669753, -118.4374785 34.0668906,-118.4373663




34.0668906, -118.4373663 34.0667584,-118.4372616




34.0667584, -118.4372616 34.0660314,-118.4369524




34.0660314, -118.4369524 34.0658228,-118.4368552




34.0658228, -118.4368552 34.0656493,-118.4367430




34.0656493, -118.4367430 34.0654861,-118.4365909




34.0654861, -118.4365909 34.0653477,-118.4363665




34.0653477, -118.4363665 34.0652111,-118.4359814




34.0652111, -118.4359814 34.0651391,-118.4356096




Notice that the ending lat/long of each segment is the same as the starting lat/long of the following segment, resulting in a contiguous street. And here’s what Glenmont Ave looks like visually:






Let’s consider the first segment in our list, which is highlighted above in red and blue:




34.0671191, -118.4379955 34.0670930,-118.4377728



If you look up 34.0671191, -118.4379955 in Google Maps (just type in these coordinates into the Google Maps search bar), you’ll see that this is the location of the intersection of Malcolm Ave and Glenmont Ave (in the upper-left corner of the map). And if you look up 34.0670930,-118.4377728, you’ll see that this refers to a spot maybe 100 feet down and right from Malcolm Ave, at the point at which Glenmont Ave. begins to curve just bit. Notice that the second segment for Glenmont Ave:




34.0670930, -118.4377728 34.0670621,-118.4376356




is directly connected to the first segment - the ending latitude/longitude of the first segment (in blue) is exactly the same as the starting latitude/longitude of the second segment (in green). In this manner, OSM can represent a long curvy street by stitching together multiple connecting line segments. (By the way, if you’re not familiar with the latitude/longitude system, don’t worry about it - for the purposes of this project, just assume that these are x,y points on a 2D grid.)

Now let’s look at OSM’s data for Malcolm Ave, which as we see in the map above intersects with Glenmont Ave. Here are a limited subset of the line segments that make up this much longer street:




...




34.0679593, -118.4379825 34.0676614,-118.4379719




34.0676614, -118.4379719 34.0673693,-118.4379684




34.0673693, -118.4379684 34.0671191,-118.4379955




34.0671191, -118.4379955 34.0668172,-118.4380882




34.0668172, -118.4380882 34.0665572,-118.4382046




34.0665572, -118.4382046 34.0660665,-118.4385079




34.0660665, -118.4385079 34.0654874,-118.4388836




...




You’ll notice the highlighted line segment in the middle of the list. This line segment begins at coordinate




34.0671191, -118.4379955




which just happens to be the point of intersection of Glenmont and Malcolm, and was the first lat/long amongst the segments we showed you above for Glenmont Ave. We can thus see that these two streets intersect at this point!







So, you can imagine that given a starting geolocation (e.g., 34.0617768, -118.4466596 for 1031 Broxton Ave) and an ending geolocation (e.g., 34.0765967, -118.4196219 for The Maltz Park, a park in Beverly Hills), and given all of the street coordinates for all of the street segments in the OSM database, you should be able to find a contiguous chain of segments from the starting







6
location to the ending location, and then present this route to the user. Each segment that is part of this route will have its starting latitude, longitude matching the ending latitude, longitude of the previous segment.




And that’s the goal of this project - to find a (near) optimal route from some starting coordinate to some ending coordinate!




Right now, you’re probably thinking “There are thousands of streets in LA alone, and tens of thousands of street segments, how the heck am I supposed to sift through all that data to find a viable route?” Well, believe it or not, it’s much easier than you think! And by the end of CS32, you’ll have build your own turn-by-turn navigation system.







Street Map Data File







We will provide you with a simple data file (called mapdata.txt) that contains limited street map data for the Westwood, West Los Angeles, West Hollywood, Brentwood, and Santa Monica areas. This data file has a simplified format and was derived from OSM’s more complicated XML-format data files. Our mapdata.txt file basically has data on thousands of individual street segments, which together make up the entire map. The file also holds the location of a number of popular attractions (e.g., In N Out Burger, Engineering IV) that your program will be responsible for navigating to/from. Here’s an entry for a particular street segment of Gayley Ave. from the mapdata.txt file:




Gayley Avenue




34.0602175, -118.4464952 34.0597400,-118.4460477




3




Iso Fusion Café|34.0600264, -118.4460993 Native Foods Café|34.0599185, -118.4460044 Novel Cafe Westwood|34.0600033, -118.4465424




The first line of each segment holds the name of the street that this segment is associated with.




In this case, this street segment is part of Gayley Avenue.




The second line holds the starting and ending geo-coordinates of the street segment in latitude, longitude format.




The third line specifies a count, C, of how many total attractions there are on this particular street segment.




Finally, there are C lines, one for each attraction found on this particular segment, detailing the name and geo-coordinates of the attraction separated by a pipe | character. Note: C’s value










7
may be zero if there are no attractions on the segment. An attraction may be a place of business (e.g., “Iso Fusion Café”) or a street address (e.g., “1031 Gayley Ave”).




For example, the above data would represent the highlighted street segment below. You can see the attractions (Iso Fusion Cafe, Native Foods Cafe, and Novel Cafe) all represented on the map:







Here’s a slightly longer example from our map data file:




...




Glendon Avenue




34.0591340, -118.4426546 34.0589680,-118.4424895




0




Glendon Avenue




34.0589680, -118.4424895 34.0582358,-118.4421816




1




Pierce Brothers Westwood Village Memorial Park|34.0587141, -118.4418438 Glendon Avenue




34.0582358, -118.4421816 34.0572000,-118.4417620




1




CVS|34.0575488, -118.4423488




Wellworth Avenue




34.0575140, -118.4405712 34.0572000,-118.4417620



…




Notice how the first Glendon Avenue segment has an ending geo-coordinate that matches the second Glendon Avenue segment’s starting geo coordinate (34.0589680,-118.4424895). Further, notice that the second Glendon Avenue segment has an ending geo-coordinate that matches the starting geo-coordinate for the third Glendon Avenue segment (34.0582358, - 118.4421816). So these three segments are effectively chained together by their start/end coordinates. Now consider the Wellworth Avenue segment. Its ending coordinate (34.0572000,-118.4417620) is the same as the ending geo-coordinate of the third Glendon Avenue segment. So this means that this location defines an intersection between Glendon Avenue and Wellworth Avenue. And in fact, if you look this up in Google maps, this is what you’ll see:










So now you know how our mapping data is encoded. And hopefully you’re beginning to see that if you have some clever data structures, given any geo-coordinate, you can determine all segments that start or end at that point. You could then follow each such segment to its other end, and figure out what segments it’s connected to, and so on.







What Do You Need to Do?







For this project you will create five classes (each will be described below in more detail):




You will create a class template MyMap which works much like the C++ STL map and which must use a binary search tree as its data structure. This class template will hold associations between an arbitrary type of key (e.g., a string containing an attraction
name like “Barney’s Beanery”) with an arbitrary type of value (e.g., a latitude/longitude where that attraction is located).




You will create a class MapLoaderImpl that is used to load up the data from the mapdata.txt file that we provide, so the data can be used by your program.



You will create a class AttractionMapperImpl that can be used to look up an attraction by name, e.g. “Mongol BBQ”, and will return that attraction’s geo-coordinate, if it was found in our data file.
You will create a class SegmentMapperImpl that can be used to look up a geo-coordinate (e.g., a latitude/longitude) and will return all segment(s) that are associated with that coordinate. That is, it will return all segments that either start at the specified geo-coordinate, end at the specified geo-coordinate, or have an attraction with the specified geo-coordinate located on the segment.



You will build a class called NavImpl that allows the user to specify a starting attraction (e.g., “Mongol BBQ”), an ending attraction (e.g., “Getty Conservation Institute”), and will then return a vector of turn-by-turn directions required to get from the starting point to the ending point.









What Will We Provide?







We’ll provide you with a header file named provided.h which you must not modify. It defines:




A GeoCoord struct that you can use to hold a particular latitude/longitude, and a GeoSegment struct that defines a segment consisting of starting and ending GeoCoords.
Functions to compute the distance between two GeoCoords, the angle of a GeoSegment, and the angle between two GeoSegments (i.e., street segments).



A StreetSegment struct that holds details of a street segment loaded from a map data file: the name of the street segment, its starting and ending geocoordinates, and a vector of attractions on that segment.
A NavSegment class. The Navigator’s navigate() method returns its routing directions as a sequence of these NavSegments. Each NavSegment holds data on either (a) one segment of the route (e.g., a street name, and the segment’s starting and ending geo-coordinates), or (b) a turn instruction, detailing a turn that must be made between two segments in the route.



MapLoader, AttractionMapper, SegmentMapper, and Navigator classes. The code you write will implement these classes.



We’ll provide a simple main.cpp file that brings your entire program together and lets you test it. You MUST not modify this file, as you will not turn it in with your solution. (Of course, you can modify it during development, but the program you turn in must work correctly with the main.cpp that we provided.)


We also provide you with two data files:




mapdata.txt: Contains all of the mapping data (latitudes and longitudes for each street, street names, etc.) that you have to process in your program.



validlocs.txt: Contains a list of attraction names/addresses (e.g., “Engineering IV” or “Barney’s Beanery”) extracted from mapdata.txt that you can route from or route to when testing your program.



Our Test Driver







If you compile your code with our main.cpp file, you can use it to test your completed classes. Our main.cpp file implements a command-line interface, meaning that if you open a Windows/MacOS Command Shell (e.g., by typing “cmd.exe” in the Windows start box in the bottom-left corner of the screen, or by running the Terminal app in MacOS), and switch to the directory that holds your compiled executable file, you can run our test harness code.




From the command line, you can run the test harness as follows:




C:\PATH\TO\YOUR\CODE BruinNav.exe c:\path\to\the\mapdata.txt "start location name" "end location name”




So, for example, if you wanted our test driver to test out your navigation code to get directions from 1031 Broxton Ave. to The Maltz Park, you’d write:




C:\cs32\p4 BruinNav.exe c:\cs32\p4\mapdata.txt "1031 Broxton Ave." “The Maltz Park”




Our test program will then run, take the inputs you passed on the command line (e.g., The Maltz Park) and pass them to your classes so they can load the appropriate map data and generate a route. The test program will then take the results from your classes (e.g., routing instructions passed back in a vector), and print them to the screen like this:




You are starting at: 1031 Broxton Avenue




Proceed 0.09 miles southeast on Broxton Avenue




Turn left onto Kinross Avenue




Proceed 0.07 miles east on Kinross Avenue




Turn right onto Glendon Avenue




Proceed 0.08 miles southeast on Glendon Avenue




Turn left onto Lindbrook Drive




Proceed 0.93 miles east on Lindbrook Drive




Turn right onto Holmby Avenue




Proceed 0.08 miles southeast on Holmby Avenue




Turn left onto Wilshire Boulevard




Proceed 0.92 miles east on Wilshire Boulevard