Voorbereiding

In Python zijn functies zelf ook objecten, waardoor je ze kunt gebruiken zoals alle andere objecten. In het bijzonder kun je functies toekennen aan variabelen of doorgeven als argument aan andere functies. Bekijk bijvoorbeeld onderstaande drie functies.

def herhalen(waarde, functie, aantal):
    for i in range(aantal):
        waarde = functie(waarde)
    return waarde

def verhogen(waarde):
    return waarde + 1

def verlagen(waarde):
    return waarde - 1

Hieronder staat een voorbeeld van hoe deze functies gebruikt kunnen worden. Ga na hoe Python reageert als je achtereenvolgens de volgende instructies uitvoert binnen een interactieve Python sessie waarin je eerst zorgt dat bovenstaande functies gedefinieerd werden. Verzeker jezelf ervan dat je goed begrijpt waarom je een bepaalde waarde krijgt en wat er juist gebeurt in de interactieve sessie vooraleer je verder gaat met de eigenlijke opgave.

>>> verhogen(5)
>>> verlagen(101)
>>> herhalen(5, verhogen, 3)
>>> herhalen(5, verlagen, 3)
>>> herhalen(5, verlagen, verhogen(3))

Inleiding

Als je aan een cirkel denkt, dan denk je meteen aan de ronde tekening die je met een passer kan maken. Dat is echter alleen maar zo omdat we zo gewoon zijn om te werken met de Euclidische afstand. Een cirkel wordt gedefinieerd als een verzameling van punten die allemaal op een bepaalde afstand liggen van een gegeven punt (het centrum of middelpunt van de cirkel). Als je het concept afstand zou herdefiniëren dan verandert ook het uitzicht van een cirkel.

Maar waarom zou je het concept afstand willen herdefiniëren? De Euclidische afstand komt overeen met de afstand in vogelvlucht. Deze is niet altijd even bruikbaar bij praktische problemen. Daarom heb je bijvoorbeeld de graafafstand die de afstand definieert aan de hand van de afstand via een wegennet. Deze manier om een afstand te berekenen is echter iets ingewikkelder en vraagt de kennis van het weggennet in casu. We gaan in deze opgave — naast de Euclidische afstand — twee andere manieren beschouwen om de afstand te berekenen, die iets gemakkelijker zijn dan deze graafafstand.

De Manhattan-afstand dankt zijn naam aan het typische stratenpatroon van Manhattan waar alle straten ofwel loodrecht op elkaar staan ofwel evenwijdig met elkaar lopen. In dit geval wordt de afstand gegeven als de som van het verschil van de $$x$$-coördinaten en het verschil van de $$y$$-coördinaten. Dit komt overeen met de weg die je zou afleggen om van het ene punt naar het andere punt te gaan als je enkel evenwijdig met de $$x$$-as en de $$y$$-as zou mogen wandelen.

De Chebyshev-afstand of de schaakbord-afstand dankt zijn naam aan het feit dat op een discreet rooster deze afstand overeenkomt met het aantal zetten dat het schaakstuk koning nodig heeft om van het ene punt naar het andere punt te gaan. De afstand wordt in dit geval gegeven door het maximum van het verschil van de $$x$$-coördinaten en het verschil van de $$y$$-coördinaten.

In onderstaande tabel vind je een overzicht van de verschillende formules voor de afstand tussen twee punten $$(x_1, y_1)$$ en $$(x_2, y_2)$$ zoals die wordt gedefinieerd door deze verschillende afstandsmaten. Kan je op basis van deze formules voorspellen hoe een cirkel er zal uitzien voor elk van deze vormen van afstand?

naam formule
Euclidische afstand $$d=\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$$
Manhattan-afstand $$d=|x_1-x_2| + |y_1-y_2|$$
schaakbord-afstand $$d=\max(|x_1-x_2|,|y_1-y_2|)$$

Als je dus zegt dat een bepaalde plaats binnen een gegeven straal rond het punt $$P$$ ligt, dan moet je er eigenlijk ook bijzeggen welke definitie van afstand je gebruikt. Dit is dan ook wat we in deze opgave gaan doen.

Opgave

  1. Schrijf drie functies euclidische_afstand, manhattanafstand en schaakbordafstand die corresponderen met de gelijknamige concepten voor het begrip afstand zoals die in bovenstaande tabel gedefinieerd werden. Aan elk van deze functies moeten verplicht twee argumenten doorgegeven worden. Elk argument is een tuple van 2 reële getallen die de $$x$$- en de $$y$$-coördinaat van een punt in het vlak voorstellen. Als resultaat geven deze functies telkens de afstand tussen de twee gegeven punten terug als een reëel getal, overeenkomstig de corresponderende definitie van afstand.

  2. Schrijf een functie locatiefilter die twee verplichte parameters en twee optionele parameters heeft. Verplicht moeten eerst een centrum als een tuple van coördinaten en een lijst van punten (dit is dus een lijst van tuples van coördinaten) doorgegeven worden. Vervolgens kan je ook een straal en een afstandsfunctie doorgeven. Standaard worden deze laatste argumenten ingesteld op respectievelijk 1 en de Euclidische afstand. Deze functie geeft dan een nieuwe lijst terug die enkel die punten bevat die op of binnen de cirkel liggen die beschreven wordt door de straal en de afstandsfunctie.

Bekijk zeker ook onderstaand voorbeeld voor meer details over hoe de functies kunnen gebruikt worden en hoe ze zich moeten gedragen. Na het indienen van een oplossing krijg je enkele kaartjes te zien die de verschillende cirkels tonen en de locaties die volgens jouw functie binnen deze cirkels gelegen zijn.

Voorbeeld

>>> euclidische_afstand((0, 0), (3, 4))
5.0
>>> manhattanafstand((0, 0), (3, 4))
7.0
>>> schaakbordafstand((0, 0), (3, 4))
4.0
>>> punten = [(0, 0), (1, 0), (0, 1), (1, 1), (0, -1), (-1, 1)]
>>> locatiefilter((0, 0), punten)
[(0, 0), (1, 0), (0, 1), (0, -1)]
>>> locatiefilter((0, 0), punten, 2)
[(0, 0), (1, 0), (0, 1), (1, 1), (0, -1), (-1, 1)]
>>> locatiefilter((0, 0), punten, 1, schaakbordafstand)
[(0, 0), (1, 0), (0, 1), (1, 1), (0, -1), (-1, 1)]
>>> locatiefilter((1, 0), punten, 2, manhattanafstand)
[(0, 0), (1, 0), (0, 1), (1, 1), (0, -1)]