Android Kotlin中求线段与简单闭合多边形的最近交点

1. 基础工具实现 #

基于Android自带的LatLng类，先实现两个核心工具方法：线段交点计算、坐标距离计算，用于后续逻辑处理。

import android.location.Location
import com.google.android.gms.maps.model.LatLng

// 判断点是否在线段范围内（处理浮点精度问题）
private fun isPointOnSegment(p: LatLng, a: LatLng, b: LatLng): Boolean {
    // 叉积验证是否在直线上
    val cross = (p.latitude - a.latitude) * (b.longitude - a.longitude) - 
                (p.longitude - a.longitude) * (b.latitude - a.latitude)
    if (cross.absoluteValue > 1e-6) return false

    // 验证是否在线段的边界范围内
    val minLat = minOf(a.latitude, b.latitude)
    val maxLat = maxOf(a.latitude, b.latitude)
    val minLng = minOf(a.longitude, b.longitude)
    val maxLng = maxOf(a.longitude, b.longitude)
    
    return p.latitude in (minLat - 1e-6)..(maxLat + 1e-6) && 
           p.longitude in (minLng - 1e-6)..(maxLng + 1e-6)
}

// 计算两条线段AB与CD的交点，无交点则返回null
private fun getSegmentIntersection(a: LatLng, b: LatLng, c: LatLng, d: LatLng): LatLng? {
    val denominator = (b.latitude - a.latitude) * (d.longitude - c.longitude) - 
                      (b.longitude - a.longitude) * (d.latitude - c.latitude)
    if (denominator.absoluteValue < 1e-6) return null // 线段平行或重合

    val t = ((a.longitude - c.longitude) * (d.latitude - c.latitude) - 
             (a.latitude - c.latitude) * (d.longitude - c.longitude)) / denominator
    val u = -((a.longitude - c.longitude) * (b.latitude - a.latitude) - 
              (a.latitude - c.latitude) * (b.longitude - a.longitude)) / denominator

    // t和u都在[0,1]区间内，说明线段相交
    if (t in 0.0..1.0 && u in 0.0..1.0) {
        val intersectLat = a.latitude + t * (b.latitude - a.latitude)
        val intersectLng = a.longitude + t * (b.longitude - a.longitude)
        val intersectPoint = LatLng(intersectLat, intersectLng)
        
        return if (isPointOnSegment(intersectPoint, a, b) && isPointOnSegment(intersectPoint, c, d)) {
            intersectPoint
        } else null
    }
    return null
}

// 计算两个地理坐标的直线距离（单位：米）
private fun calculateDistance(start: LatLng, end: LatLng): Float {
    val results = FloatArray(1)
    Location.distanceBetween(start.latitude, start.longitude, end.latitude, end.longitude, results)
    return results[0]
}

2. 核心逻辑：寻找最近交点 #

遍历多边形的每条闭合边，收集所有与目标线段的交点，再筛选出离线段起点最近的点。

fun findClosestIntersection(segmentStart: LatLng, segmentEnd: LatLng, polygonPoints: List<LatLng>): LatLng? {
    if (polygonPoints.size < 3) return null // 多边形至少需要3个顶点

    val intersections = mutableListOf<LatLng>()

    // 遍历所有多边形边（含最后一个顶点到第一个顶点的闭合边）
    for (i in polygonPoints.indices) {
        val polyA = polygonPoints[i]
        val polyB = polygonPoints[(i + 1) % polygonPoints.size]
        
        getSegmentIntersection(segmentStart, segmentEnd, polyA, polyB)?.let {
            intersections.add(it)
        }
    }

    // 返回距离起点最近的交点
    return intersections.minByOrNull { calculateDistance(segmentStart, it) }
}

3. 注意事项 #

• 适用场景：上述算法基于平面几何近似，适合小范围（如城市级）的多边形计算。如果需要处理跨区域的大范围场景，建议先将经纬度投影到UTM平面坐标系，计算完成后再转换回地理坐标。
• 精度调整：可根据需求修改代码中的1e-6阈值，适配不同的浮点精度要求。
• Turf Java补充：如果后续继续使用Turf，可调用其线段相交API替代上述getSegmentIntersection方法，核心的多边形边遍历、最近点筛选逻辑保持一致。

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