是多边形内的点

本文关键字：多边形 | 更新日期: 2023-09-27 18:11:31

我需要写一个函数，将计算如果一个点是在多边形内(真/假)。多边形总是包含4个点。我正在阅读多边形和点从SVG文件

<g id="polygons">
    <g id="LWPOLYLINE_183_">
        <polyline class="st10" points="37.067,24.692 36.031,23.795 35.079,24.894 36.11,25.786 37.067,24.692   " />
    </g>
    <g id="LWPOLYLINE_184_">
        <polyline class="st10" points="35.729,23.8 35.413,23.516 34.625,24.39 34.945,24.67 35.729,23.8   " />
    </g>
    <g id="LWPOLYLINE_185_">
        <polyline class="st10" points="34.483,24.368 33.975,23.925 34.743,23.047 35.209,23.454 34.483,24.368   " />
    </g>
    <g id="LWPOLYLINE_227_">
        <polyline class="st10" points="36.593,22.064 36.009,21.563 35.165,22.57 35.736,23.061 36.593,22.064   " />
    </g>
</g>
<g id="numbers">
    <g id="TEXT_1647_">
        <text transform="matrix(0.7 0 0 1 34.5876 23.8689)" class="st12 st2 st13">169</text>
    </g>
    <g id="TEXT_1646_">
        <text transform="matrix(0.7 0 0 1 35.1049 24.1273)" class="st12 st2 st13">168</text>
    </g>
    <g id="TEXT_1645_">
        <text transform="matrix(0.7 0 0 1 35.924 24.7302)" class="st12 st2 st13">167</text>
    </g>
    <g id="TEXT_1643_">
        <text transform="matrix(0.7 0 0 1 36.0102 22.4477)" class="st12 st2 st13">174</text>
    </g>
</g>

因此，对于折线，它将是前4组坐标，对于文本X和Y是矩阵括号中的最后两个数字。也不知道文本的那个点是文本的中心还是左下角(假设是这个)。

到目前为止，我得到了列表中所有点和多边形的坐标，所以我用这种方式进行交叉检查。

是多边形内的点

测试一个点是否在多边形内的一个简单方法是计算多边形边缘和从测试点发出的射线之间的交点个数。因为你可以选择任意的射线，通常选择与X轴平行的射线是很方便的。它的代码看起来像这样:

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;
}

这里有一些额外的代码来处理一些文字角情况(如果测试射线直接击中顶点，则需要一些特殊处理)。

给定4个点，按顺时针或逆时针顺序定义一个多边形的顶点。要确定一个点是否在内，首先通过得到每对直线的叉乘来确定多边形是否凹。

多边形是p1,p2,p3,p4，每个都有x和y。

求外积取三个点p1 p2 p3其中p2是两条直线相交的顶点

cross = (p2.x-p1.x) * (p3.y-p2.y) - (p2.y-p1.y) * (p3.x-p2.x);

{p1,p2,p3}, {p2,p3,p4}, {p3,p4,p1}, {p4,p1,p2}的Do

如果十字对所有的顶点都是相同的符号(注意0既是负的也是正的)，那么这个多边形是凹的。

如果不完全相同，只能有一个不同。你需要把这个多边形分成两个3边多边形，把不同的点和相反的点连接起来。

Eg是p2 p3 p4的叉乘，是负的其余部分是正的那么你就得到了两个多边形p1 p2 p3 p3 p3 p3 p4 p1

现在你有一个或两个多边形。

计算你要测试的点与每条线的交叉

cross = (p2.x-p1.x) * (testPoint.y-p1.y) - (p2.y-p1.y) * (testPoint.x-p1.x);

对{p1,p2}, {p2,p3}, {p3,p4}, {p4,p1}每一行执行

如果所有线段的符号相同，则该点在多边形内。如果你有两个多边形，你只需要满足一个多边形的相同符号条件

是这样解决的:

public static bool IsPointInPolygon4(PointF[] polygon, PointF testPoint)
    {
        bool result = false;
        int j = polygon.Count() - 1;
        for (int i = 0; i < polygon.Count(); i++)
        {
            if (polygon[i].Y < testPoint.Y && polygon[j].Y >= testPoint.Y || polygon[j].Y < testPoint.Y && polygon[i].Y >= testPoint.Y)
            {
                if (polygon[i].X + (testPoint.Y - polygon[i].Y) / (polygon[j].Y - polygon[i].Y) * (polygon[j].X - polygon[i].X) < testPoint.X)
                {
                    result = !result;
                }
            }
            j = i;
        }
        return result;
    }
相关文章：