判断一个点是否在某个区域内(多边形)

 判断一个点是否在某个区域内(多边形)

背景：
比如滴滴会根据乘客所在的不同区域，给出不同的价格。市区堵一点，那么价格也高点。获取服务范围只规定在某个范围内

原理：
求解从该点向右发出的水平线射线与多边形各边的交点，当交点数为奇数，则在内部。
不过要注意几种特殊情况：1、点在边或者顶点上;2、点在边的延长线上;3、点出发的水平射线与多边形相交在顶点上

源代码：
Point类-多边形顶点的封装类如坐标(166.3,18.4)
Line类-多边形对应的各个边的封装类，如{(166.3,18.4), (166.9,19)}
MapUtil类-地图公共处理类

package com.qj.book.util;

/**
* Created by xsm48563 on 2017/10/31.
* 点
*/
public class Point {

/**
* 水平方向值/经度
*/
public Double X;
/**
* 垂直方向值/纬度
*/
public Double Y;

Point(Double x, Double y) {

x = x == null ? 0:x;
y = y == null ? 0:y;
this.X = x;
this.Y = y;
}

public boolean equals(Object obj) {

// 如果为同一对象的不同引用,则相同
if (this == obj) {
return true;
}
// 如果传入的对象为空,则返回false
if (obj == null) {
return false;
}
if (obj instanceof Point) {
Point point = (Point) obj;
if (point.X.equals(this.X) && point.Y.equals(this.Y)) {
return true;
} else {
return false;
}
} else {
return false;
}
}

public static void main(String[] args) {

Point A = new Point(1d, null);
Point B = new Point(null, 3d);
System.out.println(A.equals(B));
}
}

package com.qj.book.util;

import java.math.BigDecimal;

/**
* Created by xsm48563 on 2017/10/31.
* 线
*/
public class Line {

/**
* 端点1
*/
public Point POINTA;

/**
* 端点2
*/
public Point POINTB;

Line(Point pointA, Point pointB) {

this.POINTA = pointA;
this.POINTB = pointB;
}

/**
* 判断当前线段是否包含给定的点

* 即给定的点是否在当前边上
* @param point
* @return
*/
public boolean isContainsPoint(Point point) {

boolean result = false;
//判断给定点point与端点1构成线段的斜率是否和当前线段的斜率相同
//给定点point与端点1构成线段的斜率k1
Double k1 = null;
if (point.X.equals(this.POINTA.X)) {
k1 = Double.NEGATIVE_INFINITY;
} else {
k1 = div(sub(point.Y, this.POINTA.Y), sub(point.X, this.POINTA.X));
}
//当前线段的斜率k2
Double k2 = null;
if (this.POINTB.X.equals(this.POINTA.X)) {
k2 = Double.NEGATIVE_INFINITY;
} else {
k2 = div(sub(this.POINTB.Y, this.POINTA.Y), sub(this.POINTB.X, this.POINTA.X));
}
if (k1 != null && k2 != null) {
if (k1.equals(k2)) {
//若斜率相同，继续判断给定点point的x是否在pointA.x和pointB.x之间,若在 则说明该点在当前边上
if (sub(point.X, this.POINTA.X) * sub(point.X, this.POINTB.X) < 0) {
result = true;
}
}
}
return result;
}

//叉积
double mult(Point a, Point b, Point c) {
return (a.X-c.X)*(b.Y-c.Y)-(b.X-c.X)*(a.Y-c.Y);
}

/**
* 给定线段是否与当前线段相交

* 相交返回true, 不相交返回false
* @param line
* @return
*/
public boolean
isIntersect(Line line) {

Point aa = this.POINTA;
Point bb = this.POINTB;
Point cc = line.POINTA;
Point dd = line.POINTB;
if (Math.max(aa.X, bb.X) < Math.min(cc.X, dd.X)) {
return false;
}
if (Math.max(aa.Y, bb.Y) < Math.min(cc.Y, dd.Y)) {
return false;
}
if (Math.max(cc.X, dd.X) < Math.min(aa.X, bb.X)) {
return false;
}
if (Math.max(cc.Y, dd.Y) < Math.min(aa.Y, bb.Y)) {
return false;
}
if (mult(cc, bb, aa) * mult(bb, dd, aa) < 0 ) {
return false;
}
if ( mult(aa, dd, cc) * mult(dd, bb, cc) < 0 ) {
return false;
}
return true;
}

/**
* 提供精确的加法运算。
* @param v1 被加数
* @param v2 加数
* @return 两个参数的和
*/
public static double add(double v1,double v2){
BigDecimal b1 = new BigDecimal(Double.toString(v1));
BigDecimal b2 = new BigDecimal(Double.toString(v2));
return b1.add(b2).doubleValue();
}

/**
* 提供精确的减法运算。
* @param v1 被减数
* @param v2 减数
* @return 两个参数的差
*/
public static double sub(double v1,double v2){
BigDecimal b1 = new BigDecimal(Double.toString(v1));
BigDecimal b2 = new BigDecimal(Double.toString(v2));
return b1.subtract(b2).doubleValue();
}

/**
* 提供精确的乘法运算。
* @param v1 被乘数
* @param v2 乘数
* @return 两个参数的积
*/
public static double mul(double v1,double v2){
BigDecimal b1 = new BigDecimal(Double.toString(v1));
BigDecimal b2 = new BigDecimal(Double.toString(v2));
return b1.multiply(b2).doubleValue();
}

private static final int DEF_DIV_SCALE = 10;

/**
* 提供（相对）精确的除法运算，当发生除不尽的情况时，精确到
* 小数点以后10位，以后的数字四舍五入。
* @param v1 被除数
* @param v2 除数
* @return 两个参数的商
*/
public static double div(double v1,double v2){
return div(v1,v2,DEF_DIV_SCALE);
}

/**
* 提供（相对）精确的除法运算。当发生除不尽的情况时，由scale参数指
* 定精度，以后的数字四舍五入。
* @param v1 被除数
* @param v2 除数
* @param scale 表示表示需要精确到小数点以后几位。
* @return 两个参数的商
*/
public static double div(double v1,double v2,int scale){
if(scale<0){
throw new IllegalArgumentException(
“The scale must be a positive integer or zero”);
}
BigDecimal b1 = new BigDecimal(Double.toString(v1));
BigDecimal b2 = new BigDecimal(Double.toString(v2));
return b1.divide(b2,scale,BigDecimal.ROUND_HALF_UP).doubleValue();
}
}

package com.qj.book.util;

import com.alibaba.fastjson.JSONArray;
import com.alibaba.fastjson.JSONObject;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;

/**
* Created by xsm48563 on 2017/10/31.
* 图形专用类
*/
public class MapUtil {


/**
* 给定点和多边形，判断给定的点是否在多边形内
* @param point
* @param points
* @return
*/
public static boolean isPointInPolygon(Point point, Listpoints) {

boolean result = false;
int intersectCount = 0;
// 判断依据：求解从该点向右发出的水平线射线与多边形各边的交点，当交点数为奇数，则在内部
//不过要注意几种特殊情况：1、点在边或者顶点上;2、点在边的延长线上;3、点出发的水平射线与多边形相交在顶点上
/**
* 具体步骤如下：
* 循环遍历各个线段：
* 1、判断点是否在当前边上(斜率相同,且该点的x值在两个端口的x值之间),若是则返回true
* 2、否则判断由该点发出的水平射线是否与当前边相交,若不相交则continue
* 3、若相交,则判断是否相交在顶点上(边的端点是否在给定点的水平右侧).若不在,则认为此次相交为穿越,交点数+1 并continue
* 4、若交在顶点上,则判断上一条边的另外一个端点与当前边的另外一个端点是否分布在水平射线的两侧.若是则认为此次相交为穿越,交点数+1.
*/
for (int i = 0; i < points.size(); i++) {
Point pointA = points.get(i);
Point pointB = null;
Point pointPre = null;
//若当前是第一个点,则上一点则是list里面的最后一个点
if (i == 0) {
pointPre = points.get(points.size() – 1);
} else {
pointPre = points.get(i – 1);
}
//若已经循环到最后一个点,则与之连接的是第一个点
if (i == (points.size() – 1)) {
pointB = points.get(0);
} else {
pointB = points.get(i + 1);
}
Line line = new Line(pointA, pointB);
//1、判断点是否在当前边上(斜率相同,且该点的x值在两个端口的x值之间),若是则返回true
boolean isAtLine = line.isContainsPoint(point);
if (isAtLine) {
return true;
} else {
//2、若不在边上,判断由该点发出的水平射线是否与当前边相交,若不相交则continue
//设置该射线的另外一个端点的x值=999,保证边的x永远不超过
Point radialPoint = new Point(999d, point.Y);
Line radial = new Line(point, radialPoint);
boolean isIntersect = radial.isIntersect(line);
if (!isIntersect) {
continue;
} else {
//3、若相交,则判断是否相交在顶点上(边的端点是否在给定点的水平右侧).若不在,则认为此次相交为穿越,交点数+1 并continue
if (!( (pointA.X > point.X) && (pointA.Y.equals(point.Y))
|| (pointB.X > point.X) && (pointB.Y.equals(point.Y)) )) {
intersectCount++;
continue;
} else {
//4、若交在顶点上,则判断上一条边的另外一个端点与当前边的另外一个端点是否分布在水平射线的两侧.若是则认为此次相交为穿越,交点数+1
if ((pointPre.Y – point.Y) * (pointB.Y – point.Y) < 0) {
intersectCount++;
}
}
}
}
}
result = intersectCount % 2 == 1;
return result;
}

public static void main(String[] args) {

Point point11 = new Point(1d, 2d);
Point point22 = new Point(2d, 4d);
Point point33 = new Point(3d, 4d);
Point point44 = new Point(5d, 2d);
Point point55 = new Point(5d, 1d);
Point point66 = new Point(3d, 0d);
List points = new ArrayList<>();
points.add(point11);
points.add(point22);
points.add(point33);
points.add(point44);
points.add(point55);
points.add(point66);
Point test = new Point(2d, 3d);
System.out.println(isPointInPolygon(test, points));
}

}

在做LBS，POI相关项目时，经常需要判断一个点是否在某个区域中的问题。在实际场景中，这个区域肯定是没有任何规律的不规则形状。针对这种场景，搜索了几种对应的解法。重点是，最后给大家奉上能工作的源码！有需要的同学们千万不能错过。

1.射线法，PNPoly算法

2.多边形面积算法

3.可用的解决方案

import java.awt.geom.GeneralPath;
import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.List;

/**
 * Created by wanglei on 17-2-14.
 */
public class MapTools {

    public static List genPointList() {
        List list = new ArrayList();
        Point2D.Double p1 = new Point2D.Double(0.0,0.0);
        Point2D.Double p2 = new Point2D.Double(0.0,0.5);
        Point2D.Double p3 = new Point2D.Double(0.0,1.0);
        Point2D.Double p4 = new Point2D.Double(1.0,0.5);
        Point2D.Double p5 = new Point2D.Double(1.0,1.0);
        Point2D.Double p6 = new Point2D.Double(1.0,0.5);
        Point2D.Double p7 = new Point2D.Double(1.0,0.0);
        Point2D.Double p8 = new Point2D.Double(0.5,0.0);

        Point2D.Double[] points = {p1,p2,p3,p4,p5,p6,p7,p8};
        for (int i = 0; i < points.length; i++) {
            list.add(points[i]);
        }

        return list;
    }

    public static boolean checkWithPath(Point2D.Double point, List<Point2D.Double> polygon) {
        GeneralPath p = new GeneralPath();
        Point2D.Double first = polygon.get(0);
        p.moveTo(first.x,first.y);
        for(Point2D.Double d: polygon) {
            p.lineTo(d.x,d.y);
        }
        p.lineTo(first.x,first.y);
        p.closePath();
        return p.contains(point);
    }

    public static void main(String[] args) {
        List list = genPointList();
        Point2D.Double p1 = new Point2D.Double(1.5,1.5);
        Point2D.Double p2 = new Point2D.Double(0.2,0.3);
        Point2D.Double p3 = new Point2D.Double(1.5,0.1);
        Point2D.Double p4 = new Point2D.Double(0.8,0.0);
        Point2D.Double p5 = new Point2D.Double(0.08,0.01);
        List<Point2D.Double> testList = new ArrayList();
        testList.add(p1);
        testList.add(p2);
        testList.add(p3);
        testList.add(p4);
        testList.add(p5);
        for(Point2D.Double each:testList) {
            boolean flag = checkWithPath(each,list);
            System.out.println(each.toString() + " is in polygon: " + flag);
        }
    }
}

/**
 * The {@code Path2D} class provides a simple, yet flexible
 * shape which represents an arbitrary geometric path.
 * It can fully represent any path which can be iterated by the
 * {@link PathIterator} interface including all of its segment
 * types and winding rules and it implements all of the
 * basic hit testing methods of the {@link Shape} interface.
 * <p>

Point2D.Double[1.5, 1.5] is in polygon: false
Point2D.Double[0.2, 0.3] is in polygon: true
Point2D.Double[1.5, 0.1] is in polygon: false
Point2D.Double[0.8, 0.0] is in polygon: true
Point2D.Double[0.08, 0.01] is in polygon: true

参考文档： 
1.http://blog.csdn.net/hjh2005/article/details/9246967 
2.http://www.apihome.cn/api/java/GeneralPath.html 
3.jdk源码

转载自：https://blog.csdn.net/weixin_40955731/article/details/80308994