[attach]472[/attach]
分解后的path 由于保证路径左边有一个黑色像素 所以路径 为 下 右 上 左
[attach]473[/attach]
数据
[attach]474[/attach]
加上pivot
[attach]475[/attach]
为了计算惩罚，我们将多边形的顶点 i 精确地放置于对应路径的点vi，即在坐标系有整型坐标的点。
故 算法中用的仍然是整型坐标， 2.2.1节
关键
从点i 找到一个 点 k 使得 vi 到 vk 中间的 所有点 vj 到 此直线的距离 d(vj, w) 都 <=1 此距离 为 max(disx, disy);
2.2.1节求的是 分解后的 path 每个节点 所能够到达的 最远 点k 仍满足d(vj, w) <=1 的 privot
示例 当i = 6
[attach]476[/attach]
k = 0 方向 左 cur = (-4, 0) constaint0 = (-3, 1) constaint1 = (-3, -1)
k = 1 方向 下 cur = (-4, 1) constaint0 = (-3, 1) constaint1 = (-5, 0) new constaint0 = (-3, 2) 没有比旧constriant0更接近 cur 故舍弃
k = 5 方向 右 cur = (0, 1) xprod(constraint[0], cur) < 0 break; 即超出constaint1 范围 故 break
简单来说 求每个点i 能够最远到达的点k 即 求第一次 的 cur 在此 cur 上下 + -1(或左右) 范围内的点。