De Russische MiG-23 piloot Nikolai Skuridin was op 4 juli 1989 een routinevlucht aan het uitvoeren in de buurt van Kolobrzeg in Polen, toen één van zijn naverbranders de geest gaf. Skuridin gebruikte zijn schietstoel in de veronderstelling dat de motor het volledig had begeven, maar het vliegtuig herstelde zich en vloog op automatische piloot richting het westen.

Het toestel moet vrij veel brandstof aan boord gehad hebben, want het vloog vanuit Polen Oost-Duitsland binnen, daarna naar West-Duitsland, en dan naar Nederland waar een gealarmeerde Amerikaanse luchtmachtbasis twee F-15s liet opstijgen om het gezelschap te houden. Toen de MiG het Belgische grondgebied betrad, kregen de F-15s opdracht om het toestel neer te halen van zodra het de Noordzee zou bereiken. Vlak voor de Franse grens kwam het echter zonder brandstof te zitten en crashte het in een huis, waarbij een tiener het leven liet.

De volledige route die het vliegtuig had afgelegd was meer dan 900 kilometer lang. Toenmalig Belgisch Minister van Buitenlandse Zaken Mark Eyskens was razend over het feit dat de Sovjets geen waarschuwing uitgestuurd hadden en geen enkele informatie vrijgegeven hadden over mogelijke gevaarlijke wapens die het onbemande vliegtuig aan boord had. Achteraf bleek dat het vliegtuig onbewapend was, op wat munitie voor een 23mm machinegeweer na.

Opgave

Alvorens een vliegtuig mag opstijgen, moet de piloot of de vliegtuigmaatschappij eerst een vliegplan indienen bij de luchtverkeersleiding. Naast de luchthaven van vertrek en aankomst, bevat dit vliegplan welke route men wil volgen, op welke hoogte men deze route wil vliegen, met welk vliegtuig (type, vliegtuigregistratienummer), hoeveel passagiers er aan boord zijn, enzoverder.

Bij deze opgave krijg je een tekstbestand in CSV formaat (comma-separated values) met gegevens over een aantal luchthavens. Voor elke luchthaven bevat het bestand twaalf informatievelden, waarbij voor deze opgave enkel de unieke 3-lettercode van de luchthaven (eerste veld) belangrijk is, samen met de breedte- en lengtegraad (respectievelijk velden 6 en 7) van de ligging van de luchthaven. Op basis van deze informatie moet je een eenvoudige routeplanner schrijven waarmee de vliegroute kan bepaald worden voor gegeven luchthavens van vertrek en aankomst, en voor een gegeven maximale actieradius van een vliegtuig.

Omdat de afstand tussen de luchthaven van vertrek en de luchthaven van aankomst groter kan zijn dan de actieradius van het vliegtuig, moet de routeplanner mogelijks een aantal tussenliggende luchthavens uitkiezen waar het vliegtuig kan bijtanken. Het vliegplan wordt vastgelegd door startend vanaf de luchthaven van vertrek, telkens de volgende nog niet bezochte luchthaven binnen de actieradius van het vliegtuig te bezoeken die het dichtst bij de bestemming gelegen is. Deze procedure wordt herhaald totdat de luchthaven van aankomst bereikt wordt, of totdat geen enkele luchthaven kan bereikt worden die aan de gestelde voorwaarden voldoet.

In deze opgave stellen we een punt op Aarde voor als een tuple met twee floating point getallen, die respectievelijk de breedte- en de lengtegraad van het punt voorstellen (uitgedrukt in graden). We noemen dit de coördinaten van het punt. Voor het bepalen van de afstand tussen twee luchthavens met coördinaten $$(b_1, l_1)$$ en $$(b_2, l_2)$$ maken we gebruik van de Haversine-afstand $$d$$, die bepaald wordt aan de hand van de formule \[\begin{aligned}[c] a & = \left(\sin\left(\frac{b_2-b_1}{2}\right)\right)^2 + \cos(b_1)\cos(b_2)\left(\sin\left(\frac{l_2-l_1}{2}\right)\right)^2 \\ c & = \arctan\left(\sqrt{\frac{a}{1-a}}\right) \\ d & = 2rc \end{aligned}\] Hierbij stelt $$r$$ de aardstraal voor. Gevraagd wordt:

• Schrijf een functie coordinaten waaraan de locatie van een CSV bestand moet doorgegeven worden. Dit bestand moet informatie bevatten over een aantal luchthavens, volgens het formaat zoals beschreven in de inleiding van de opgave. De functie moet een dictionary teruggeven die de unieke 3-lettercode van elke luchthaven uit het bestand afbeeldt op de coördinaten van de luchthaven.

• Schrijf een functie haversine waaraan twee coördinaten moeten doorgegeven worden. De functie moet de Haversine-afstand tussen de punten met gegeven coördinaten teruggeven, als uitgegaan wordt van een constante benadering van 6371 km als straal van de Aarde. Let erop dat de goniometrische functies (sin, cos, ...) uit de math module hoeken verwachten die uitgedrukt zijn in radialen, niet in graden. De math module heeft echter ook twee functies degrees en radians die hoeken omzetten van radialen naar graden, en omgekeerd.

• Gebruik de functie haversine om een functie vliegplan te schrijven waarmee de route van een vliegtuig kan bepaald worden. Aan deze functie moeten drie argumenten doorgegeven worden. De eerste twee argumenten stellen de unieke 3-lettercodes voor van de luchthavens van vertrek en aankomst. Het derde argument is een dictionary die de unieke 3-lettercodes van luchthavens afbeeldt op hun coördinaten. Bovendien heeft deze functie nog een optionele parameter actieradius waaraan de actieradius van het vliegtuig kan doorgegeven worden (uitgedrukt in kilometer; standaardwaarde: $$1000\mbox{ km}$$). De functie moet de lijst van 3-lettercodes teruggeven van alle luchthavens die het vliegtuig op zijn route zal aandoen, op basis van het routeplanningsalgoritme dat hierboven werd beschreven. Hierbij zijn de eerste en laatste code respectievelijk deze van de gegeven luchthavens van vertrek en aankomst. Indien bij het bepalen van het vliegplan geen enkele luchthaven kan bereikt worden die aan de gestelde voorwaarden voldoet, dan moet de functie een AssertionError opwerpen met de boodschap geen mogelijke route.

CSV formaat

CSV formaat (comma-separated values in het engels) is een specificatie voor tekstbestanden waarin gegevens in tabelvorm opgeslaan worden. Hierbij worden de waarden in de verschillende kolommen van de tabel van elkaar gescheiden door komma's, en worden de rijen van de tabel van elkaar gescheiden door regeleindes. Beschouw bijvoorbeeld de volgende tabel

De gegevens in deze tabel worden op de volgende manier opgeslaan in een CSV bestand

jaar,merk,type,omschrijving,prijs
1997,Ford,E350,"airco, abs, moon",3000.00
1999,Chevy,"Type ""Extended Edition""",,4900.00
1996,Jeep," Grand Cherokee ","IS VERKOCHT!
air, moon roof, loaded",4799.00 

Dit illustreert nog een aantal bijkomende regels die gelden voor CSV bestanden:

• de eerste regel kan kolomtitels bevatten, maar die regel is niet verplicht

• velden die komma's, aanhalingstekens (") of regeleindes bevatten, en velden die beginnen en/of eindigen met een spatie, moeten omsloten worden door aanhalingstekens

• aanhalingstekens binnen een veld worden verdubbeld

Om bij het verwerken van CSV bestanden zelf geen rekening te moeten houden met al deze extra regels, kan je in Python best gebruikmaken van de csv module, die deel uitmaakt van de Python Standard Library.

Voorbeeld

Bij onderstaande voorbeeldsessie gaan we ervan uit dat het tekstbestand luchthavens.csv¹ zich in de huidige directory bevindt.

>>> coords = coordinaten('luchthavens.csv')
>>> len(coords)
9187
>>> type(coords)
<class 'dict'>
>>> coords['BRU']
(50.902222, 4.485833)
>>> coords['CDG']
(49.016667, 2.55)
>>> coords['DCA']
(38.851944, -77.037778)
>>> coords['LAX']
(33.9425, -118.407222)

>>> haversine((50.902222, 4.485833), (49.016667, 2.55)) # BRU <-> CDG
251.2480027355068
>>> haversine((38.851944, -77.037778), (33.9425, -118.407222)) # DCA <-> LAX
3710.8262543589817

>>> vliegplan('DCA', 'LAX', coords)
['DCA', 'MTO', 'HLC', 'BFG', 'LAX']
>>> vliegplan('DCA', 'LAX', coords, actieradius=2000)
['DCA', 'DDC', 'LAX']
>>> vliegplan('DCA', 'LAX', coords, actieradius=4000)
['DCA', 'LAX']
>>> vliegplan('BRU', 'CDG', coords)
['BRU', 'CDG']
>>> vliegplan('BRU', 'CDG', coords, actieradius=50)
Traceback (most recent call last):
AssertionError: geen mogelijke route