更新时间:2022-12-17 10:39:51
测试点是否在多边形内的一种简单方法是计算多边形的边缘与源于测试点的光线之间的相交数.因为可以随心所欲选择光线,所以通常选择平行于X轴很方便.该代码看起来像这样:
A simple way to test whether a point is inside a polygon is to count the number of intersections between the edges of the polygon and a ray originating from the test point. Because you can pick the ray to be whatever you want, it's usually convenient to pick it to be parallel to the X axis. The code for that looks something like this:
public static bool IsInPolygon( this Point testPoint, IList<Point> vertices )
{
if( vertices.Count < 3 ) return false;
bool isInPolygon = false;
var lastVertex = vertices[vertices.Count - 1];
foreach( var vertex in vertices )
{
if( testPoint.Y.IsBetween( lastVertex.Y, vertex.Y ) )
{
double t = ( testPoint.Y - lastVertex.Y ) / ( vertex.Y - lastVertex.Y );
double x = t * ( vertex.X - lastVertex.X ) + lastVertex.X;
if( x >= testPoint.X ) isInPolygon = !isInPolygon;
}
else
{
if( testPoint.Y == lastVertex.Y && testPoint.X < lastVertex.X && vertex.Y > testPoint.Y ) isInPolygon = !isInPolygon;
if( testPoint.Y == vertex.Y && testPoint.X < vertex.X && lastVertex.Y > testPoint.Y ) isInPolygon = !isInPolygon;
}
lastVertex = vertex;
}
return isInPolygon;
}
public static bool IsBetween( this double x, double a, double b )
{
return ( x - a ) * ( x - b ) < 0;
}
其中有一些额外的代码可以处理一些实际的极端情况(如果测试射线直接撞击顶点,则需要进行特殊处理).
There's some extra code stuffed in there to deal with some literal corner cases (if the test ray hits a vertex directly, that needs some special treatment).