Cross Country Crossings
Good News! We’re starting a band! It’s called the Totally Super Pythonistas (TSP for short). You’re in charge of planning our first tour. However, I’d prefer if our tour didn’t cross over itself. You’ll also be in charge of finding out where a proposed tour crosses over itself.
Use the provided geometry module to represent locations (a Vector with latitude and longitude).
What you will do
- Make a class called City in file called city.py . The city should have a location (in latitude and longitude), a name, and a state. It should be possible to construct a City object from a string of comma separated values (name, state, latitude, longitude) such as:
Albany,NY,42.67,73.75
Albuquerque,NM,35.08,106.65
Amarillo,TX,35.18,101.83
A list of possible locations is provided, but you should be able to add any cities that have the right format. - Implement __lt__(self, other) for the City class so that you can sort a list of cities. The comparator should should order the cities from west to east. If two cities are at the same longitude, then the one with the lower latitude should be given priority. This magic method defines what should happen when someone writes
city1 < city2 . It also makes it possible to sort a list of cities.
- Make a class called Tour in a file called tour.py . The tour should have a list of cities. The list should not include any duplicates. When you create a Tour, you should pass it a dictionary of possible cities. It should also be possible to add a city to the dictionary of possible tour stops using a method called addpossible_stop . The dictionary should use the city name as a key and the city object as the value. The
addpossible_stop method should have a single parameter that is a city. The
addstop method should take a string and use the dictionary of possible stops to find the rest of the city info.
4. Make a class called TourSegment that extends (inherits from) the Segment class provided in geometry.py . You should define this class in tour.py , the same file where the Tour class is stored. The segment stores a pair of cities in the Tour. When doing inheritance, you sometimes want to both overwrite the constructor, but also call the constructor of the parent class. You can do this by calling __init__ explicitly as in the following example. Notice that the TourSegment class is taking a pair of cities as input, stores them in instance variables ( self._city1 and
self._city2 ), and then extracts the location vectors to send to the Segment constructor.
class TourSegment(Segment):
def __init__(self, city1, city2):
self._city1 = city1
self._city2 = city2
Segment.__init__(self, city1.location(), city2.location())
1. Implement a method findcrossings for a tour that finds all places where the tour would cross over itself if drawn on a map using longitude and latitude as the x- and y-coordinates respectively. The output should be a list of locations. Use the Segment class that was provided to find intersections. Return a tuple (of three items) containing the two segments that intersect and the Vector where they intersect. The intersecting segments should be listed in the order they appear on the tour.
2. Extra Credit The naive approach to finding crossings would check all pairs (quadratic time). Find something better!