GPS坐标下的线段相交检测问题

嘿，我刚好有个不用计算交点的简便方法——用方向叉积法，这是计算几何里判断线段相交的经典思路，完全不用求交点，只靠判断点相对于线段的位置就能搞定。

核心原理 #

两条线段AB和CD相交的充要条件是以下两种情况之一：

1. 互相跨越：点C、D分别在AB线段所在直线的两侧，同时点A、B分别在CD线段所在直线的两侧；
2. 端点共线：其中一条线段的某个端点恰好落在另一条线段上（比如点C在AB上，或者点A在CD上）。

我们可以通过叉积运算来判断点相对于线段的位置，叉积的正负能告诉我们点在直线的左侧、右侧还是共线。

Swift 实现代码 #

首先，我们基于CLLocationCoordinate2D实现几个辅助函数：

import CoreLocation

// 计算三个点的叉积：用于判断点r相对于线段pq的位置
private func crossProduct(p: CLLocationCoordinate2D, q: CLLocationCoordinate2D, r: CLLocationCoordinate2D) -> Double {
    // 注意：经纬度对应平面坐标的y和x
    let qxMinusPx = q.longitude - p.longitude
    let ryMinusPy = r.latitude - p.latitude
    let qyMinusPy = q.latitude - p.latitude
    let rxMinusPx = r.longitude - p.longitude
    
    return qxMinusPx * ryMinusPy - qyMinusPy * rxMinusPx
}

// 判断点p是否在线段qr上
private func pointOnSegment(p: CLLocationCoordinate2D, q: CLLocationCoordinate2D, r: CLLocationCoordinate2D) -> Bool {
    // 先判断是否共线（叉积为0），再判断点的坐标是否在线段的范围内
    guard crossProduct(p: q, q: r, r: p) == 0 else { return false }
    
    let minLon = min(q.longitude, r.longitude)
    let maxLon = max(q.longitude, r.longitude)
    let minLat = min(q.latitude, r.latitude)
    let maxLat = max(q.latitude, r.latitude)
    
    return (p.longitude >= minLon && p.longitude <= maxLon) && (p.latitude >= minLat && p.latitude <= maxLat)
}

// 核心函数：判断两条线段AB和CD是否相交
func doSegmentsIntersect(a: CLLocationCoordinate2D, b: CLLocationCoordinate2D, c: CLLocationCoordinate2D, d: CLLocationCoordinate2D) -> Bool {
    let cross1 = crossProduct(p: a, q: b, r: c)
    let cross2 = crossProduct(p: a, q: b, r: d)
    let cross3 = crossProduct(p: c, q: d, r: a)
    let cross4 = crossProduct(p: c, q: d, r: b)
    
    // 情况1：两条线段互相跨越对方的直线
    let segmentsCrossEachOther = (cross1 * cross2 < 0) && (cross3 * cross4 < 0)
    
    // 情况2：某个端点落在另一条线段上
    let pointOnSegment = pointOnSegment(p: c, q: a, r: b) ||
                         pointOnSegment(p: d, q: a, r: b) ||
                         pointOnSegment(p: a, q: c, r: d) ||
                         pointOnSegment(p: b, q: c, r: d)
    
    return segmentsCrossEachOther || pointOnSegment
}

使用示例 #

// 定义两条测试线段
let seg1A = CLLocationCoordinate2D(latitude: 39.9042, longitude: 116.4074) // 北京天安门
let seg1B = CLLocationCoordinate2D(latitude: 31.2304, longitude: 121.4737) // 上海外滩
let seg2C = CLLocationCoordinate2D(latitude: 34.3416, longitude: 108.9398) // 西安大雁塔
let seg2D = CLLocationCoordinate2D(latitude: 30.2741, longitude: 120.1551) // 杭州西湖

let isIntersecting = doSegmentsIntersect(a: seg1A, b: seg1B, c: seg2C, d: seg2D)
print("线段是否相交：\(isIntersecting)")

注意事项 #

• 这个方法是平面近似，适合小范围的线段（比如城市内的路径）。如果你的线段跨越大范围（比如跨半球），经纬度的球面特性会导致误差，这时候需要用球面几何的线段相交判断，但复杂度会高一些。
• 代码中叉积的计算直接用经纬度作为平面坐标，没有做投影转换，小范围内精度足够。如果需要更高精度，可以先把经纬度转换为墨卡托投影坐标再计算。

内容的提问来源于stack exchange，提问作者pikciu