如何判断地图要素的旋转方向 - GIS 算法

最近我接到了一个项目,任务是判断某些道路要素的旋转方向是否符合预期。为此,需要一种方法来识别这些要素的旋转方向。于是,我将自己设计的算法思路整理并撰写成此文。

什么是几何体的旋转方向

我们知道,Polygon(多边形)由一个外壳和内部的孔洞组成,因此判断旋转方向的关键在于识别多边形最外层点集的旋转方向。通常,这些最外层点集被存储在一个数组中,数组中的每个元素代表一个坐标点,这些坐标点的排列顺序就决定了几何体的旋转方向。以下是一个 0 -> 1 -> 2 -> 3 顺时针旋转的矩形示例:

1
2
3
4
5
6
 0       1
  *---->*
  ^     |
  |     v
  *<----*
 3       2

接下来,我们详细分析如何通过算法判断几何体的旋转方向。

水平 2D 要素旋转方向判断

首先是最简单的水平 2D 要素旋转方向判断。水平 2D 几何的旋转方向是指从俯视视角观察几何体时的旋转方向。这类算法主要用于判断道路标识的场景。我们观察以下图形:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
y         y extreme point  
^       、      、
|     、      、
|    *------*
|   /        ·-----*
|  /                \
|* 、x extreme point *
|  \________________/  `- x extreme point
|   、 
|    y extreme point  
+------------------------> x

可以发现,一个平面图形相对于某个坐标轴,总有至少一个极大值点和一个极小值点。因此,我们只需获取平面几何边框的所有极值点,对这些点去重后,从小到大(索引值)取出三个连续的凸点,通过判断它们构成的向量的叉乘,即可确定整个平面几何的旋转方向。之所以选择凸点是为了降低共线概率。

理论基础

假设在索引 0、1、2 位置上分别存在三个凸点,分别为点 a、点 b 和点 c。我们可以利用这三个点构建两个向量,分别是 a->bb->c。示意图如下:

clockwise

首先设 a、b、c 三个点的坐标分别为 (x1, y1)(x2, y2)(x3, y3)

通过这三个点,我们可以定义两个向量:

  • 向量 v1 是从点 a 到点 b 的向量,即 (x2-x1, y2-y1),我们将这个向量坐标设为 (A, B)
  • 向量 v2 是从点 b 到点 c 的向量,即 (x3-x2, y3-y2),我们将这个向量坐标设为 (C, D)

在二维空间中,这两个向量的叉乘就是 (A, B) x (C, D),结果等于 A * D - B * C

叉乘的结果是一个标量,其几何解释如下:

  • 面积:两个向量的叉乘的绝对值等于由这两个向量构成的平行四边形的面积。在这里,三角形 a-b-c 的面积是平行四边形面积的一半。因此,叉乘为零表示面积为零,即三个点共线。
  • 方向:叉乘的符号表示向量的相对方向:
    • 如果叉乘值大于 0,则两个向量的转动方向是逆时针;
    • 如果叉乘值小于 0,则两个向量的转动方向是顺时针;
    • 如果等于 0,则三点共线。

对于取不到三个凸点的特殊情况:

1
2
3
4
5
6
7
8
y
^
|        * <---b
|       /|
|   .--' * <---c:距离 a->b 距离最远点
|  /.· `
| *<-----------a
+----------------------->x

我们可以将这两个极值点连线,并从所有外围点集中找一个距离该直线最远的点,凑成三个尽可能凸的点进行计算。

下面我们通过代码来实现这个算法:

 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
public static boolean isClockwise2D(Polygon polygon) {
    // [1] 获取外壳所有点
    Coordinate[] coordinates = polygon.getExteriorRing().getCoordinates();
    // [2] 获取所有极值点在 coordinates 中的索引,并输出集合
    Set<Integer> extremePointIndex = getExtremePointIndex(polygon);
    // [3] 判断是否可以获取到 3 个凸点,如果获取不到,则兜底
    List<Integer> indexList= Lists.newArrayList(extremePointIndex);
    if (indexList.size() == 2) {
        int farthestIndex = getFarthestIndex(
                coordinates[indexList.get(0)],
                coordinates[indexList.get(1)], coordinates);
        // 引入救场的点,并通过 Set 去重
        Set<Integer> integerSet = Sets.newHashSet(indexList);
        integerSet.add(farthestIndex);
        indexList = Lists.newArrayList(integerSet);
    }
    // [4] 对结果排序
    indexList.sort(Integer::compareTo);

    // [5] 索引从小到大,取出三个连续的凸点
    double x1 = coordinates[indexList.get(0)].x;
    double y1 = coordinates[indexList.get(0)].y;

    double x2 = coordinates[indexList.get(1)].x;
    double y2 = coordinates[indexList.get(1)].y;

    double x3 = coordinates[indexList.get(2)].x;
    double y3 = coordinates[indexList.get(2)].y;

    // [6] 计算向量的叉乘
    double ret = (x2 - x1) * (y3 - y2) - (y2 - y1) * (x3 - x2);

    // [7] 小于 0 表示顺时针
    return ret < 0;
}
  • 获取极值点的 getExtremePointIndex 实现如下:

     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
    
    private static Set<Integer> getExtremePointIndex(Polygon polygon) {
        // 先拿到多边形外壳
        Coordinate[] coordinates = polygon.getExteriorRing().getCoordinates();
    
        int maxXIndex = -1, 
            maxYIndex = -1, 
            minXIndex = -1, 
            minYIndex = -1;
        double maxX = Double.MIN_VALUE, 
               maxY = Double.MIN_VALUE, 
               minX = Double.MAX_VALUE, 
               minY = Double.MAX_VALUE;
        // 遍历所有点,更新极值
        for (int i = 1; i < coordinates.length; i++) {
            if (maxX < coordinates[i].x) {
                maxX = coordinates[i].x;
                maxXIndex = i;
            }
            if (maxY < coordinates[i].y) {
                maxY = coordinates[i].y;
                maxYIndex = i;
            }
            if (minX > coordinates[i].x) {
                minX = coordinates[i].x;
                minXIndex = i;
            }
            if (minY > coordinates[i].y) {
                minY = coordinates[i].y;
                minYIndex = i;
            }
        }
        // 返回四个极值
        return Sets.newHashSet(maxXIndex, maxYIndex, minXIndex, minYIndex);
    }
  • 获取最远点索引的 getFarthestIndex 实现如下:

    理论基础

    已知直线上的两个点 (x1, y1)(x2, y2),设其他点的坐标为 (x, y),那么这个点到已知直线的距离公式为 (y2-y1)x - (x2-x1)y + (x2y1 - x1y2)。推导过程如下:

    • 首先,两点式的直线方程为 y-y1 = (y2-y1) / (x2-x1) * (x-x1)。将等号两边同乘 (x2-x1) 后得到:(y-y1)*(x2-x1) = (y2-y1)*(x-x1),继续拆解,得到关于 x 和 y 的方程:(x2-x1)y - (x2-x1)y1 = (y2-y1)x - (y2-y1)x1。将所有项移到等式一侧,可得:0 = (y2-y1)x - (x2-x1)y + (x2-x1)y1 - (y2-y1)x1。其中,(x2-x1)y1 - (y2-y1)x1 等于 x2y1 - x1y1 -y2x1 + x1y1,即 x2y1 - y2x1。因此,最终可得两点式的直线方程为:(y2-y1)x - (x2-x1)y + (x2y1 - y2x1) = 0
    • 我们将上述两点式直线方程简化为 Ax + By + C = 0,其中:A = (y2-y1)B = -(x2-x1)C = (x2y1 - x1y2)。那么点 (x0,y0) 到直线的距离 d = |Ax0 + By0 + C| / √(A^2 + B^2)

    因此,在比较点到直线的距离大小,不需要计算实际值的情况下,我们只需计算 |Ax0 + By0 + C| 即可,也就是相互比较 (y2-y1)x - (x2-x1)y + (x2y1 - x1y2) 的绝对值。

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    
    private static int getFarthestIndex(Coordinate c0, Coordinate c1, Coordinate[] coordinates) {
        double x1 = c0.x, y1 = c0.y;
        double x2 = c1.x, y2 = c1.y;
        // 两点式直线到点的距离方程的参数
        Triple<Double, Double, Double> lineFactor = Triple.of(y2 - y1, x1 - x2, x2*y1 - x1*y2);
    
        double maxDistance = -10000;
        int index = -1;
    
        for (int i = 0; i < coordinates.length; i++) {
            Coordinate ci = coordinates[i];
            // 两点式直线到点的距离公式,忽略规范化系数
            double curDistance = Math.abs(lineFactor.getLeft() * ci.x + lineFactor.getMiddle() * ci.y + lineFactor.getRight());
            // 获取最远点的索引
            if (curDistance > maxDistance) {
                maxDistance = curDistance;
                index = i;
            }
        }
        return index;
    }

空间 3D 要素旋转方向判断

接下来是 3D 要素旋转方向的判断,这类算法主要用于诸如交通标志牌等场景的判定。与水平 2D 要素不同,3D 要素旋转方向与观察者所处的位置有关。举个例子,一个面向北的观察者看到一个要素顺时针旋转,而面向南的另一个观察者看到同样的要素则是逆时针旋转的。因此,这类算法需要引入一个表示观察者的参考向量(通常是车道线):

clockwise ref

我们首先将观察者目视方向所在的直线作为参考向量,再从要素中选择一个与地面平齐的向量,最稳妥的做法就是获取要素顶端边线向量(从小索引点,指向大索引点,且忽略 Z 值),最后计算这两个向量之间的夹角即可确定竖直要素的旋转方向。

接下来我们着手完成算法的实现:

 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
public static Boolean isClockwise3D(Polygon polygon, LineString referenceLine) {
    // [1] 获取外壳所有点
    Coordinate[] coordinates = polygon.getExteriorRing().getCoordinates();
    // [2] 获取外壳中,z 坐标最高的点
    Coordinate maxZC = Arrays.stream(coordinates).max(Comparator.comparing(c -> c.z)).orElse(null);
    if (maxZC == null) {
        // unlikely
        return null;
    }
    // [3] 再来一次遍历,找到上述 z 值最高的点
    double maxZ = maxZC.z;
    // 小优化:i = 0 的点一般会被作为要素最高点,因此这里第一个判断它,
    for (int i = 0; i < coordinates.length - 1; i++) {
        double currZ = coordinates[i].z;
        if (currZ != maxZ) {
            continue;
        }
        // [4] 获取最高点前后两个点,然后拿到两个向量,选择较长的那个作为顶边向量
        int pre = i - 1;
        int next = i + 1;
        if (i == 0) {
            pre = coordinates.length - 2;
            next = 1;
        } else if (i == coordinates.length - 2) {
            pre = i - 1;
            next = 0;
        }
        // [5] 拿到 pre->i 与 i->next 中较长的向量,当做要素顶端边线
        double smeDistance1 = getDistance(coordinates[pre], coordinates[i]);
        double smeDistance2 = getDistance(coordinates[i], coordinates[next]);
        LineString vector = smeDistance1 > smeDistance2 ?
                createLineString(coordinates[pre], coordinates[i]) :
                createLineString(coordinates[i], coordinates[next]);
        // [6] 然后开始截取参考向量,以要素到参考向量上的投影线为中心,上下 1 米,避免太长影响性能
        LengthIndexedLine lengthIndexedLine = new LengthIndexedLine(referenceLine);
        double projectIndex = lengthIndexedLine.project(coordinates[0]);
        Coordinate projectPoint = lengthIndexedLine.extractPoint(projectIndex);
        referenceLine = cutLine(referenceLine, projectPoint, 1, 1);
        if (referenceLine == null) {
            // unlikely
            return null;
        }
        // [7] 最后,开始判断是否是顺时针
        Boolean result = checkHandle(referenceLine, vector);
        // [8] 返回结果
        return result == null ? null : Boolean.TRUE.equals(result);
    }
    return null;
}

其中:

  • getDistance 方法用于计算两个点之间的距离,涉及机密省略;

  • createLineString 方法用于创建两点之间的线段,可以参考 JTS - 创建 LineString、MultiLineString

  • cutLine 方法用于裁切线段,该方法以 projectPoint 为中心,上下裁切指定的长度。思路就是以从某个点开始,沿着线路两端遍历指定的距离,得到两个的线段,最终将其融合即可。实现如下:

      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
    
    private static LineString cutLine(LineString ls, Coordinate start, int forwardDistance, int backDistance) {
        // 截取从 start 开始,到尾点的部分
        LineString forwardLine = cutLineToEnd(ls, start);
        if (forwardLine != null) {
            // 然后从截取部分的首点开始,向后截取 forwardDistance 长度
            forwardLine = cutLineInStart(forwardLine, forwardDistance);
        }
        // 截取从首点开始,到 start 的部分
        LineString backLine = cutLineToStart(ls, start);
        if (backLine != null) {
            // 然后从截取部分的尾点开始,向前截取 backDistance 长度
            backLine = cutLineInEnd(backLine, backDistance);
        }
        // 参数校验
        if (forwardLine == null || backLine == null) {
            return null;
        }
        // 特殊情况直接返回结果
        if (forwardLine == null && backLine != null) {
            return backLine;
        }
        if (forwardLine != null && backLine == null) {
            return forwardLine;
        }
        // 两个方向都存在结果,则融合
        List<Coordinate> coordinates = Lists.newArrayList();
        coordinates.addAll(Arrays.asList(backLine.getCoordinates()));
        coordinates.remove(coordinates.size() - 1);
        coordinates.addAll(Arrays.asList(forwardLine.getCoordinates()));
        GeometryFactory geometryFactory = new GeometryFactory();
        return geometryFactory.createLineString(coordinates.toArray(new Coordinate[0]));
    }
    
    /**
     * 线段裁切,范围从 start 坐标开始,直到线段结尾
     * @param ls 目标线段
     * @param start 起始点
     * @return 裁切后的线段,如果构不成线段返回 null
     */
    private static LineString cutLineToEnd(LineString ls, Coordinate start) {
        GeometryFactory geometryFactory = new GeometryFactory();
        Point startPoint = geometryFactory.createPoint(start);
        List<Coordinate> coordinates = Lists.newArrayList();
        int i = 0;
        Coordinate[] lsCoordinates = ls.getCoordinates();
        // 遍历目标线段,直至 start 坐标位置,拿到最近的索引 i
        for (int j = 1; j < lsCoordinates.length; j++) {
            // 特殊情况,start 恰好是 ls 首点
            if (lsCoordinates[j - 1].equals(start)) {
                break;
            }
            i = j;
            // 特殊情况,start 恰好是 ls 上的某个点
            if (lsCoordinates[j].equals(start)) {
                break;
            }
            // 计算 start 到当前小节线段的距离,足够小表示点在线上,意味着找到了起始点索引
            LineString tmpLine = createLineString(lsCoordinates[j - 1], lsCoordinates[j]);
            double distance = getDistance(startPoint, tmpLine);
            if (distance < Math.pow(10, -7)) {
                coordinates.add(start);
                break;
            }
        }
        // 将从 i 到末尾的所有点,生成线段返回
        coordinates.addAll(Arrays.asList(lsCoordinates).subList(i, lsCoordinates.length));
        if (coordinates.size() < 2) {
            return null;
        }
        return createLineString(coordinates.toArray(new Coordinate[0]));
    }
    
    /**
     * 线段裁切,范围从线段首点开始,一直切到 end 坐标附近
     * @param ls 目标线段
     * @param end 终点
     * @return 裁切后的线段,如果构不成线段返回 null
     */
    private static LineString cutLineToStart(LineString ls, Coordinate end) {
        GeometryFactory geometryFactory = new GeometryFactory();
        Point endPoint = geometryFactory.createPoint(end);
        List<Coordinate> coordinates = Lists.newArrayList();
        Coordinate[] lsCoordinates = ls.getCoordinates();
        // 遍历目标线段,直至 end 坐标位置,将经过的点加入 coordinates
        for (int i = 1; i < lsCoordinates.length; i++) {
            coordinates.add(lsCoordinates[i - 1]);
            // 特殊情况,end 恰好是线段首点
            if (lsCoordinates[i - 1].equals(end)) {
                break;
            }
            // 特殊情况,end 恰好是 ls 上的某个点
            if (lsCoordinates[i].equals(end)) {
                coordinates.add(lsCoordinates[i]);
                break;
            }
            // 计算 end 到当前小节线段的距离,足够小表示点在线上,意味着找到了终点索引
            LineString tmpLine = createLineString(lsCoordinates[i - 1], lsCoordinates[i]);
            double distance = getDistance(endPoint, tmpLine);
            if (distance < Math.pow(10, -7)) {
                coordinates.add(end);
                break;
            }
        }
        // 将从首点到 end 附近的所有点,生成线段返回
        if (coordinates.size() < 2) {
            return null;
        }
        return createLineString(coordinates.toArray(new Coordinate[0]));
    }
    
    /**
     * 从首点截取指定长度,长度不够时返回整条线
     * @param ls 目标线段
     * @param length 裁切的长度
     * @return 裁切后的线段
     */
    private static LineString cutLineInStart(LineString ls, int length) {
        double dLen = 0.0; // 缓存已经遍历到的长度
        boolean bGet = false;
        List<Coordinate> coordinates = Lists.newArrayList();
        // 从首点开始,计算每个节点的长度,追加到 dLen
        for (int i = 0; i < ls.getNumPoints() - 1; i++) {
            Point cur = ls.getPointN(i);
            Point next = ls.getPointN(i + 1);
            double distance = getDistance(cur.getCoordinate(), next.getCoordinate());
            if (dLen + distance > length) { // 如果已遍历长度加上当前小节,超过了需求
                // 计算剩余距离
                double neededLen = length - dLen;
                // 计算并入的比例
                double percent = neededLen / distance;
                double x = cur.getCoordinate().x + (next.getCoordinate().x - cur.getCoordinate().x) * percent;
                double y = cur.getCoordinate().y + (next.getCoordinate().y - cur.getCoordinate().y) * percent;
                coordinates.add(new Coordinate(x, y));
                bGet = true; // 表示提前找够,跳出的
                break;
            } else { // 否则保存当前点,继续向后遍历
                coordinates.add(cur.getCoordinate());
            }
            dLen += distance; // 追加长度
        }
    
        if (!bGet) {
            coordinates.add(ls.getCoordinateN(ls.getNumPoints() - 1));
        }
        GeometryFactory geometryFactory = new GeometryFactory();
        return geometryFactory.createLineString(coordinates.toArray(new Coordinate[0]));
    }
    
    /**
     * 从尾点向前截取指定长度,长度不够时返回整条线路
     * @param ls 目标线段
     * @param length 裁切的长度
     * @return 裁切后的线段
     */
    private static LineString cutLineInEnd(LineString ls, int length) {
        double dLen = 0.0; // 缓存已经遍历到的长度
        boolean bGet = false;
        List<Coordinate> coordinates = Lists.newArrayList();
        // 从首点开始,计算每个节点的长度,追加到 dLen
        for (int i = ls.getNumPoints() - 1; i > 0; i--) {
            Point cur = ls.getPointN(i);
            Point pre = ls.getPointN(i - 1);
            double distance = getDistance(cur.getCoordinate(), pre.getCoordinate());
            if (dLen + distance > length) { // 如果已遍历长度加上当前小节,超过了需求
                // 计算剩余距离
                double neededLen = length - dLen;
                // 计算并入的比例
                double present = neededLen / distance;
                double x = cur.getCoordinate().x + (cur.getCoordinate().x - pre.getCoordinate().x) * present;
                double y = cur.getCoordinate().y + (cur.getCoordinate().y - pre.getCoordinate().y) * present;
                coordinates.add(new Coordinate(x, y));
                bGet = true; // 表示提前找够,跳出的
                break;
            } else { // 否则保存当前点,继续向前遍历
                coordinates.add(cur.getCoordinate());
            }
            dLen += distance; // 追加长度
        }
    
        if (!bGet) {
            coordinates.add(ls.getCoordinateN(0));
        }
        Collections.reverse(coordinates);
        GeometryFactory geometryFactory = new GeometryFactory();
        return geometryFactory.createLineString(coordinates.toArray(new Coordinate[0]));
    }
  • 最终,获取到顶边向量后,配合参考向量,通过 checkHandle 方法计算旋转方向。该算法的关键在于确定顶边向量所指的方向是否位于观察者的右侧。

    我们以顺时针方向为基准,计算这两个向量与 y 轴正方向的夹角。如果顶边向量与 y 轴正方向的夹角位于参考向量与 y 轴正方向的夹角其顺时针方向 180 度之间的范围内,即可确定要素的旋转方向也是顺时针。实现如下:

      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
    
    /**
     * 判断是否是顺时针
     * @param referenceLine 参考向量
     * @param featureLine 要素顶边向量
     * @return 是否是顺时针,如果两线接近平行返回 null
     */
    private static Boolean checkHandle(LineString referenceLine, LineString featureLine) {
        // 接近平行,返回 null
        if (isParallel(referenceLine, featureLine, 15)) {
            return null;
        }
        // 计算参考向量与 y 轴正方向的夹角
        double refLineAngle = angleToNorth(
                referenceLine.getStartPoint().getX(),
                referenceLine.getStartPoint().getY(),
                referenceLine.getEndPoint().getX(),
                referenceLine.getEndPoint().getY()
        );
        if (refLineAngle == 0) {
            return null;
        }
        refLineAngle = Math.toDegrees(refLineAngle); // 弧度转角度
        double maxAngle= refLineAngle + 180;
        // 计算顶边向量与 y 轴正方向的夹角
        double feaLineAngle = angleToNorth(
                featureLine.getStartPoint().getX(),
                featureLine.getStartPoint().getY(),
                featureLine.getEndPoint().getX(),
                featureLine.getEndPoint().getY()
        );
        if (feaLineAngle == 0) {
            return null;
        }
        feaLineAngle = Math.toDegrees(feaLineAngle); // 弧度转角度
    
        // 判断 feaLineAngle 是否在 ref + 180 范围内,
        //  如果在,说明在观察者视角,标牌顶边向量是指向右侧的,即顺时针
        if (feaLineAngle > refLineAngle && feaLineAngle < maxAngle) {
            return true;
        }
        // 如果 ref 向量顺时针转了 180 度后超过了 360,则回转 360 度再判断一次
        int circle = 360;
        if (maxAngle > circle) {
            return feaLineAngle > refLineAngle - circle && feaLineAngle < maxAngle - circle;
        }
        return false;
    }
    
    /**
     * 判断两条线是否平行
     * @param l1 线 1
     * @param l2 线 2
     * @param threshold 阈值
     * @return 结果
     */
    private static boolean isParallel(LineString l1, LineString l2, int threshold) {
        // 计算夹角,然后判断
        double angle = angle(l1.getStartPoint(), l1.getEndPoint(), l2.getStartPoint(), l2.getEndPoint());
        if (angle < 0) {
            angle += 360;
        }
        if (angle > 180) {
            angle = 360 - angle;
        }
        return angle < threshold || angle > (180 - threshold);
    }
    
    /**
     * 计算两个有向线段之间的夹角度数
     * @param p0 线段 1 首点
     * @param p1 线段 1 尾点
     * @param p2 线段 2 首点
     * @param p3 线段 2 尾点
     * @return 角度
     */
    private static double angle(Point p0, Point p1, Point p2, Point p3) {
        GeometryFactory geometryFactory = new GeometryFactory();
        // 通过坐标差,得到这两个线段的向量
        Point vector1 = geometryFactory.createPoint(new Coordinate(p1.getX() - p0.getX(), p1.getY() - p0.getY()));
        Point vector2 = geometryFactory.createPoint(new Coordinate(p3.getX() - p2.getX(), p3.getY() - p2.getY()));
        // 通过叉乘计算正弦与模的乘积
        double sin = vector1.getX() * vector2.getY() - vector2.getX() * vector1.getY();
        // 通过点乘计算余弦与模的乘积
        double cos = vector1.getX() * vector2.getX() + vector1.getY() * vector2.getY();
        // 计算夹角弧度,并转换为角度
        //  (因为内部会计算 sin 与 cos 比值,所以向量模长不影响结果)
        return Math.atan2(sin, cos) * 57.29577951308232D;
    }
    
    /**
     * 计算向量与 y 坐标轴正方向的顺时针夹角(单位弧度)
     * @param dx0 向量首点 X
     * @param dy0 向量首点 Y
     * @param dx1 向量尾点 X
     * @param dy1 向量尾点 Y
     * @return 弧度
     */
    private static double angleToNorth(double dx0, double dy0, double dx1, double dy1) {
        // 将向量起点移动到坐标原点
        double x = dx1 - dx0;
        double y = dy1 - dy0;
    
        if (Math.abs(x) < 1.0E-10D && y > 0.0D) {
            // 如果向量几乎与 y 轴正方向重合,则夹角为弧度 0
            return 0.0;
        } else if (Math.abs(x) < 1.0E-10D && y < 0.0D) {
            // 如果向量几乎与 y 轴负方向重合,则夹角为 π
            return 3.141592653589793D;
        } else if (Math.abs(y) < 1.0E-10D && x > 0.0D) {
            // 如果向量几乎与 x 轴正方向重合,则夹角为 90 度
            return 1.5707963267948966D;
        } else if (Math.abs(y) < 1.0E-10D && x < 0.0D) {
            // 如果向量几乎与 x 轴负方向重合,则夹角为 270 度
            return 4.71238898038469D;
        } else { // 普通情况,只能计算了
            double alpha = Math.atan(Math.abs(y / x));
            double beta = -1.0D;
            if (x > 0.0D && y > 0.0D) {
                // 第一象限,向量与 y 轴正方向夹角为 90 度 - alpha
                beta = 1.5707963267948966D - alpha;
            } else if (x < 0.0D && y > 0.0D) {
                // 第二象限,向量与 y 轴正方向夹角为 270 度 + alpha
                beta = 4.71238898038469D + alpha;
            } else if (x < 0.0D && y < 0.0D) {
                // 第三象限,向量与 y 轴正方向夹角为 270 度 - alpha
                beta = 4.71238898038469D - alpha;
            } else if (x > 0.0D && y < 0.0D) {
                // 第四象限,向量与 y 轴正方向夹角为 90 度 + alpha
                beta = 1.5707963267948966D + alpha;
            }
            return beta;
        }
    }

至此,本文的主要内容就介绍完了。

0%