点在多边形内吗? [英] Is point inside polygon?

问题描述

我需要编写一个函数来计算点是否在多边形内(真/假).

I need to write a function that will calculate if a point is inside polygon (true/false).

多边形始终包含4个点.我正在从SVG文件中读取多边形和点

Polygon always contains 4 points. I'm reading polygons and points from SVG file

<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个数字.还不知道文本的那个点是文本的中心还是左下角(假设就是这个).

So for polyline it would be the first 4 sets of coordinates and for text X and Y are last 2 numbers in matrix brackets. Also don't know if that point for text is the center of text or bottom left corner (suppose it's this).

到目前为止，我在列表中获得了点和多边形的所有坐标，因此我要进行交叉检查.

So far I got all coordinates for points and polygons in lists so I'm cross checking that way.

推荐答案

测试点是否在多边形内的一种简单方法是计算多边形的边缘与源于测试点的光线之间的相交数.因为可以随心所欲选择光线，所以通常选择平行于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).

这篇关于点在多边形内吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！