欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

判断点是否在多边形的范围内

程序员文章站 2022-04-01 08:53:55
...
public class GeometryUtils {
	public final static double  EPSILON=0.00001;
	
	
	public static double getEpsilon(double maxx, double maxy,double minx, double miny, double epsilon){
		if((maxy-miny+maxx-minx)==0)return epsilon;
		return Math.abs(epsilon/(maxy-miny+maxx-minx));
	}

	// / <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];
			}
		}
		
		double epsilon = getEpsilon(maxx, maxy, minx, miny, EPSILON);
		
		if (point != null) {

			// 首先判断是否在面的外框范围内
			if (point[0] < minx || point[0] > maxx || point[1] < miny
					|| point[1] > maxy) {
				System.out.println("直接out");
				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 ((lt(point1[0] , point[0],epsilon) &&
							(eq(point2[0],point[0],epsilon) || gt(point2[0] , point[0],epsilon) ) )
							|| (lt(point2[0] , point[0],epsilon) &&
									(eq(point1[0],point[0],epsilon)) || gt(point1[0], point[0],epsilon)  )) {
						tempValue = point1[1] + (point[0] - point1[0])
								/ (point2[0] - point1[0])
								* (point2[1] - point1[1]);
						if (tempValue < point[1]) {
							count++;
						} else if (eq(tempValue ,point[1],epsilon)) {
							count = -1;
							break;
						}
					}
					j = i;
				}
			}
		}
		if (count == -1) {
			result = 0;// 点在线段上
		} else {
			tempI = count % 2;
			if (tempI == 0)// 为偶数
			{
				result = -1;
			} else {
				result = 1;
			}
		}
		return result;
	}
	
	public static boolean eq(double a,double b, double epsilon){		
		return Math.abs(a-b)<epsilon;
	}
	
	public static boolean gt(double a,double b, double epsilon){		
		return a-b>=epsilon;
	}
	public static boolean lt(double a,double b, double epsilon){		
		return b-a>=epsilon;
	}
	
	public static void main(String[] args){
		int result =  polygonIsContainPoint(new double[]{106.63,35.85}, 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);
       
       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);
       
   	  result =  polygonIsContainPoint(new double[]{10,10}, 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);

	}

}




原文链接:http://peizhiinfo.iteye.com/blog/1237481