路樁號轉經緯度算法實現：二分查找 + 相似三角形插值

問題定義

公路工程以「樁號」(里程標識) 定位空間位置。需將任意樁號轉換為對應的經緯度座標，以支援 GIS 定位、導航等功能。

核心原理

1. 路線數據為有序節點列表，每節點含 mile (樁號)、x (經度)、y (緯度)。
2. 目標樁號必落在兩相鄰節點之間 (或延長線上)。
3. 以二分查找 O(log n) 定位相鄰節點 P1(mile1, x1, y1)、P2(mile2, x2, y2)。
4. 利用相似三角形線性插值計算目標座標：

k = (mile - mile1) / (mile2 - mile1)
x = x1 + (x2 - x1) * k
y = y1 + (y2 - y1) * k

關鍵代碼實現 (Java)

1. 二分查找相鄰節點

private static Point[] getNeighborPoint(List<Point> list, double mile) {
    Point[] pt = new Point[2];
    Point first = list.get(0);
    Point last = list.get(list.size() - 1);

    if (mile <= first.getMile()) { pt[0] = pt[1] = first; }
    else if (mile >= last.getMile()) { pt[0] = pt[1] = last; }
    else {
        int start = 0, end = list.size() - 1;
        while (true) {
            int mid = (start + end) / 2;
            Point midPt = list.get(mid);
            if (midPt.getMile() > mile) {
                Point prev = list.get(mid - 1);
                if (prev.getMile() < mile) { pt[0] = prev; pt[1] = midPt; break; }
                else end = mid;
            } else if (midPt.getMile() < mile) {
                Point next = list.get(mid + 1);
                if (next.getMile() > mile) { pt[0] = midPt; pt[1] = next; break; }
                else start = mid;
            } else { pt[0] = pt[1] = midPt; break; }
        }
    }
    return pt;
}

2. 線性插值計算座標

private static Point getLocation(Point p1, Point p2, double mile) {
    double dMile = p2.getMile() - p1.getMile();
    if (dMile == 0) return p1;
    double k = (mile - p1.getMile()) / dMile;
    double x = p1.getX() + (p2.getX() - p1.getX()) * k;
    double y = p1.getY() + (p2.getY() - p1.getY()) * k;
    return new Point(x, y, mile);
}

特殊情況處理清單

• 目標樁號 ≤ 起點樁號 → 回傳起點座標。
• 目標樁號 ≥ 終點樁號 → 回傳終點座標。
• 相鄰節點樁號相同 (dMile=0) → 直接回傳第一節點，避免除零。
• 路線節點列表為空或僅一點 → 業務層攔截拋異常。

區別提醒：樁號→經緯度 vs 經緯度→樁號

本文解決「樁號→經緯度」：二分查找相鄰節點 + 線性插值。
反向「經緯度→樁號」：需計算點到多條線段的最短垂足距離，屬完全不同的幾何問題，切勿混淆。