[MUSIC] To get an intuition about how we will proceed to test point inclusion in a polygon, imagine that on a sunny day, you walk along the street with a number of high buildings. At some moment you will find yourself in the sunshine, but keeping on moving at some point you will cross the boundary of the next shaded region and you will be in the shadow unless you cross this boundary for the second time. Then you will have to tolerate the sun until the boundary of the next shadow spot and so on. Let us see how similar observations can help us to develop an algorithm for testing point inclusion in the polygon. Given the polygon P and the point q, we need to check whether q lies inside P. First, let us shoot from q, a horizontal ray out to the left. For now, assume that the ray r doesn't pass through the vertices of P. Next, imagine that we stay on the ray r very far from the polygon P. In such a case, it is common to say that we'll reside at the infinity. In reality, what matters is that initially, we are certainly outside the polygon P. Now let us start moving from the infinity toward the point q. While crossing the boundary of the polygon P, we will alternate between its inner and outer regions. To make this more precise, at the first crossing we will get inside the polygon P. In the second crossing, we will get outside P. At the third crossing we will again get inside P and so on. That's to determine whether the point q lies inside the polygon P. We need to calculate the number of intersections of the ray r with the boundary of P. In this example, the ray r intersects the boundary of the polygon P three times which indicates that q lies inside P. And if the number of crossings is even, then q lies outside P. If we shift the point q from our example to the right as shown in this slide, then the number of intersections of the ray r with the polygon boundary will be 4. Which will indicate the point q lies outside the polygon P. Finally, note that the ray r doesn't need to be horizontal. The reason why we choose it to be horizontal is that the horizontal ray is easy to store and handle. In particular, if we know that the ray r emanates from the point q to the left, it is sufficient to know the coordinates of the point q, to unambiguously restore r.