Algorithm

判断两个多边形的位置关系算法

Posted by Williamic on 2020-05-13

1.概述

   在平面几何运算过程中，经常需要判断两个多边形的几何位置关系，常见的几何位置关系有相离、相切（内切和外切）、相交等。多边形的位置关系，可以从线与线的位置关系、点与多边形的位置关系两个方面来切入，其中主要的算法是跨立算法和射线算法。

2.跨立算法

1）两线段相交

   跨立算法就是利用向量的叉乘来判断线与线是否相交，这里首先要引用向量的叉乘。假设向量A（x1，y1），向量B（x2，y2），则向量A与向量B的叉乘 = k = x1y2 - y1x2。

  • 若k > 0，代表向量B在向量A的逆时针方向。
  • 若k < 0，代表向量B在向量A的顺时针方向。
  • 若k = 0，代表向量B与向量A平行，但可能同向可能反向。

   假设目前有线段AB和CD，如下图所示，若AB与CD相交，则需要满足2个条件：点C和点D在AB线段的异侧，点A和点B在线段CD的异侧。这两个条件为AB与CD相交的充分必要条件。两线段相交    所以利用跨立算法，设k1 = AB向量与AD向量的叉乘 ，k2 = AB向量与AC向量的叉乘，若k1✖️k2 < 0（AB向量与AD向量的叉乘和AB向量与AC向量的叉乘是异号），则证明点C和点D在AB线段的异侧。设k3 = CD向量与CA向量的叉乘，k4 = CD向量与CB向量的叉乘，若k3 * k4 < 0 ，则证明A点和B点在CD线段的异侧。
   以上两个证明都成立，则代表AB线段与CD线段相交。

2）两线段相切

   线段相切是线段相交的一种特殊情况，如下图所示。两线段相切    此时AB向量与AD向量平行，AC向量在AB向量的顺时针方向，故k1k2 = 0 ，k3k4 < 0。
   同理CA向量在CD向量的逆时针方向，CB向量在CD向量的顺时针方向，故点A和点B在CD向量异侧。

3）两线段相离

   只要有线段的两个端点在另一条线段的同侧，则证明两线段相离，如下图所示。向量AD和向量AC都在AB向量的顺时针方向，此时k1 * k2 > 0。两线段相离

3.射线算法（适用于所有多边形）

   在几何运算中，射线算法用来判断一个点是否在多边形内部。即从该点做一条射线，计算该点与多边形的边的交点，如果交点为偶数个， 说明点在多边形外部。如果交点为奇数个，说明点在多边形内部。
   但需要考虑某几种情况：

  • 点在多边形上。
  • 点的射线经过多边形的顶点。
  • 点的射线与多边形的边重合。

1）点在多边形边上

   这种情况只需要判断点是否在多边形上即可。

2）点的射线经过多边形的顶点

   射线经过多边形的顶点有两种类型，从一点出发的射线经过多边形的顶点，如下图k1和k2所示。两线段相离   k1射线经过点C，此时与CD、CB边分别有一个交点，CD边和CB边在k1射线的同侧（可以利用上面提到的跨立算法来进行计算），此时计算实际交点为2个，则射线k1的起始点在多边形外部。
   k2射线经过点B，与BC边和BA边分别有一个交点，BC边和BA边在k2射线的异侧，故把2个交点融合为1个点，则射线k2的起始点在多边形内部。

3）点的射线与多边形的边重合

   与射线经过多边形的顶点情况相同，射线与多边形的边重合的情况同样有两种类型，如下图所示。两线段相离   如图所示射线k1与EF、DC边分别有一个交点，且k1射线与ED边重合，ED边的邻边EF和DC都在k1射线的同侧（可以取EF边的中点和DC边的中点来带入跨立算法），所以忽略ED边，此时实际交点数为2个，故射线k1的起始点在多边形外部。
   同理射线k2与DC、BA边相交，与CB边重合，此时CB边的邻边CD和BA在k2射线的异侧，故取CB边的中点作为射线k2与CB边的交点，此时总交点数为3个，k2射线的起始点在多边形内部。

4.算法代码

1）将顶点转换为XY坐标系

   由于实际应用环境为地图上的2个多边形，所以需要将坐标点转换成XY坐标系中的坐标，其他形式的多边形坐标点按照各自的方式转换成XY坐标系即可。
   贴一段GPS坐标转XY坐标系的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/**
 * 经纬度转XY坐标（厘米为单位）
 *
 * @param latLongList
 * @return
 */
private static List<Point2D> loc2Point2D(LatLong origin, List<LatLong> latLongList) {
    ArrayList<Point2D> pointList = new ArrayList<>();//坐标
    for (int i = 0; i < latLongList.size(); i++) {
        Point2D point2D = loc2Point2D(origin, latLongList.get(i), i);
        pointList.add(point2D);
    }
    return pointList;
}

/**
 * 获取loc相对于origin的坐标
 */
private static Point2D loc2Point2D(LatLong origin, LatLong loc, int pointIndex) {
    Point2D point2D = new Point2D(lon2cm(origin, loc), lat2cm(origin, loc), pointIndex);
    return point2D;
}

/**
 * 经度补偿
 *
 * @param latitude 纬度
 * @return
 */
private static double longitude_scale(double latitude) {
    double cos = Math.cos(latitude * 3.14159265358979323846 / 180.0);
    if (cos < 0.01) {
        cos = 0.01;
    } else if (cos > 1.0) {
        cos = 1.0;
    }
    return cos;
}

/**
 * 经度差转距离（厘米）
 *
 * @param origin
 * @param loc
 * @return
 */
private static double lon2cm(LatLong origin, LatLong loc) {
    double v = loc.getLongitude() - origin.getLongitude();//经度差
    double v1 = (89.83204953368922 / 1E7) / longitude_scale(origin.getLatitude());//对应的比例  XX°/m
    return  v / v1 * 100;//厘米
}

/**
 * 纬度差转距离（厘米）
 *
 * @param origin
 * @param loc
 * @return
 */
private static double lat2cm(LatLong origin, LatLong loc) {
    double v = loc.getLatitude() - origin.getLatitude();//纬度差
    return v / (89.83204953368922 / 1E7) * 100;//厘米
}


public class Point2D{
    public double x;
    public double y;
    public int pointIndex;//边界点的index 

    public Point2D(double x, double y,int pointIndex) {
        this.x = x;
        this.y = y;
        this.pointIndex = pointIndex;
    }
}


public class LatLong {
    public double latitude;//纬度
    public double longitude;//经度

    public LatLong() {
    }

    public LatLong(double latitude, double longitude) {
        this.latitude = latitude;
        this.longitude = longitude;
    }
}

2）快速排除法

   快速排除法是利用多边形的最大横坐标、最大纵坐标、最小横坐标、最小纵坐标四个值来初步判断多边形是否有相交的可能，排除不会相交的情况，减少后续运算。代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/**
 * 快速排除两个地块是否有交叉
 * @param obPointList   障碍区地块坐标点（XY坐标系）
 * @param pointList     边界地块坐标点（XY坐标系）
 * @return              不存在交叉则返回false
 */
public static boolean fastExclude(List<Point2D> obPointList , List<Point2D> pointList){
    double obPointMaxX = Double.MAX_VALUE;
    double obPointMaxY = Double.MAX_VALUE;
    double obPointMinX = Double.MIN_VALUE;
    double obPointMinY = Double.MIN_VALUE;

    double pointMaxX = Double.MAX_VALUE;
    double pointMaxY = Double.MAX_VALUE;
    double pointMinX = Double.MIN_VALUE;
    double pointMinY = Double.MIN_VALUE;

    for (int i = 0; i<  obPointList.size() ;i++){
        Point2D point = obPointList.get(i);

        if (obPointMaxX == Double.MAX_VALUE) {
            obPointMaxX = point.x;
        } else if (obPointMaxX < point.x) {
            obPointMaxX = point.x;
        }

        if (obPointMaxY == Double.MAX_VALUE) {
            obPointMaxY = point.y;
        } else if (obPointMaxY < point.y) {
            obPointMaxY = point.y;
        }

        if (obPointMinX == Double.MIN_VALUE) {
            obPointMinX = point.x;
        } else if (obPointMinX > point.x) {
            obPointMinX = point.x;
        }

        if (obPointMinY == Double.MIN_VALUE) {
            obPointMinY = point.y;
        } else if (obPointMinY > point.y) {
            obPointMinY = point.y;
        }
    }

    for (int i = 0; i<  pointList.size() ;i++){
        Point2D point = pointList.get(i);

        if (pointMaxX == Double.MAX_VALUE) {
            pointMaxX = point.x;
        } else if (pointMaxX < point.x) {
            pointMaxX = point.x;
        }

        if (pointMaxY == Double.MAX_VALUE) {
            pointMaxY = point.y;
        } else if (pointMaxY < point.y) {
            pointMaxY = point.y;
        }

        if (pointMinX == Double.MIN_VALUE) {
            pointMinX = point.x;
        } else if (pointMinX > point.x) {
            pointMinX = point.x;
        }

        if (pointMinY == Double.MIN_VALUE) {
            pointMinY = point.y;
        } else if (pointMinY > point.y) {
            pointMinY = point.y;
        }
    }
    return !(obPointMaxX <= pointMinX) && !(obPointMinX >= pointMaxX) && !(obPointMaxY <= pointMinY) && !(obPointMinY >= pointMaxY);
}

3）跨立算法

   运算前先将点转换成线，再遍历2个多边形的每条边来计算边与边是否相交，若边相交则证明2个多边形相交。代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
public class Line2D {
    private static final double RANGE = 0.1;//允许误差范围
    public Point2D startPoint = null;
    public Point2D endPoint = null;
    public int polygonLineIndex = -1;//-1表示不是polygonLine

    public double maxX = Double.MAX_VALUE;
    public double minX = Double.MIN_VALUE;
    public double maxY = Double.MAX_VALUE;
    public double minY = Double.MIN_VALUE;
    
    //直线一般式 ax+by+c = 0
    public double a;
    public double b;
    public double c;
    
    /**
     * 线段，两点式
     * @param startPoint
     * @param endPoint
     */
    public Line2D(Point2D startPoint, Point2D endPoint, int polygonLineIndex) {
        this.startPoint=startPoint;
        this.endPoint=endPoint;
        this.polygonLineIndex=polygonLineIndex;
        this.minX=Math.min(startPoint.x,endPoint.x)-RANGE;//精度丢失
        this.maxX=Math.max(startPoint.x,endPoint.x)+RANGE;//精度丢失
        this.minY=Math.min(startPoint.y,endPoint.y)-RANGE;//精度丢失
        this.maxY=Math.max(startPoint.y,endPoint.y)+RANGE;//精度丢失
        
        double x1 = startPoint.x;
        double y1 = startPoint.y;
        double x2 = endPoint.x;
        double y2 = endPoint.y;

        this.a = y2 - y1;
        this.b = x1 - x2;
        this.c = (x2 - x1) * y1 - (y2 - y1) * x1;//或x2*y1-x1*y2
        if (this.b < 0) {
            this.a *= -1; this.b *= -1; this.c *= -1;
        }else if (b == 0 && a < 0) {
            this.a *= -1; this.c *= -1;
        }
    }
    
    //判断直线是否平行
    public boolean isParallel(Line2D line2D){
        double a1 = this.a;
        double b1 = this.b;
        double a2 = line2D.a;
        double b2 = line2D.b;
        double m = a1 * b2 - a2 * b1;
        return m == 0;
    }
}

/**
 * 获取线段集合
 *
 * @param pointList
 * @return
 */
private static List<Line2D> point2Line(List<Point2D> pointList) {
    //线段集合
    List<Line2D> lineList = new ArrayList<>();
    for (int i = 0; i < pointList.size(); i++) {
        Line2D line2D;
        if (i == pointList.size() - 1) {
            line2D = new Line2D(pointList.get(i), pointList.get(0), i);
        } else {
            line2D = new Line2D(pointList.get(i), pointList.get(i + 1), i);
        }
        lineList.add(line2D);
    }
    return lineList;
}

public class Vector2D {
    public double x;
    public double y;

    public Vector2D() {
        x = 0;
        y = 0;
    }

    public Vector2D(double _x, double _y) {
        x = _x;
        y = _y;
    }

    //获取弧度
    public double getRadian() {
        return Math.atan2(y, x);
    }

    //获取角度
    public double getAngle() {
        return getRadian() / Math.PI * 180;
    }

    public Vector2D clone() {
        return new Vector2D(x, y);
    }

    public double getLength() {
        return Math.sqrt(getLengthSQ());
    }

    public double getLengthSQ() {
        return x * x + y * y;
    }

    //2个向量的数量积(点积)
    public double dotProduct(Vector2D v) {
        return x * v.x + y * v.y;
    }

    //2个向量的向量积( )
    public double crossProduct(Vector2D v) {
        return x * v.y - y * v.x;
    }
}

/**
 * 跨立算法，判断线与线是否相交（不包含点边重合和边边重合）
 * 有向量 a，b，c
 * 若 (a*b)*(b*c) = 0 则两线段重合
 * 若 (a*b)*(b*c) < 0 则两线段相交
 * 若 (a*b)*(b*c) > 0 则两线段不相交
 *
 * @param obLineList    障碍区组成的线段
 * @param lineList      边界点组成的线段
 * @return              返回true则证明相交
 */
public static boolean judgeIntersect(List<Line2D> obLineList, List<Line2D> lineList) {
    for (int i = 0; i < obLineList.size(); i++) {
        Line2D obLine = obLineList.get(i);
        for (int j = 0; j < lineList.size(); j++) {
            Vector2D vector1 = new Vector2D(obLine.startPoint.x - lineList.get(j).startPoint.x,
                    obLine.startPoint.y - lineList.get(j).startPoint.y);
            Vector2D vector2 = new Vector2D(obLine.endPoint.x - lineList.get(j).startPoint.x,
                    obLine.endPoint.y - lineList.get(j).startPoint.y);
            Vector2D vector3 = new Vector2D(lineList.get(j).endPoint.x - lineList.get(j).startPoint.x,
                    lineList.get(j).endPoint.y - lineList.get(j).startPoint.y);
            //向量vector1 与 vector3的叉乘
            double val1 = vector3.crossProduct(vector1);
            //向量vector2 与 vector3的叉乘
            double val2 = vector3.crossProduct(vector2);

            Vector2D vector4 = new Vector2D(lineList.get(j).startPoint.x - obLine.startPoint.x,
                    lineList.get(j).startPoint.y - obLine.startPoint.y);
            Vector2D vector5 = new Vector2D(lineList.get(j).endPoint.x - obLine.startPoint.x,
                    lineList.get(j).endPoint.y - obLine.startPoint.y);
            Vector2D vector6 = new Vector2D(obLine.endPoint.x - obLine.startPoint.x,
                    obLine.endPoint.y - obLine.startPoint.y);
            //向量vector4 与 vector6的叉乘
            double val3 = vector6.crossProduct(vector4);
            //向量vector5 与 vector6的叉乘
            double val4 = vector6.crossProduct(vector5);

            if (val1 * val2 < 0 && val3 * val4 < 0) {
                return true;
            }
        }
    }
    return false;
}

4）射线算法

   射线向右水平射出，并根据射线与多边形的交点来判断点在多边形的内外。代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
/**
 * 判断点是否在边上
 *
 * @param lineList
 * @param targetPoint
 * @return
 */
public static boolean isOnLine(List<Line2D> lineList, Point2D targetPoint) {
    for (int i = 0; i < lineList.size(); i++) {
        Line2D line = lineList.get(i);
        if (line.isIn(targetPoint)) {
            return true;
        }
    }
    return false;
}

/**
 * 点是否在线段内
 * @param tPoint
 * @return
 */
public boolean isIn(Point2D tPoint) {
    if (startPoint!=null&&endPoint!=null){
        Vector2D tVector = new Vector2D(tPoint.x - startPoint.x, tPoint.y - startPoint.y);
        Vector2D startVector = new Vector2D(endPoint.x - startPoint.x, endPoint.y - startPoint.y);
        double v = startVector.crossProduct(tVector);
        double yDis = Math.abs(v / startVector.getLength());
        if (yDis<RANGE){//tPoint在直线上
            if (contain(tPoint)){//tPoint在线段上
                return true;
            }
        }
    }
    return false;
}

public class IntersectData implements Cloneable {
    public Point2D point2D;
    public int polygonLineIndex;//此处值为-1表示边界点 -5表示障碍区的边 -4表示额外增加的障碍区点

    public IntersectData(Point2D point2D, int crossLineIndex, int polygonLineIndex) {
        this.point2D = point2D;
        this.crossLineIndex = crossLineIndex;
        this.polygonLineIndex = polygonLineIndex;
    }
}

/**
 * 获取点到直线的距离，正值表示在startVector直线上方，负值表示在startVector直线下方
 *
 * @param startPoint
 * @param endPoint
 * @param targetPoint
 * @return
 */
public static double getRealYDis(Point2D startPoint, Point2D endPoint, Point2D targetPoint) {
    Vector2D startVector = new Vector2D(endPoint.x - startPoint.x, endPoint.y - startPoint.y);
    Vector2D endVector = new Vector2D(targetPoint.x - startPoint.x, targetPoint.y - startPoint.y);
    double v = startVector.crossProduct(endVector);
    double dis = v / startVector.getLength();
    double angle = startVector.getAngle();
    if (angle >= -90 && angle < 90) {
        dis = dis;
    } else {
        dis = -dis;
    }
    return dis;
}

//点与直线x轴上的距离
public static double getXDis(Point2D startPoint, Point2D endPoint, Point2D targetPoint) {
    Vector2D startVector = new Vector2D(endPoint.x - startPoint.x, endPoint.y - startPoint.y);
    Vector2D endVector = new Vector2D(targetPoint.x - startPoint.x, targetPoint.y - startPoint.y);
    double v = startVector.dotProduct(endVector);
    return v / startVector.getLength();
}

/**
 * 判断目标点是否在指定多边形内，适应全部多边形
 *
 * @param target
 * @param latLongList
 * @return
 */
public static boolean isInPolygon(LatLong target, List<LatLong> latLongList) {
    //目标点
    Point2D targetPoint = loc2Point2D(latLongList.get(0), target, -1);

    //多边形的点
    List<Point2D> pointList = loc2Point2D(latLongList.get(0), latLongList);

    //多边形的边
    List<Line2D> lineList = point2Line(pointList);

    Point2D toPoint = new Point2D(targetPoint.x + 100, targetPoint.y, -1);
    Line2D crossLine = new Line2D(targetPoint, toPoint);

    //判断点是否在多边形的边上
    if (isOnLine(lineList, targetPoint)) {//点在边上
        return true;
    }
    //交点集合
    ArrayList<IntersectData> intersectPoint2DList = new ArrayList<>();
    for (int i = 0; i < lineList.size(); i++) {
        //平行
        if (crossLine.isParallel(lineList.get(i))){
            //判断是否重合
            if (Math.abs(crossLine.a * lineList.get(i).startPoint.x
                    + crossLine.b * lineList.get(i).startPoint.y + crossLine.c) < 0.1) {
                int next = (i+1)%lineList.size();
                int first = (lineList.size()+i-1)%lineList.size();
                int temp;
                if (next < first){
                    temp = next;
                    next = first;
                    first = temp;
                }
                //左右邻边
                Line2D firstLine = lineList.get(first);
                Line2D nextLine = lineList.get(next);
                //判断这两点是否在横截线同一边
                Point2D startPoint = new Point2D((firstLine.startPoint.x + firstLine.endPoint.x) / 2,
                        (firstLine.startPoint.y + firstLine.endPoint.y) / 2, -1);
                Point2D endPoint = new Point2D((nextLine.startPoint.x + nextLine.endPoint.x) / 2,
                        (nextLine.startPoint.y + nextLine.endPoint.y) / 2, -1);

                double startYDis = getRealYDis(targetPoint, toPoint, startPoint);
                double endYDis = getRealYDis(targetPoint, toPoint, endPoint);

                if (startYDis > -0.1 && startYDis < 0.1) {
                    startYDis = 0;
                }
                if (endYDis > -0.1 && endYDis < 0.1) {
                    endYDis = 0;
                }

                if (startYDis * endYDis < 0) {//邻边在射线两端
                    intersectPoint2DList.add(new IntersectData(new Point2D((lineList.get(i).startPoint.x+lineList.get(i).endPoint.x)/2,
                            (lineList.get(i).startPoint.y+lineList.get(i).endPoint.y)/2,-1),-1,i));
                }
            }
        }else {
            Point2D intersectPoint = crossLine.getIntersectPoint(lineList.get(i));
            if (intersectPoint != null) {//targetLine与多边形的边相交
                intersectPoint2DList.add(new IntersectData(intersectPoint, -1, i));
            }
        }
    }
    ArrayList<Pair<Integer, Integer>> pairList = new ArrayList<>();
    for (int i = 1; i < intersectPoint2DList.size(); i++) {
        IntersectData first = intersectPoint2DList.get(i - 1);
        IntersectData next = intersectPoint2DList.get(i);
        double firstDis = getXDis(targetPoint, toPoint, first.point2D);
        double nextDis = getXDis(targetPoint, toPoint, next.point2D);
        if (Math.abs(nextDis - firstDis) < 0.1) {//交点重合
            int firstLineIndex = first.polygonLineIndex;
            int nextLineIndex = next.polygonLineIndex;
            Line2D firstLine = lineList.get(firstLineIndex);//交点i - 1对应的线段
            Line2D nextLine = lineList.get(nextLineIndex);//交点i对应的线段

            //判断这两点是否在横截线同一边
            Point2D startPoint = new Point2D((firstLine.startPoint.x + firstLine.endPoint.x) / 2,
                    (firstLine.startPoint.y + firstLine.endPoint.y) / 2, -1);
            Point2D endPoint = new Point2D((nextLine.startPoint.x + nextLine.endPoint.x) / 2,
                    (nextLine.startPoint.y + nextLine.endPoint.y) / 2, -1);

            double startYDis = getRealYDis(targetPoint, toPoint, startPoint);
            double endYDis = getRealYDis(targetPoint, toPoint, endPoint);

            if (startYDis > -0.1 && startYDis < 0.1) {
                startYDis = 0;
            }
            if (endYDis > -0.1 && endYDis < 0.1) {
                endYDis = 0;
            }
            if (startYDis * endYDis >= 0) {//同一边
                //不用处理，直接当两个交点
            } else {//dis1*dis2<0 在两端
                //把两交点合并一点
                pairList.add(Pair.create(i - 1, i));
            }
        }
    }
    for (int i = 0; i < pairList.size(); i++) {
        Pair<Integer, Integer> pair = pairList.get(i);
        int first = pair.first;
        int second = pair.second;
        //移除其中一个即可
        intersectPoint2DList.remove(first);
    }
    //去除在targetPoint点负方向的点（去除正方向也行，只要取一个方向的交点即可）
    Iterator<IntersectData> iterator = intersectPoint2DList.iterator();
    while (iterator.hasNext()) {
        IntersectData next = iterator.next();
        Point2D point2D = next.point2D;
        double xDis1 = getXDis(targetPoint, toPoint, point2D);//交点到原点的X轴距离
        if (xDis1 < -0.1) {
            iterator.remove();
        }
    }
    if (intersectPoint2DList.size() % 2 != 0) {//交点数为奇数  targetPoint点在多边形内
        return true;
    }
    return false;
}

5）判断位置关系

   判断两个多边形位置关系（相离、相交、包含、重合），代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
* 判断多边形位置关系
* @param newLatLongs       多边形A的实际坐标
* @param actualOb          多边形B的实际坐标
*/
private void getPolygonsPosition(List<LatLong> newLatLongs, List<LatLong> actualOb){
    //将GPS坐标点转换成XY坐标系
    List<Point2D> point2Ds = loc2Point2D(newLatLongs.get(0), newLatLongs);
    List<Point2D> obPointList = loc2Point2D(newLatLongs.get(0), actualOb);
    //快速排除法判断存在交叉部分
    if (MapUtils.fastExclude(obPointList, point2Ds)) {
        //点转换为线段
        List<Line2D> borderLine = point2Line(point2Ds);
        List<Line2D> obLine = point2Line(obPointList);
        //跨立算法判断线段相交
        if (MapUtils.judgeIntersect(obLine, borderLine)) {
            //2个多边形相交
        } else {
            //2个多变形不相交
            boolean include = true;
            for (int j = 0; j < obPointList.size(); j++) {
                //判断多边形B的点是否在多边形A的线段上
                if (!MapUtils.isOnLine(borderLine, obPointList.get(j))) {
                    //射线算法判断多边形B点的是否在多边形A内
                    if (MapUtils.isInPolygon(actualOb.get(j), newLatLongs)) {
                        //多边形B在多边形A的内部（内切、内包含）
                        include = false;
                        break;
                    } else {//（外离、外包含）
                        if (MapUtils.isInPolygon(newLatLongs.get(0), actualOb)){
                            //多边形B包含多边形A
                            include = false;
                            break;
                        } else {
                            //多边形B在多边形A外部
                            include = false;
                            break;
                        }
                    }
                }
            }
            if (include) {
                //两个多边形重合
            }
        }
        }else{
            //两个多边形相离
        }
}



FEATURED TAGS
Algorithm
FRIENDS