作者gwliao (gwliao)
看板Prob_Solve
標題Re: [問題] 請問多邊形合併
時間Sat Sep 16 14:55:27 2006
※ 引述《fredfrost (幸福就是妳)》之銘言：
: 請問假如說有兩個多邊形
: 資料只有每個點的位置 跟連線順序 但為非向量邊
: 也就是 沒固定要順時鐘或逆時鐘繞
: 而且允許空心圖形 如下
: ┌───┬───┐
: │┌──┴──┐│
: ││ ││
: │└─────┘│
: └───────┘
依序走一次就知道是順時鐘或逆時鐘繞.
我自己會將point list轉成逆時鐘繞.
(這是我的習慣, 但一定要有習慣. XD )
: 當兩多邊形要合併時 要怎麼來實現他呢
: 例如：
: ┌───┬───┐ ┌───┬───┐
: │┌──┴──┐│ │┌──┴──┐│
: ┌──┴┴┐ ││ ┌──┘└┐ ││
: │ ├────┘│ ＝ │ └────┘│
: │ ├─────┘ │ ┌─────┘
: │ │ │ │
: └────┘ └────┘
: 再更難一點：（雙線框為自定義看要怎麼切）
: ┌───┬───┐ ┌───┬───┐
: │┌──┴──┐│ │┌──┴──┐│
: ┌─┴┴─────┴┴─┐ ┌─┘└─────┘└─┐
: │ │ ＝ │ │
: └─┬┬─────┬┬─┘ └─┐┌─────┐┌─┘
: │└─────┘│ │└─────┘│
: └───────┘ └───────┘
: 有空心圖形 無法用點集合表示
我之前用的表達方式跟你不一樣.
我是用多個point list表示an polygon with hole.
逆時鐘繞的point list表外框,順時鐘繞的point list表內框.
這樣處理完就知道一些資料.
以垂直Edge來說:
Edge是由下往上, 表左邊沒東西, 右邊有.
由上往下,剛好相反.
內框和外框所形成的edge都有這性質.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.230.223
1F：推 yoco315:好方法耶 @@ 09/16 14:58
2F：推 gwliao:別客氣, 我剛好學過Computional Geometry, 剛好也做這件事. 09/16 21:30
3F：推 march20:那洞中洞怎麼辦@@ 09/18 16:23
4F：推 gwliao:那算另一個 polygon 或是另一個外框. 09/18 19:10