作者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