点在多边形内吗？

Question

我需要编写一个函数来计算一个点是否在多边形内 (true/false)。多边形总是包含 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 是矩阵括号中的最后 2 个数字。也不知道文本的那个点是文本的中心还是左下角（假设是这个）。

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

Answer 1

给定 4 个定义多边形顶点的点，顺时针或逆时针。如果多边形是凹的，则通过获取每对线的叉积来确定点是否在第一个锻炼内部。

多边形是 p1,p2,p3,p4 各有一个 x 和 y。

要得到叉积得到 3 个点，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}

做

如果十字对所有顶点都是相同的符号（注意0既是负数又是正数）那么多边形是凹的。

如果不完全相同，只有一个可以不同。您需要通过将不同的点与相反的点连接起来，将多边形拆分为两个 3 边形。

例如 p2,p3,p4 的交叉是负的，其余的是正的那么你有两个多边形 p1,p2,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}

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

Answer 2

测试点是否在多边形内部的一种简单方法是计算多边形的边与来自测试点的射线之间的交点数。因为您可以随意选择光线，所以通常选择平行于 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;
}

其中填充了一些额外的代码来处理一些实际的极端情况（如果测试射线直接击中顶点，则需要一些特殊处理）。

Answer 3

这样解决的：

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

点在多边形内吗？

Is point inside polygon?

c#

math

svg

computational-geometry