potrace笔记

破晓

原文地址：http://www.blogbus.com/linxinboy-logs/270323157.html
以下是potrace算法2.2.1节笔记，  主要是对算法中calc_lon函数的解释，
potrace的代码相当难阅读， 只有看过代码的同学才知道以下有何意义。

笔记 potrace 2.2.1节
原始像素点

分解后的path   由于保证路径左边有一个黑色像素  所以路径 为 下 右 上 左



数据



加上pivot



为了计算惩罚，我们将多边形的顶点 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



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(或左右) 范围内的点。