作者dataiann (DaTaiAnn)
看板Programming
标题[问题] 找路径的演算法
时间Thu Oct 23 22:04:17 2008
问题 :
假设有类似下面的三块多边形，要找出图中的 6 个 x 所连成的路径得长度与宽度。
多边形经过排序过，排序是依据左边的座标，如果相等，再依据底部的座标。
读入的顺序会是，最上面那块->最下面那块->中间那块
(这边画三个只是举例子)
我想到得是用 scanline 从左扫到右边，但问题是，比如第一块(最上面那块)，
一开始怎麽决定他的方向是往右或是上下 ?
(因为 scanline 在最下面那块读进来时，就需要处理之前的资料，不然，要等所有
相同座标的资料都读进来，多边形的数量可能会很大)。
或者是除了用 scanline 之外，有没有其他方法?
+--------+
x x |
+----+-x-+
| |
+-x-+--------+
| x x
+------------+
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 118.160.223.7
※ 编辑: dataiann 来自: 118.160.223.7 (10/23 22:05)