February 13, 2013 at 19:34The 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 (points, lines, ellipses, rectangles, etc.), a rather unpleasant situation arose: the user can set an arbitrary polygon and make it inactive, however, so that in the future there is a possibility activate this polygon and continue working with it (for example, move it to another place or add / remove vertices) it is necessary for an inactive object to determine whether the user has touched a given object, ie it was necessary to solve the question of whether a point belongs to a polygon.
This problem is widely known in computational geometry and I bring to your attention the results of my research on this topic.
In computational geometry, it is usually assumed that the polygon is simple, i.e. without self-intersections, but the problem is also considered for polygons of complex shape. This problem is most often solved by the following methods:
If the polygon is simple (i.e. 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 can return different results for some points. For example, if the polygon intersects with itself, then when using the method of accounting for intersections, points in the region of intersection are defined as points outside. However, the same points will be considered to lie inside the polygon when using the method of accounting for the number of revolutions (see. Figure).
The method of accounting for the number of intersections and its optimization are described in detail in this article, so let's look at the second algorithm for solving the problem.
This method accurately determines whether a point lies inside a complex polygon by comparing how many times the polygon wraps around a point. A point does not belong to a polygon only if the 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 - a point which does not lie on the curve of the C . Declare vector c (P, u) (from the point P to a curve C ):
and a unit vector w (P, u) :
,
which gives a continuous function W (P): C → S1 , mapping the point C (u) of the curve C to the point w (P, u) on the unit circle S 1 = {(x, y) | x2 + y2 = 1} . This mapping can be represented in polar coordinates
,
where theta (u) - a positive counterclockwise rotation in radians.
Then the number of revolutions wn (P, C) of the continuous curve C around the point P is equal to the integer number of times when W (P) rotates the curve C around the unit circle S 1 . This corresponds to the homotopy class S 1and can be calculated through the integral:
When the curve C is a polygon with vertices V 0 , V 1 , ..., V n = V 0 , 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:
(1)
The figure shows how you can graphically represent the sign sum of the angles.
Obviously, formula (1) is not very effective because it uses the trigonometric function of the arccosine, which is computationally demanding. It is necessary to replace this formula with a more effective one.
Take any point Q on the unit circle. Then, as the curve W (P) wraps around S 1 , it passes the point Q a certain number of times. If we assume (+1) when the curve passes Q counterclockwise, and (-1) when the curve passes clockwise, the accumulated sum will be the total number of times how many W (P) wraps around S 1 and is equal to wn (P , C) - the number of turns of a continuous curve C around the point P . Further, if we take an infinite ray R with origin at point Pand extending in the direction of the vector Q , the intersection of beam R , and curve C corresponds to the point where W (P) extends Q . To develop a mathematical apparatus, it is necessary to distinguish between positive and negative transitions, where C intersects R in the 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 origin at point P, just checking if the end of the rib is above or below the beam. If an edge crosses a direct ray from bottom to top, then the intersection is positive (+1), but if it crosses an edge from top to bottom, then the intersection is negative (-1). The sum of the intersection marks gives the number of revolutions wn (P, C) .
Moreover, it is possible to avoid calculating the actual point of intersection of the edge and beam. To do this, it is enough to determine which side the edge intersects with the beam. If the ascending edge intersects the ray to the right of the point P , then P is to the left of the edge, because the triangle V i V i + 1 P is oriented counterclockwise. If the descending edge crosses the ray on the left, then the point Pis 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 revolutions requires a complete enumeration 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 operations of multiplication at each iteration of the loop of enumeration of vertices.
UPD:
Probably in vain I did not immediately attach the source code, so I am correcting myself.
Primary Source: GeometryAlgorithms.com
In the process of developing an application for Android, which involves user interaction with graphic primitives (points, lines, ellipses, rectangles, etc.), a rather unpleasant situation arose: the user can set an arbitrary polygon and make it inactive, however, so that in the future there is a possibility activate this polygon and continue working with it (for example, move it to another place or add / remove vertices) it is necessary for an inactive object to determine whether the user has touched a given object, ie it was necessary to solve the question of whether a point belongs to a polygon.
This problem is widely known in computational geometry and I bring to your attention the results of my research on this topic.
Introduction
In computational geometry, it is usually assumed that the polygon is simple, i.e. without self-intersections, but the problem is also considered for polygons of complex shape. This problem is most often solved by the following methods:
- by the method of taking into account the number of intersections, which counts how many times the ray leaving the point P intersects the boundaries of the polygon. If the number of intersections is odd, then it is declared that the point lies inside the polygon, if even - outside.
- rev metering method, which counts the number of revolutions, which makes oriented polygon boundary around a given point P . In algebraic topology, this number is called the winding number. A point is considered to be lying 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 (i.e. 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 can return different results for some points. For example, if the polygon intersects with itself, then when using the method of accounting for intersections, points in the region of intersection are defined as points outside. However, the same points will be considered to lie inside the polygon when using the method of accounting for the number of revolutions (see. Figure).
The method of accounting for the number of intersections and its optimization are described in detail in this article, so let's look at the second algorithm for solving the problem.
Speed metering method
This method accurately determines whether a point lies inside a complex polygon by comparing how many times the polygon wraps around a point. A point does not belong to a polygon only if the 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 - a point which does not lie on the curve of the C . Declare vector c (P, u) (from the point P to a curve C ):
and a unit vector w (P, u) :
, which gives a continuous function W (P): C → S1 , mapping the point C (u) of the curve C to the point w (P, u) on the unit circle S 1 = {(x, y) | x2 + y2 = 1} . This mapping can be represented in polar coordinates
,where theta (u) - a positive counterclockwise rotation in radians.
Then the number of revolutions wn (P, C) of the continuous curve C around the point P is equal to the integer number of times when W (P) rotates the curve C around the unit circle S 1 . This corresponds to the homotopy class S 1and can be calculated through the integral:
When the curve C is a polygon with vertices V 0 , V 1 , ..., V n = V 0 , 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:
(1) The figure shows how you can graphically represent the sign sum of the angles.
Obviously, formula (1) is not very effective because it uses the trigonometric function of the arccosine, which is computationally demanding. It is necessary to replace this formula with a more effective one.
Optimization of the method of accounting for revolutions
Take any point Q on the unit circle. Then, as the curve W (P) wraps around S 1 , it passes the point Q a certain number of times. If we assume (+1) when the curve passes Q counterclockwise, and (-1) when the curve passes clockwise, the accumulated sum will be the total number of times how many W (P) wraps around S 1 and is equal to wn (P , C) - the number of turns of a continuous curve C around the point P . Further, if we take an infinite ray R with origin at point Pand extending in the direction of the vector Q , the intersection of beam R , and curve C corresponds to the point where W (P) extends Q . To develop a mathematical apparatus, it is necessary to distinguish between positive and negative transitions, where C intersects R in the 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 origin at point P, just checking if the end of the rib is above or below the beam. If an edge crosses a direct ray from bottom to top, then the intersection is positive (+1), but if it crosses an edge from top to bottom, then the intersection is negative (-1). The sum of the intersection marks gives the number of revolutions wn (P, C) .
Moreover, it is possible to avoid calculating the actual point of intersection of the edge and beam. To do this, it is enough to determine which side the edge intersects with the beam. If the ascending edge intersects the ray to the right of the point P , then P is to the left of the edge, because the triangle V i V i + 1 P is oriented counterclockwise. If the descending edge crosses the ray on the left, then the point Pis 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 revolutions requires a complete enumeration 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 operations of multiplication at each iteration of the loop of enumeration of vertices.
UPD:
Implementation
Probably in vain I did not immediately attach the source code, so I am correcting myself.
Source
public class Polygon {
// Массивы для хранения координат вершин многоугольника
private ArrayList xPoints = new ArrayList();
private ArrayList yPoints = new ArrayList();
// Опустим все get и set методы, как само собой разумеющееся
// Метод, который высчитывает число оборотов кривой
public boolean сontains(float _pointX, float _pointY) {
float windingNumber = 0; // Счётчик числа оборотов
float startX = 0;
float startY = 0;
float endX = 0;
float endY = 0;
int count = xPoints.size();
for (int i = 1; i <= count; i++) {
startX = xPoints.get(i - 1);
startY = yPoints.get(i - 1);
if (i == count) {
endX = xPoints.get(0);
endY = yPoints.get(0);
} else {
endX = xPoints.get(i);
endY = yPoints.get(i);
}
if (startY <= _pointY) {
if (endY > _pointY) {
// Восходящая грань
if (isLeft(startX, startY, endX, endY, _pointX, _pointY) > 0) {
// Точка P слева от грани многоугольника
++windingNumber;
}
}
} else {
if (endY <= _pointY) {
// Нисходящая грань
if (isLeft(startX, startY, endX, endY, _pointX, _pointY) < 0) {
// Точка P справа от грани
--windingNumber;
}
}
}
}
return (windingNumber != 0);
}
// start* и end* - координаты точек, представляющих грань. point* - координаты точки P, которую проверяем
private float isLeft(float _startX, float _startY, float _endX, float _endY, float _pointX, float _pointY) {
return ((_endX - _startX) * (_pointY - _startY) - (_pointX - _startX) * (_endY - _startY));
}
} Primary Source: GeometryAlgorithms.com