获取线段与多边形的交点,用于地图中路段与框选多边形求交点

思路

1. 将多边形看成多条线段
2. 转换为求指定线段与多边形中所有线段的交点

/**
 * 获取线段与多边形的交点
 *
 * @param lineSeg
 * @param polygonStr  String 数据格式:
 *              [
 *                  {
 *                  "lat": 29.714137480015246,
 *                  "lng": 106.56833767890933
 *                  },
 *                  {
 *                      "lat": 29.712870211340846,
 *                      "lng": 106.56738281250004
 *                  },
 *                  {
 *                      "lat": 29.712944756999807,
 *                      "lng": 106.56945347785953
 *                  },
 *                  {
 *                      "lat": 29.714370432075135,
 *                      "lng": 106.5696465969086
 *                  }
 *               ]
 * @return 交点集合
 */
public static List<Point2D> getIntersectPtsByLineSeqAndPolygon(LineSegment2D lineSeg, String polygonStr) {
    List<Point2D.Double> polygonPointList = getPointList(polygonStr);
    List<Point2D> intersectPointList = CollUtil.newArrayList();

    Point2D intersectPoint = null;
    // 遍历多边形,判断每条边,是否与指定线段相交
    for (int i = 0; i < polygonPointList.size(); i ++) {
        // 下一个点的下标: 当i取最大时,nextI = 0,及第一个点
        int nextI = (i + 1) % polygonPointList.size();
        LineSegment2D edge = new LineSegment2D(
            polygonPointList.get(i).x, polygonPointList.get(i).y,
            polygonPointList.get(nextI).x, polygonPointList.get(nextI).y);

        // 得到两条线段的交点
        intersectPoint = getCrossPointBy2LineSegment(lineSeg, edge);
        if (intersectPoint != null) {
            intersectPointList.add(intersectPoint);
        }

    }

    // 排除相同的点
    ArrayList<Point2D> distinct = CollUtil.distinct(intersectPointList);

    return distinct;
}
           

/**
 * 获取两条线段交点
 * @param lsegA
 * @param lsegB
 * @return
 */
public  static Point2D getCrossPointBy2LineSegment(LineSegment2D lsegA, LineSegment2D lsegB){
    double x;
    double y;
    double x1=lsegA.firstPoint().getX();
    double y1=lsegA.firstPoint().getY();
    double x2=lsegA.lastPoint().getX();
    double y2=lsegA.lastPoint().getY();
    double x3=lsegB.firstPoint().getX();
    double y3=lsegB.firstPoint().getY();
    double x4=lsegB.lastPoint().getX();
    double y4=lsegB.lastPoint().getY();
    double k1=Double.MAX_VALUE;
    double k2=Double.MAX_VALUE;
    boolean flag1=false;
    boolean flag2=false;

    if((x1-x2)==0)
        flag1=true;
    if((x3-x4)==0)
        flag2=true;

    if(!flag1)
        k1=(y1-y2)/(x1-x2);
    if(!flag2)
        k2=(y3-y4)/(x3-x4);

    if(k1==k2)
        return null;

    if(flag1){
        if(flag2)
            return null;
        x=x1;
        if(k2==0){
            y=y3;
        }else{
            y=k2*(x-x4)+y4;
        }
    }else if(flag2){
        x=x3;
        if(k1==0){
            y=y1;
        }else{
            y=k1*(x-x2)+y2;
        }
    }else{
        if(k1==0){
            y=y1;
            x=(y-y4)/k2+x4;
        }else if(k2==0){
            y=y3;
            x=(y-y2)/k1+x2;
        }else{
            x=(k1*x2-k2*x4+y4-y2)/(k1-k2);
            y=k1*(x-x2)+y2;
        }
    }
    if(between(x1,x2,x)&&between(y1,y2,y)&&between(x3,x4,x)&&between(y3,y4,y)){
        Point2D point=new Point2D.Double();
        point.setLocation(x,y);
        if(point.equals(lsegA.firstPoint())||point.equals(lsegA.lastPoint()))
            return null;
        return point;
    }else{
        return null;
    }
}

public static boolean between(double a,double b,double target){
     // 允许的误差值
     double offset = 0.0000001;
     if(target>=a-offset && target<=b+offset || target<=a+offset && target>=b-offset)
         return true;
     else
         return false;
 }