Re: [問題] 請問多邊形合併
看板Prob_Solve (計算數學 Problem Solving)作者gwliao時間18年前 (2006/09/16 21:06)推噓0(0推 0噓 0→)留言0則, 0人參與討論串3/3 (看更多)
※ 引述《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)
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
