e作者gwliao (gwliao)
看板Prob_Solve
標題Re: [問題] 請問多邊形合併
時間Sat Sep 16 21:29:57 2006
※ 引述《gwliao (gwliao)》之銘言：
: ※ 引述《fredfrost (幸福就是妳)》之銘言：
續前篇............
: : ┌───┬───┐ ┌───┬───┐
: : │┌──┴──┐│ │┌──┴──┐│
: : ┌──┴┴┐ ││ ┌──┘└┐ ││
: : │ ├────┘│ ＝ │ └────┘│
: : │ ├─────┘ │ ┌─────┘
: : │ │ │ │
: : └────┘ └────┘
只留下垂直線段:
| || |
| | | |
| | | | | |
| | | |
| |
| |
然後由左到右掃:
本來想畫圖, 但我失敗了. Q_Q
你可以去找Computational Geometry的書, 找Line sweep.
做polygon的OR operation只要O(n*log n)的時間.
補充一下: 我是指這種只有水平垂直的polygon.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.230.223
※ 編輯: gwliao 來自: 140.112.230.223 (09/17 03:34)