You are given a text file containing a list of countries, together with a description of their borders. Each line of the file contains the name of a country, followed by a tab and a list of an even number of real values that are separated by spaces. The list of $$2n$$ real values describes a polygon having $$n$$ successive vertices (listed in clockwise or counterclockwise order) on the border of the country. Each point $$p$$ on Earth is described by a tuple $$(p_b, p_l)$$, where $$p_b \in \mathbb{R}$$ indicates the latitude and $$p_l \in \mathbb{R}$$ indicates the longitude of the point. Accordingly, each point $$(p_b, p_l)$$ on the border of a country is described by two successive numbers $$p_b, p_l \in \mathbb{R}$$ in the list of real values. Below we give an example of a small portion of such a text file.

Afghanistan	37.24 74.92 37.18 74.39 37.03 74.57 36.82 72.56 36.13 71.24 ...
Albania	41.02 19.44 41.80 19.60 41.85 19.37 42.62 19.65 42.56 20.07 ...
Algeria	36.80 2.96 36.89 4.79 36.64 5.33 37.09 6.40 36.94 8.62 ...
American Samoa	-14.30 -170.54 -14.29 -170.56 -14.28 -170.54 -14.30 -170.54 ...
Andorra	42.57 1.78 42.51 1.73 42.60 1.45 42.57 1.78
...

Given a text file that is formatted as described above, your task is to determine the country for each given point on Earth. If we assume that a polygon describing the border of a country is plane figure, all we need to able to do is determine whether or not a given point $$c = (c_b, c_l)$$ is inside or outside the given $$n$$-gon (a polygon with $$n$$ sides) with successive vertices $$p_1, p_2, \ldots, p_n$$.

This can be done by counting the number of edges of the polygon for which the following two conditions are both fulfilled: \[\begin{cases} c_l < p_l \textrm{ or } c_l < q_l \textrm{ (but not both)}\\ c_b - q_b < \dfrac{p_b - q_b}{p_l - q_l}(c_l - q_l) \end{cases}\] Herewith, each edge is represented by two successive vertices $$p = (p_b, p_l)$$ and $$q = (q_b, q_l)$$, and the vertices of the polygon are iterated consistently in clockwise or counterclockwise order. If an odd number of edges fulfills the above conditions, the point $$c$$ is located inside the polygon. Otherwise it is located outside the polygon.

Assignment

Define a class Polygon that can be used to represent planar polygons in Python. This class must support at least the following methods:

• An initialisation method that takes a list of points in the two-dimensional plane. These points represent the successive vertices of a polygon (in clockwise or counterclockwise order). Each point is described by a tuple $$(withx, y)$$,  $$x, y \in \mathbb{R}$$.

• A method contains that takes a point in the two-dimensional plane. The method must return a Boolean value that indicates whether or not the given point is inside the polygon.

Use the class Polygon to define a class WorldMap. An object of the class WorldMap represents a list of countries, where the border of each country is represented as a planar polygon. The class WorldMap must support at least the following methods:

• An initialisation method that takes the location of a text file. This file must contain a list of countries and the description of their borders, using the format as outlined in the introduction of this assignment.

• A method borders that takes the name of a country. The method must return a planar polygon (an object of the class Polygon) that describes the border of the given country, as defined in the given text file. Herewith, the name of the country must exactly match the name of one of the countries in the given text file. If this is not the case, the method must raise an AssertionError with the message unknown country.

• A method country that takes the location of a point on Earth (a tuple). Based on the given text file, the method must determine in which country this point is located, and return the name of that country. In case the given point is not inside any country contained in the text file, the method must return the value None.

Example

In the following interactive session, we assume that the text file countries.txt¹ is located in the current directory.

>>> polygon = Polygon([(0, 0), (0, 1), (1, 1), (1, 0)])
>>> polygon.contains((0.5, 0.5))
True
>>> polygon.contains((1.5, 0.5))
False
>>> polygon.contains((0.5, 1.5))
False
>>> polygon.contains((-0.5, 0.5))
False
>>> polygon.contains((0.5, -0.5))
False

>>> map = WorldMap('countries.txt')    
>>> map.border('Belgium').contains((50.5, 4.2))   # Brussels
True
>>> map.border('France').contains((50.5, 4.2))    # Brussels
False
>>> map.border('Legoland')
Traceback (most recent call last):
AssertionError: unknown country
>>> map.country((50.5, 4.2))     # Brussels
'Belgium'
>>> map.country((45.25, -75.42)) # Ottawa
'Canada'
>>> map.country((-17.5, 31.03))  # Harare
'Zimbabwe'
>>> map.country((-16.3, -68.09)) # La Paz
'Bolivia'
>>> map.country((-10.0, -20.0)) # ???