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)