1from __future__ import print_function, division, absolute_import 2from __future__ import unicode_literals 3from fontTools.misc.py23 import * 4 5 6def iup_segment(coords, rc1, rd1, rc2, rd2): 7 # rc1 = reference coord 1 8 # rd1 = reference delta 1 9 out_arrays = [None, None] 10 for j in 0,1: 11 out_arrays[j] = out = [] 12 x1, x2, d1, d2 = rc1[j], rc2[j], rd1[j], rd2[j] 13 14 15 if x1 == x2: 16 n = len(coords) 17 if d1 == d2: 18 out.extend([d1]*n) 19 else: 20 out.extend([0]*n) 21 continue 22 23 if x1 > x2: 24 x1, x2 = x2, x1 25 d1, d2 = d2, d1 26 27 # x1 < x2 28 scale = (d2 - d1) / (x2 - x1) 29 for pair in coords: 30 x = pair[j] 31 32 if x <= x1: 33 d = d1 34 elif x >= x2: 35 d = d2 36 else: 37 # Interpolate 38 d = d1 + (x - x1) * scale 39 40 out.append(d) 41 42 return zip(*out_arrays) 43 44def iup_contour(delta, coords): 45 assert len(delta) == len(coords) 46 if None not in delta: 47 return delta 48 49 n = len(delta) 50 # indices of points with explicit deltas 51 indices = [i for i,v in enumerate(delta) if v is not None] 52 if not indices: 53 # All deltas are None. Return 0,0 for all. 54 return [(0,0)]*n 55 56 out = [] 57 it = iter(indices) 58 start = next(it) 59 if start != 0: 60 # Initial segment that wraps around 61 i1, i2, ri1, ri2 = 0, start, start, indices[-1] 62 out.extend(iup_segment(coords[i1:i2], coords[ri1], delta[ri1], coords[ri2], delta[ri2])) 63 out.append(delta[start]) 64 for end in it: 65 if end - start > 1: 66 i1, i2, ri1, ri2 = start+1, end, start, end 67 out.extend(iup_segment(coords[i1:i2], coords[ri1], delta[ri1], coords[ri2], delta[ri2])) 68 out.append(delta[end]) 69 start = end 70 if start != n-1: 71 # Final segment that wraps around 72 i1, i2, ri1, ri2 = start+1, n, start, indices[0] 73 out.extend(iup_segment(coords[i1:i2], coords[ri1], delta[ri1], coords[ri2], delta[ri2])) 74 75 assert len(delta) == len(out), (len(delta), len(out)) 76 return out 77 78def iup_delta(delta, coords, ends): 79 assert sorted(ends) == ends and len(coords) == (ends[-1]+1 if ends else 0) + 4 80 n = len(coords) 81 ends = ends + [n-4, n-3, n-2, n-1] 82 out = [] 83 start = 0 84 for end in ends: 85 end += 1 86 contour = iup_contour(delta[start:end], coords[start:end]) 87 out.extend(contour) 88 start = end 89 90 return out 91 92# Optimizer 93 94def can_iup_in_between(deltas, coords, i, j, tolerance): 95 assert j - i >= 2 96 interp = list(iup_segment(coords[i+1:j], coords[i], deltas[i], coords[j], deltas[j])) 97 deltas = deltas[i+1:j] 98 99 assert len(deltas) == len(interp) 100 101 return all(abs(complex(x-p, y-q)) <= tolerance for (x,y),(p,q) in zip(deltas, interp)) 102 103def _iup_contour_bound_forced_set(delta, coords, tolerance=0): 104 """The forced set is a conservative set of points on the contour that must be encoded 105 explicitly (ie. cannot be interpolated). Calculating this set allows for significantly 106 speeding up the dynamic-programming, as well as resolve circularity in DP. 107 108 The set is precise; that is, if an index is in the returned set, then there is no way 109 that IUP can generate delta for that point, given coords and delta. 110 """ 111 assert len(delta) == len(coords) 112 113 forced = set() 114 # Track "last" and "next" points on the contour as we sweep. 115 nd, nc = delta[0], coords[0] 116 ld, lc = delta[-1], coords[-1] 117 for i in range(len(delta)-1, -1, -1): 118 d, c = ld, lc 119 ld, lc = delta[i-1], coords[i-1] 120 121 for j in (0,1): # For X and for Y 122 cj = c[j] 123 dj = d[j] 124 lcj = lc[j] 125 ldj = ld[j] 126 ncj = nc[j] 127 ndj = nd[j] 128 129 if lcj <= ncj: 130 c1, c2 = lcj, ncj 131 d1, d2 = ldj, ndj 132 else: 133 c1, c2 = ncj, lcj 134 d1, d2 = ndj, ldj 135 136 # If coordinate for current point is between coordinate of adjacent 137 # points on the two sides, but the delta for current point is NOT 138 # between delta for those adjacent points (considering tolerance 139 # allowance), then there is no way that current point can be IUP-ed. 140 # Mark it forced. 141 force = False 142 if c1 <= cj <= c2: 143 if not (min(d1,d2)-tolerance <= dj <= max(d1,d2)+tolerance): 144 force = True 145 else: # cj < c1 or c2 < cj 146 if c1 == c2: 147 if d1 == d2: 148 if abs(dj - d1) > tolerance: 149 force = True 150 else: 151 if abs(dj) > tolerance: 152 # Disabled the following because the "d1 == d2" does 153 # check does not take tolerance into consideration... 154 pass # force = True 155 elif d1 != d2: 156 if cj < c1: 157 if dj != d1 and ((dj-tolerance < d1) != (d1 < d2)): 158 force = True 159 else: # c2 < cj 160 if d2 != dj and ((d2 < dj+tolerance) != (d1 < d2)): 161 force = True 162 163 if force: 164 forced.add(i) 165 break 166 167 nd, nc = d, c 168 169 return forced 170 171def _iup_contour_optimize_dp(delta, coords, forced={}, tolerance=0, lookback=None): 172 """Straightforward Dynamic-Programming. For each index i, find least-costly encoding of 173 points 0 to i where i is explicitly encoded. We find this by considering all previous 174 explicit points j and check whether interpolation can fill points between j and i. 175 176 Note that solution always encodes last point explicitly. Higher-level is responsible 177 for removing that restriction. 178 179 As major speedup, we stop looking further whenever we see a "forced" point.""" 180 181 n = len(delta) 182 if lookback is None: 183 lookback = n 184 costs = {-1:0} 185 chain = {-1:None} 186 for i in range(0, n): 187 best_cost = costs[i-1] + 1 188 189 costs[i] = best_cost 190 chain[i] = i - 1 191 192 if i - 1 in forced: 193 continue 194 195 for j in range(i-2, max(i-lookback, -2), -1): 196 197 cost = costs[j] + 1 198 199 if cost < best_cost and can_iup_in_between(delta, coords, j, i, tolerance): 200 costs[i] = best_cost = cost 201 chain[i] = j 202 203 if j in forced: 204 break 205 206 return chain, costs 207 208def _rot_list(l, k): 209 """Rotate list by k items forward. Ie. item at position 0 will be 210 at position k in returned list. Negative k is allowed.""" 211 n = len(l) 212 k %= n 213 if not k: return l 214 return l[n-k:] + l[:n-k] 215 216def _rot_set(s, k, n): 217 k %= n 218 if not k: return s 219 return {(v + k) % n for v in s} 220 221def iup_contour_optimize(delta, coords, tolerance=0.): 222 n = len(delta) 223 224 # Get the easy cases out of the way: 225 226 # If all are within tolerance distance of 0, encode nothing: 227 if all(abs(complex(*p)) <= tolerance for p in delta): 228 return [None] * n 229 230 # If there's exactly one point, return it: 231 if n == 1: 232 return delta 233 234 # If all deltas are exactly the same, return just one (the first one): 235 d0 = delta[0] 236 if all(d0 == d for d in delta): 237 return [d0] + [None] * (n-1) 238 239 # Else, solve the general problem using Dynamic Programming. 240 241 forced = _iup_contour_bound_forced_set(delta, coords, tolerance) 242 # The _iup_contour_optimize_dp() routine returns the optimal encoding 243 # solution given the constraint that the last point is always encoded. 244 # To remove this constraint, we use two different methods, depending on 245 # whether forced set is non-empty or not: 246 247 if forced: 248 # Forced set is non-empty: rotate the contour start point 249 # such that the last point in the list is a forced point. 250 k = (n-1) - max(forced) 251 assert k >= 0 252 253 delta = _rot_list(delta, k) 254 coords = _rot_list(coords, k) 255 forced = _rot_set(forced, k, n) 256 257 chain, costs = _iup_contour_optimize_dp(delta, coords, forced, tolerance) 258 259 # Assemble solution. 260 solution = set() 261 i = n - 1 262 while i is not None: 263 solution.add(i) 264 i = chain[i] 265 assert forced <= solution, (forced, solution) 266 delta = [delta[i] if i in solution else None for i in range(n)] 267 268 delta = _rot_list(delta, -k) 269 else: 270 # Repeat the contour an extra time, solve the 2*n case, then look for solutions of the 271 # circular n-length problem in the solution for 2*n linear case. I cannot prove that 272 # this always produces the optimal solution... 273 chain, costs = _iup_contour_optimize_dp(delta+delta, coords+coords, forced, tolerance, n) 274 best_sol, best_cost = None, n+1 275 276 for start in range(n-1, 2*n-1): 277 # Assemble solution. 278 solution = set() 279 i = start 280 while i > start - n: 281 solution.add(i % n) 282 i = chain[i] 283 if i == start - n: 284 cost = costs[start] - costs[start - n] 285 if cost <= best_cost: 286 best_sol, best_cost = solution, cost 287 288 delta = [delta[i] if i in best_sol else None for i in range(n)] 289 290 291 return delta 292 293def iup_delta_optimize(delta, coords, ends, tolerance=0.): 294 assert sorted(ends) == ends and len(coords) == (ends[-1]+1 if ends else 0) + 4 295 n = len(coords) 296 ends = ends + [n-4, n-3, n-2, n-1] 297 out = [] 298 start = 0 299 for end in ends: 300 contour = iup_contour_optimize(delta[start:end+1], coords[start:end+1], tolerance) 301 assert len(contour) == end - start + 1 302 out.extend(contour) 303 start = end+1 304 305 return out 306