Suppose that we work with an interactive map of Europe, which allows you to select a country and displays its local map in response. The first task the geographic information system must address to this end is determining which country contain the mouse pointer at the moment whether you made the click. This is a so-called point location problem. Now, suppose that certain special information needs to be displayed to the user in case she is interested in a particular country. For example, these might be details on the train schedule perturbed because of an accident. Then the question takes the following form. Given a region and point, determine whether the letter lies inside the formal? In practice, regions of interest often represent polygons. Consequently, the task to be addressed becomes a well-known computational geometry problem called pointer inclusion in the polygon. Now, let us formalize the problem statement. First of all, we will need to provide a definition of a polygon. A simple polygon is a subset of the plane bounded with a non self-intersecting piece-wise linear curve. On the left, you see an example of a simple polygon. A region of the plane bounded with the self-intersecting piece-wise linear curve is not a simple polygon. Here you see a polygon with holes. Its boundary comprises a collection of pairwise disjoint non self-intersecting piecewise linear curve. Such a polygon is also not considered simple. In what follows, when speaking of polygons, we will always assume them to be simple, unless explicitly stated otherwise. In a programming code, a polygon is typically represented by an array or a list (possibly circular) that stores it vertices. A polygon vertex is simply a point represented by two its coordinates. Thereby, it is common to order the polygon vertices counterclockwise This means that when walking from the current vertex to the next one, we're locally have the interior of the polygon on our left. You can easily verify that the labeling of the vertices you see in the left of this slide, satisfies this requirement. For example, imagine walking along the polygon edge, from the vertex v_1 to v_2, then indeed the interior of the polygon will be on your left-hand side. But if we label the polygon vertices in the clockwise order, the desired property will no longer hold. Indeed now, while walking from the vertex v_1 to v_2, you will have the interior of the polygon on your right. Now, let us get back to our problem. We are given a planar polygonal region and an indicated point, and wonder whether this point lies inside the region of interest like in this case, or outside it like in this case. The formal problem statement is the following. Given a polygon P and the point q, determine whether q lies inside P?