Preparation

Python functions are first-class objects, so that they can be used as any other object. In particular, functions can be assigned to variables or passed as arguments to other functions. As an example, consider the following three functions.

def repeat(value, func, count):
    for i in range(count):
        value = func(value)
    return value

def increase(value):
    return value + 1

def decrease(value):
    return value - 1

The following interactive Python sessions illustrates how these functions can be used. Start an interactive Python session of your own, define the above functions, and then inspect how Python responds if you call the functions as given below. Before you start with the actual assignment, you should make sure that you fully understand why a certain value is returned and what exactly happens in the interactive session.

>>> increase(5)
>>> decrease(101)
>>> repeat(5, increase, 3)
>>> repeat(5, decrease, 3)
>>> repeat(5, decrease, increase(3))

Introduction

If you think of a circle, you probably have in mind a round drawing that can be made by a compass. However, circles are only round if we use the Euclidean distance. A circle is defined as the set of points in a plane that are at a given distance from a given point (the centre of the circle). If the distance concept is redefined, then the geometry of circles also changes.

But why should we redefine the distance concept? The Euclidean distance corresponds to the distance from a bird's eye view. Such a distance is not always useful in practical applications. Graph distance, for example, defines distance based on a given road map. This way of computing distances is slightly more complicated and requires knowledge of the road map at hand. In this exercises we will — apart from the Euclidean distance — consider two alternative ways to compute distances, which are slightly less complicated than the graph distance.

The Manhattan distance owes its name to the typical pattern of streets in Manhattan where all street either are perpendicular or parallel to each other. In this case, the distance is given as the sum of the difference of the $$x$$-co-ordinates and the difference of the $$y$$-co-ordinates. This corresponds to the path you would take to go from one point to another point if you could only walk parallel to the $$x$$-axis and the $$y$$-axis.

The Chebyshev distance or chessboard distance owes its name to the fact that it corresponds to the number of moves a king needs to go on a chessboard to go from one point to another. In this case, the distance is given as the maximum of the difference of the $$x$$-co-ordinates and the difference of the $$y$$-co-ordinates.

The following table gives an overview of the different formulas that compute the distance between two points $$(x_1, y_1)$$ and $$(x_2, y_2)$$ as defined by the different distance measures. Based on these formulas, can you predict how a circle will look like for each of the different distance measures?

As a result, if we say that a given location is within a given radius around a point $$P$$, we actually should also specify what distance measure we are using. This is what we will do in this exercise.

Assignment

1. Write three functions euclidean_distance, manhattan_distance and chessboard_distance corresponding to the same distance concepts as defined in the above table. Each of these functions takes exactly two arguments. Each argument is a tuple of two floating point numbers that represent the $$x$$- and the $$y$$-coordinate of a point in the plane. The function must return the distance between both points as a floating point number, in accordance with the corresponding distance measure.

2. Write a function location_filter that has two mandatory and two optional parameters. It is mandatory to pass a center (as a tuple of co-ordinates) and a list of points (as a list of tuples of co-ordinates) to the function. In addition, it should also be possible to pass a radius and a distance function. By default, the latter two arguments are set to 1 and the Euclidean distance. The function must return a new list that only contains the points that are in or on the circle that is defined by the given radius and distance function.

Check the example below for more details on how the functions can be used and how they should behave. After submitting your solution, you will get to see several maps give a graphical representation of the circles and the points that are in or on the circle according to your implementation of the function location_filter.

Example

>>> euclidean_distance((0, 0), (3, 4))
5.0
>>> manhattan_distance((0, 0), (3, 4))
7.0
>>> chessboard_distance((0, 0), (3, 4))
4.0
>>> points = [(0, 0), (1, 0), (0, 1), (1, 1), (0, -1), (-1, 1)]
>>> location_filter((0, 0), points)
[(0, 0), (1, 0), (0, 1), (0, -1)]
>>> location_filter((0, 0), points, 2)
[(0, 0), (1, 0), (0, 1), (1, 1), (0, -1), (-1, 1)]
>>> location_filter((0, 0), points, 1, chessboard_distance)
[(0, 0), (1, 0), (0, 1), (1, 1), (0, -1), (-1, 1)]
>>> location_filter((1, 0), points, 2, manhattan_distance)
[(0, 0), (1, 0), (0, 1), (1, 1), (0, -1)]