判断一个点是否在某个区域内(多边形)
背景：
比如滴滴会根据乘客所在的不同区域，给出不同的价格。市区堵一点，那么价格也高点。获取服务范围只规定在某个范围内
原理：
求解从该点向右发出的水平线射线与多边形各边的交点，当交点数为奇数，则在内部。
不过要注意几种特殊情况：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 /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 /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 /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);
Listpoints = 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算法
本算法是由W. Randolph Franklin提出的。算法的思路如下：
从待测点出发作一条射线，可沿y轴方向也可没x轴方向，然后判断这条射线与不规则区域的交点数量。如果点的两边交点的个数都是奇数个则该点在多边形内，否则在多边形外。
这个算法对于任意不规则图形都适用。
关于本算法更详细的介绍，请参考参考文献1。
2.多边形面积算法
非凹多边形，凹多边形需要切割为凸多边形。
第四点分别与三角形的两个点组成的面积分别设为S1,S2,S3，只要S1+S2+S3>原来的三角形面积就不在三角形范围中.可以使用海伦公式 。
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);}}}
1234567891011121314151617181922232425262728293031323334353637383940414243444546474849505152535455565758596061
上面的代码主要是用到了java.awt.geom包。java.awt.geom是jdk自带的类包，不用任何额外的安装。GeneralPath 类表示根据直线、二次曲线和三次 (Bézier) 曲线构造的几何路径。它可以包含多个子路径。GeneralPath继承自java.awt.geom.Path2D。那么这个Path2D是干嘛的呢？看看jdk里面的一段注解：
/*** 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>
12345678
第一句话就告诉了我们Path2D是干嘛的：Path2D类提供了一个简单，灵活的形状类，用来表示任意几何路径。
测试代码中，生成了一个边长为1的正方形矩形区域，其中一个顶点为(0,0)。最后的测试结果为：
Point2D.Double[1.5, 1.5] is in polygon: falsePoint2D.Double[0.2, 0.3] is in polygon: truePoint2D.Double[1.5, 0.1] is in polygon: falsePoint2D.Double[0.8, 0.0] is in polygon: truePoint2D.Double[0.08, 0.01] is in polygon: true
12345
测试结果准确无误，完美地满足了我们的需求！
时间关系，没有来得及具体研究jdk里源码的实现细节，后续可以进一步研究Path2D的实现算法。
参考文档：
1./hjh/article/details/9246967
2./api/java/GeneralPath.html
3.jdk源码
