掃街地圖 (Street Sweep Map)

將各縣市門牌座標資料轉換為掃街路線，以最近鄰居演算法規劃路徑，產生可在地圖上瀏覽的 GeoJSON 路線檔案。

資料處理流程

raw/*.csv, *.xlsx
       │
       ▼
  ┌─────────────┐
  │ 1. 讀取與正規化  │  自動偵測編碼 (UTF-8/BIG5/CP950)，統一不同欄位名稱
  └──────┬──────┘
         ▼
  ┌─────────────┐
  │ 2. 去重複      │  以「街路段＋地區＋巷＋弄＋號」為鍵，每個地址只保留一筆
  └──────┬──────┘
         ▼
  ┌─────────────┐
  │ 3. 座標轉換    │  TWD97 (EPSG:3826) → WGS84 (EPSG:4326)
  └──────┬──────┘
         ▼
  ┌─────────────┐
  │ 4. 路徑規劃    │  KDTree 加速的最近鄰居 TSP，依鄉鎮市區分組
  └──────┬──────┘
         ▼
  ┌─────────────┐
  │ 5. 線段簡化    │  Douglas-Peucker 演算法，ε=0.00005° (約 5 公尺)
  └──────┬──────┘
         ▼
  ┌─────────────┐
  │ 6. 分段輸出    │  每段 ≤ 15 km（自行車約一小時），輸出 GeoJSON
  └──────┬──────┘
         ▼
  output/<city>/<district_code>.geojson

步驟說明

1. 讀取與欄位正規化

各縣市的原始資料欄位名稱不一致，程式透過 COLUMN_MAP 字典統一對應：

正規化欄位	原始欄位變體
district	鄉鎮市區代碼、areacode、districtCode
street	街、路段、街路段、街或路段、街_路段、street、road、section、街（路段）
number	號、號樓、number、houseNumber
x	橫座標、橫坐標、TWD97橫坐標、x_3826、coordinateX
y	縱座標、縱坐標、TWD97縱坐標、y_3826、coordinateY
address	地址（新竹市為合併欄位，無獨立街路段）

檔案編碼依序嘗試 UTF-8-SIG → BIG5 → CP950，若全部失敗則以 errors='replace' 模式重試（處理編碼混亂的檔案如新竹縣）。

多檔案城市（如雲林 yunlin_1.xlsx ~ yunlin_3.xlsx）會自動合併。

2. 地址去重複

同一門牌號（截斷至「號」字）的多筆資料（如不同樓層）只保留第一筆座標，避免路線在同一棟建築上重複繞行。

3. TWD97 → WGS84 座標轉換

原始資料使用 TWD97 二度分帶（EPSG:3826）投影座標。程式實作完整的橫麥卡托逆轉換公式，將橫座標 (E) 與縱座標 (N) 轉為 WGS84 經緯度，中央經線 121°E，尺度因子 0.9999。

4. 最近鄰居路徑規劃 (Nearest-Neighbor TSP)

每個鄉鎮市區的門牌點位獨立規劃路線：

1. 以所有點位的 TWD97 座標建立 KDTree
2. 從第一個點出發，每次查詢最近的 32 個鄰居，選擇尚未拜訪的最近點
3. 若 32 個鄰居都已拜訪，退回暴力搜尋剩餘點位
4. 重複直到所有點位都被拜訪

此為貪婪近似解，非最佳解，但對數萬至數十萬點位的規模能在數秒內完成。

5. Douglas-Peucker 線段簡化

路徑規劃後，許多相鄰門牌座標非常接近（同一條巷子內間距僅數公尺），在地圖上顯示時不需要這麼高的精度。

使用 Douglas-Peucker 演算法移除「偏離直線不超過 ε」的中間點：

• ε = 0.00005°，在台灣緯度約等於 5 公尺
• 使用迭代（非遞迴）實作，避免大量點位時的遞迴深度限制
• 比較時使用距離平方避免開根號，提升效能

典型壓縮率：都市密集區保留 2035%，鄉村區保留 5075%。整體輸出從 120 MB 降至 43 MB。

6. 分段與 GeoJSON 輸出

簡化後的路線以 Haversine 公式計算累積距離，每累積 15 km 切割為一段（自行車時速 15 km/h 約一小時的路程）。每段至少包含 2 個點位。

輸出為 GeoJSON FeatureCollection，每個 Feature 為一段 LineString，屬性包含：

• district：鄉鎮市區代碼
• segment：段序號
• total_segments：該區總段數
• km：該段距離（公里）

目錄結構

map_cover/
├── raw/                        # 原始門牌座標資料 (868 MB)
│   ├── taipei.csv
│   ├── kaohsiung.csv
│   ├── yunlin_1.xlsx           # 多檔案會自動合併
│   ├── yunlin_2.xlsx
│   ├── yunlin_3.xlsx
│   └── ...                     # 共 19 個檔案，涵蓋 17 個縣市
├── scripts/
│   ├── generate_all.py         # 產生掃街路線 GeoJSON
│   └── generate_csv.py         # 產生統一格式 CSV
├── data/                       # 統一格式 CSV (generate_csv.py 產出)
│   ├── taipei/
│   │   ├── 63000010.csv
│   │   └── ...
│   └── .../
├── docs/                       # 網頁與產出資料（可直接部署為靜態網站）
│   ├── index.html              # 地圖瀏覽介面
│   └── output/                 # 產出的 GeoJSON (43 MB, 330 個檔案)
│       ├── taipei/
│       │   ├── 63000010.geojson    # 松山區
│       │   ├── 63000020.geojson    # 信義區
│       │   └── ...
│       ├── kaohsiung/
│       │   └── ...
│       └── .../
└── README.md

使用方式

產生路線資料

pip install numpy scipy openpyxl
python3 scripts/generate_all.py

處理 17 個縣市約需 2~3 分鐘，產出寫入 docs/output/。

產生統一格式 CSV

python3 scripts/generate_csv.py

將各縣市不同格式的原始資料統一為 UTF-8 CSV，依鄉鎮市區分檔輸出至 data/<city>/<district_code>.csv。

統一欄位：city_code, district_code, village, neighbor, street, area, lane, alley, number, address, x, y

此步驟不做去重複或座標轉換，保留原始資料完整內容。

瀏覽地圖

以任意 HTTP 伺服器開啟 docs/ 目錄：

cd docs
python3 -m http.server 8000
# 瀏覽 http://localhost:8000

介面功能：

• 左側面板選擇縣市與行政區
• 搜尋欄支援縣市名與區域名
• 點擊路線段落或使用底部導覽列切換段落
• 每段路線顯示起點（綠色）、終點（紅色）及行進方向箭頭
• 支援 URL hash 直連，如 #tainan/6700100

涵蓋縣市

縣市	行政區數	原始筆數
臺北市	12	1,154,424
新北市	29	1,982,870
桃園市	13	1,081,316
新竹市	3	210,396
新竹縣	13	262,762
苗栗縣	18	226,617
臺中市	29	1,292,650
彰化縣	26	467,023
雲林縣	20	283,980
嘉義縣	18	198,697
臺南市	37	847,103
高雄市	38	1,275,343
屏東縣	33	327,457
臺東縣	16	93,671
花蓮縣	13	151,358
澎湖縣	6	40,609
金門縣	6	32,005

相依套件

• Python 3.8+
• NumPy
• SciPy（KDTree）
• openpyxl（讀取 xlsx）
• Leaflet 1.9.4（前端地圖，由 CDN 載入）