The method implemented here is reproduced in https://blog.csdn.net/trj14/article/details/43190653 and https://blog.csdn.net/WilliamSun0122/article/details/77994526
It was implemented and adjusted according to Qt’s rules.
There are four implementation methods below. The specific explanation of each method is explained in the reposted blog, and will not be repeated here.
Here we only talk about the specific implementation of the code and the time complexity of each method.
The first method is highly recommended. The other three methods have more or less problems for some special graphics.
Method 1: Ray method
Time complexity: O(n).
Scope of application: Any polygon.
Advantages: There is no need to consider accuracy errors and the order in which polygon points are given.
Algorithm idea: take the measured point Q as the endpoint, draw a ray in any direction (generally draw a ray horizontally to the right), and count the number of intersections between the ray and the polygon. If it is an odd number, Q is inside the polygon; if it is an even number, Q is outside the polygon. There will be some special situations when counting, as shown in the figure
//Judge point P within the polygon - ray method
bool Widget::InsidePolygon( QVector<QPointF> polygon,QPointF pt )
{<!-- -->
int i,j;
bool inside,redo;
int N = polygon.size();
redo = true;
for (i = 0;i < N; + + i)
{<!-- -->
// Is it on the vertex?
if (polygon[i].x() == pt.x() & amp; & amp; polygon[i].y() == pt.y())
{<!-- -->
redo = false;
inside = true;
break;
}
}
while (redo)
{<!-- -->
redo = false;
inside = false;
for (i = 0,j = N - 1;i < N;j = i + + )
{<!-- -->
if ( (polygon[i].y() < pt.y() & amp; & amp; pt.y() < polygon[j].y()) ||
(polygon[j].y() < pt.y() & amp; & amp; pt.y() < polygon[i].y()) )
{<!-- -->
if (pt.x() <= polygon[i].x() || pt.x() <= polygon[j].x())
{<!-- -->
double _x = (pt.y()-polygon[i].y())*(polygon[j].x()-polygon[i].x())/(polygon[j].y()- polygon[i].y()) + polygon[i].x();
if (pt.x() < _x) // on the left side of the line
inside = !inside;
else if (pt.x() == _x) // online
{<!-- -->
inside = true;
break;
}
}
}
else if (pt.y() == polygon[i].y())
{<!-- -->
if (pt.x() < polygon[i].x()) // The intersection is at the vertex
{<!-- -->
if (polygon[i].y() > polygon[j].y())
pt.setY(pt.y() - 1);
else
pt.setY(pt.y() + 1);
redo = true;
break;
}
}
else if ( polygon[i].y() == polygon[j].y() & amp; & pt.y() == polygon[i].y() & amp; & amp;
((polygon[i].x() < pt.x() & amp; & amp; pt.x() < polygon[j].x()) ||
(polygon[j].x() < pt.x() & amp; & amp; pt.x() < polygon[i].x())) )// on the horizontal boundary line
{<!-- -->
inside = true;
break;
}
}
}
return inside;
}
Method 2: Area sum discrimination method
Time complexity: greater than O(n).
Scope of application: All convex edge shapes, some concave deformations.
Advantages: The algorithm is simple.
Disadvantages: Accuracy requirements, emphasis on the direction given by the polygon points (counterclockwise).
Algorithm idea: If a point is inside a polygon or on an edge, then the sum of the area of the triangle formed by the point and all sides of the polygon is equal to the area of the polygon. The area of a polygon can be calculated using the cross product, that is, a vector is formed by connecting the origin of the coordinates and each vertex. The sum of 0.5 of the cross products of all vectors is the area of the polygon. However, there will be a certain error in calculating the area, and the error range of the accuracy needs to be set.
//Area Sum Discriminant Method
bool InsidePolygon3( QVector<QPointF> polygon,QPointF pt )
{<!-- -->
int i,j;
bool inside = false;
double polygon_area = 0;
double trigon_area = 0;
int N = polygon.size();
for (i = 0,j = N - 1;i < N;j = i + + )
{<!-- -->
polygon_area + = polygon[i].x() * polygon[j].y() - polygon[j].x() * polygon[i].y();
trigon_area + = abs(
pt.x() * polygon[i].y() -
pt.x() * polygon[j].y() -
polygon[i].x() * pt.y() +
polygon[i].x() * polygon[j].y() +
polygon[j].x() * pt.y() -
polygon[j].x() * polygon[i].y()
);
}
trigon_area *= 0.5;
polygon_area = abs(polygon_area * 0.5);
if ( fabs(trigon_area - polygon_area) < 1e-7 )
inside = true;
return inside;
}
Method Three: Point and Line Discrimination Method
Time complexity: O(n).
Scope of application: All convex edge shapes, some concave deformations.
Algorithm idea: For a polygon (forward, that is, counterclockwise), if a point is to the left of all its directed edges, then this point must be inside the polygon. The cross product can be used to determine the relationship between a point and a given edge, that is, whether the point is to the left, right or on the edge.
//Point and line discrimination method
bool InsidePolygon4( QVector<QPointF> polygon,QPointF p )
{<!-- -->
int i,j;
bool inside = false;
int count1 = 0;
int count2 = 0;
int N = polygon.size();
for (i = 0,j = N - 1;i < N;j = i + + )
{<!-- -->
double value = (p.x() - polygon[j].x()) * (polygon[i].y() - polygon[j].y()) - (p.y() - polygon[j].y( )) * (polygon[i].x() - polygon[j].x());
if (value > 0)
+ + count1;
else if (value < 0)
+ + count2;
}
if (0 == count1 ||
0 == count2)
{<!-- -->
inside = true;
}
return inside;
}
Method 4: Angle and Discrimination Method
Time complexity: O(n).
Scope of application: All convex edge shapes, some concave deformations.
Advantages: Does not emphasize the order given by polygon points.
Disadvantages: This algorithm has high accuracy requirements (can cause large accuracy errors).
Algorithm idea: If the sum of the angles formed by connecting the measured point and all vertices of the polygon is equal within the accuracy range, the point is within the polygon, otherwise it is outside the polygon.
//Do not judge vertices as needed
bool IsPointInLine( QPointF & amp;pt,QPointF & amp;pt1,QPointF & amp;pt2 )
{<!-- -->
bool inside = false;
if (pt.y() == pt1.y() & amp; & amp;
pt1.y() == pt2.y() & amp; & amp;
((pt1.x() < pt.x() & amp; & amp; pt.x() < pt2.x()) ||
(pt2.x() < pt.x() & amp; & amp; pt.x() < pt1.x())) )
{<!-- -->
inside = true;
}
else if (pt.x() == pt1.x() & amp; & amp;
pt1.x() == pt2.x() & amp; & amp;
((pt1.y() < pt.y() & amp; & amp; pt.y() < pt2.y()) ||
(pt2.y() < pt.y() & amp; & amp; pt.y() < pt1.y())) )
{<!-- -->
inside = true;
}
else if ( ((pt1.y() < pt.y() & amp; & amp; pt.y() < pt2.y()) ||
(pt2.y() < pt.y() & amp; & amp; pt.y() < pt1.y())) & amp; & amp;
((pt1.x() < pt.x() & amp; & amp; pt.x() < pt2.x()) ||
(pt2.x() < pt.x() & amp; & amp; pt.x() < pt1.x())) )
{<!-- -->
if (0 == (pt.y()-pt1.y())/(pt2.y()-pt1.y())-(pt.x() - pt1.x()) / (pt2. x()-pt1.x()))
{<!-- -->
inside = true;
}
}
return inside;
}
//Angle and discrimination method
bool InsidePolygon2( QVector<QPointF> polygon,QPointF p)
{<!-- -->
int i,j;
double angle = 0;
bool inside = false;
int N = polygon.size();
for (i = 0,j = N - 1;i < N;j = i + + )
{<!-- -->
if (polygon[i].x() == p.x() & amp; & amp; // Whether it is on the vertex
polygon[i].y() == p.y())
{<!-- -->
inside = true;
break;
}
else if (IsPointInLine(p,polygon[i],polygon[j])) // Whether it is on the boundary line
{<!-- -->
inside = true;
break;
}
double x1,y1,x2,y2;
x1 = polygon[i].x() - p.x();
y1 = polygon[i].y() - p.y();
x2 = polygon[j].x() - p.x();
y2 = polygon[j].y() - p.y();
double radian = atan2(y1,x1) - atan2(y2,x2);
radian = abs(radian);
if (radian > M_PI) radian = 2* M_PI - radian;
angle + = radian; // Calculate the sum of angles
}
if ( fabs(6.28318530717958647692 - angle) < 1e-7 )
inside = true;
return inside;
}