和大家分享一个判断点是否在多边形范围内的算法

判断点与多边形的关系（在平面上），不能用简单的向量叉乘来判断，特别是在有凹边形的情况下，下面和大家分享一个判断点是否在多边形范围内的简单算法。在进行判断前，建议先进行范围大致判断，在许多情况下，应该说大部分情况下，我们进行判断的对象在空间上相差可能很远，如果一开始就直接用算法去计算，这样会浪费大量的计算时间和空间，所以在使用具体算法前，先进行一个大致范围的判断。先判断它是否有可能在这个区域，如果不可能就直接out，如果有可能，再用算法去计算具体是否在范围内。和后面的算法相比，前面的比较过程所消耗的时间可以说是微不足道，但是用这个微不足道的时间却可以极大提高算法的运行效率。废话不多说了，直接上算法！用静态方法写的，可以直接调用，该算法也适合凹边形的情况。

/// <summary>
/// <para>判断点是否在多边形的范围内</para>
/// <para>返回值：值为1表示点在多边形范围内；</para>
/// <para>值为0表示点在多边形边上；</para>
/// <para>值为-1表示点不在多边形范围内。</para>
/// </summary>
/// <param name="point">点坐标，长度为2</param>
/// <param name="polyline">多边形节点坐标，长度为2*n，其中n应大于或等于3，即至少为三角形</param>
/// <returns>
/// <para>返回值：值为1表示点在多边形范围内；</para>
/// <para>值为0表示点在多边形边上；</para>
/// <para>值为-1表示点不在多边形范围内。</para>
/// </returns>
public static int PolygonIsContainPoint(double[] point,double[] polyline)
{
int result = -1, count = 0, pointcount = 0, tempI;
double maxx = 0, minx = 0, maxy = 0, miny = 0;
if (polyline != null)
{
int i;
pointcount = polyline.Length / 2;
maxx = minx = polyline[0];
maxy = miny = polyline[1];
for (i = 0; i < pointcount; i++)
{
tempI = i + i;
if (maxx < polyline[tempI])
maxx = polyline[tempI];
if (minx > polyline[tempI])
minx = polyline[tempI];
if (maxy < polyline[tempI + 1])
maxy = polyline[tempI + 1];
if (miny > polyline[tempI + 1])
miny = polyline[tempI + 1];
}
}
if (point != null)
{

//首先判断是否在面的外框范围内
if (point[0] < minx || point[0] > maxx
|| point[1] < miny || point[1] > maxy)
{
return result;
}
else
{
int i, j;
j = pointcount - 1;
double[] point1, point2;
double tempValue;
for (i = 0; i < pointcount; i++)
{
point1 = new double[2];
point2 = new double[2];
tempI = i + i;
point1[0] = polyline[tempI];
point1[1] = polyline[tempI + 1];
tempI = j + j;
point2[0] = polyline[tempI];
point2[1] = polyline[tempI + 1];
if ((point1[0] < point[0] && point2[0] >= point[0])
|| (point2[0] < point[0] && point1[0] >= point[0]))
{
tempValue=point1[1] + (point[0] - point1[0]) / (point2[0] - point1[0]) * (point2[1] - point1[1]);
if (tempValue < point[1])
{
count++;
}
else if (tempValue == point[1])
{
count = -1;
break;
}
}
j = i;
}
}
}
if (count == -1)
{
result = 0;//点在线段上
}
else
{
tempI = count % 2;
if (tempI == 0)//为偶数
{
result = -1;
}
else
{
result = 1;
}
}
return result;
}
}

评论

2 楼 wangguxian 2013-06-16  

它的起点是没有算在里面的，所以第一个点的返回值是-1，其他的都是0
首先，感谢楼主和大家分享，我现在急着用，所以就测试下直接用你的了。
其次，以后有时间我要尝试自己写一下。

1 楼 yx3019 2012-03-20  

怎么用的啊，好像不太对。

int result =  PolygonIsContainPoint(new double[]{106.61502,35.84901}, new double[]{106.61502,35.84901,
                    106.61605,35.85133,
                    106.62112,35.85416,
                    106.62635,35.85305,
                    106.63725,35.85219,
                    106.64867,35.84953,
                    106.65021,35.84627,
                    106.65202,35.84052,
                    106.64472,35.84352,
                    106.63991,35.84781,
                    106.63399,35.84798,
                    106.62807,35.84549,
                    106.62258,35.84704,
                    106.61674,35.84841});
           System.out.println(result);

取的坐标点 和 后面的一样，结果 返回-1