The problem of determining whether a point belongs to a polygon

Hello, dear habravchane!
In the process of developing an application for Android, which involves user interaction with graphic primitives (dots, lines, ellipses, rectangles, etc.), a rather unpleasant situation arose: the user can define an arbitrary polygon and make it inactive, but in the future activate this polygon and continue working with it (for example, move to another place or add / delete vertices) it is necessary for an inactive object to determine whether the user has touched this object, ie it was necessary to solve the problem of the point belonging to the polygon.

This problem is widely known in computational geometry and I bring to your attention the results of my research on this topic.

Introduction

Computational geometry usually assumes that a polygon is simple, i.e. without self-intersections, but the problem is also considered for complex polygons. This problem is most often solved by the following methods:

• the method of taking into account the number of intersections, which counts the number of times the ray outgoing from point P crosses the boundaries of the polygon. If the number of intersections is odd, then it is declared that the point lies inside the polygon, if it is even - outside.
• method of counting the number of revolutions, which counts the number of revolutions, which makes the oriented boundary of the polygon around a given point P. In algebraic topology, this number is called the winding number. A point is considered to lie outside the polygon only if the number of revolutions is zero, otherwise the point lies inside the contour of the polygon.

If the polygon is simple (that is, it does not have self-intersections), then both methods give the same result for all points. However, if the polygon has a complex shape, then the methods may return different results for some points. For example, if a polygon intersects with itself, then when using the method of taking into account the intersections, points in the intersection region are defined as points outside. However, the same points will be considered lying inside the polygon when using the method of counting the speed (see figure).


')
The method of counting the number of intersections and its optimization are described in detail in this article, so let's consider the second algorithm for solving the problem.

Turnover Method

This method determines whether a point lies inside a complex polygon, comparing how many times a polygon is wrapped around a point. The point does not belong to the polygon only in the case when the number of revolutions (winding number) is zero.

Let a continuous two-dimensional curve C be defined by the points C (u) = C (x (u), y (u)) , where 0 ≤ u ≤ 1 and C (0) = C (1) . Also let P be a point not lying on the curve C. Declare the vector c (P, u) (from point P to curve C ):



and the unit vector w (P, u) :

,

which gives a continuous function W (P): C → S ¹ , mapping the point C (u) of the curve C to the point w (P, u) on the unit circle S ¹ = {(x, y) | x2 + y2 = 1} . This mapping can be represented in polar coordinates:

,

where θ (u) is a positive counterclockwise rotation in radians.
Then the rotation number wn (P, C) of a continuous curve C around the point P is equal to an integer number of times when W (P) turns the curve C around the unit circle S ¹ . This corresponds to the homotopy class S ¹ and can be calculated through the integral:



When curve C is a polygon with vertices V ₀ , V ₁ , ..., V _n = V ₀ , the integral is reduced to the sign sum of the angles at which each edge of the polygon V _i V _{i + 1 is} opposite to the point P. Thus, if θ _i is equal to the angle between PV _i and PV _{i + 1} , then:

(one)

The figure shows how you can graphically represent the signed sum of the angles.


It is obvious that formula (1) is not very effective, since it uses the compositive power of the arcgon-sine trigonometric function. It is necessary to replace this formula with a more efficient one.

Optimization of the method of accounting for turnovers

Take any point Q on the unit circle. Then, as the curve W (P) wraps around S ¹ , it passes the point Q a certain number of times. If we count (+1) when the curve passes Q counterclockwise, and (-1) when the curve passes clockwise, the accumulated amount will be the total number of times W (P) is wrapped around S ¹ and equal to wn (P , C) is the number of revolutions of the continuous curve C around the point P. Further, if we take an infinite ray R with a beginning at the point P and passing in the direction of the vector Q , then the intersection of the ray R and the curve C corresponds to the point where W (P) passes Q. To develop a mathematical apparatus, it is necessary to distinguish between positive and negative transitions, where C crosses R in directions from right to left or from left to right. This can be determined by the sign of the scalar product of the normal vector to C and the direction of the vector q = Q , and it is necessary to calculate the scalar product for each edge of the polygon. For a horizontal ray R with the origin at point P , it is sufficient to check whether the edge of the edge is above or below the ray. If the edge intersects the direct ray from bottom to top, then the intersection is positive (+1), but if it intersects the edge from top to bottom, then the intersection is negative (-1). The sum of the intersection signs gives the number of revolutions wn (P, C) .



Moreover, it is possible to avoid calculating the actual intersection point of the edge and ray. To do this, it is sufficient to determine from which side the edge intersects the ray. If the ascending edge intersects the ray to the right of point P , then P is to the left of the edge, since the triangle V _i V _{i + 1} P is oriented counterclockwise. If the descending edge intersects the ray from the left, then the point P is located to the right of the edge, since the triangle V _i V _{i + 1 is} oriented clockwise.



The figure on the left shows the ascending edge, and on the right - the descending edge.

In conclusion, I would like to say that the method of accounting for turns requires a complete search of the vertices of a given polygon, and this, in my opinion, is its drawback. However, it is more than compensated by the ease of implementation and the presence of only two multiplication operations at each iteration of the loop through the vertices.

UPD:

Implementation

Probably in vain, I did not immediately attach the source code, so I am fixing it.


Primary source: GeometryAlgorithms.com