1from typing import ( 2 Sequence, 3 Tuple, 4 Union, 5) 6from numbers import ( 7 Integral, 8 Real 9) 10 11try: 12 import cython 13except ImportError: 14 # if cython not installed, use mock module with no-op decorators and types 15 from fontTools.misc import cython 16 17if cython.compiled: 18 # Yep, I'm compiled. 19 COMPILED = True 20else: 21 # Just a lowly interpreted script. 22 COMPILED = False 23 24 25_Point = Tuple[Real, Real] 26_Delta = Tuple[Real, Real] 27_PointSegment = Sequence[_Point] 28_DeltaSegment = Sequence[_Delta] 29_DeltaOrNone = Union[_Delta, None] 30_DeltaOrNoneSegment = Sequence[_DeltaOrNone] 31_Endpoints = Sequence[Integral] 32 33 34MAX_LOOKBACK = 8 35 36def iup_segment(coords : _PointSegment, 37 rc1 : _Point, 38 rd1 : _Delta, 39 rc2 : _Point, 40 rd2 : _Delta) -> _DeltaSegment: 41 """Given two reference coordinates `rc1` & `rc2` and their respective 42 delta vectors `rd1` & `rd2`, returns interpolated deltas for the set of 43 coordinates `coords`. """ 44 45 # rc1 = reference coord 1 46 # rd1 = reference delta 1 47 out_arrays = [None, None] 48 for j in 0,1: 49 out_arrays[j] = out = [] 50 x1, x2, d1, d2 = rc1[j], rc2[j], rd1[j], rd2[j] 51 52 if x1 == x2: 53 n = len(coords) 54 if d1 == d2: 55 out.extend([d1]*n) 56 else: 57 out.extend([0]*n) 58 continue 59 60 if x1 > x2: 61 x1, x2 = x2, x1 62 d1, d2 = d2, d1 63 64 # x1 < x2 65 scale = (d2 - d1) / (x2 - x1) 66 for pair in coords: 67 x = pair[j] 68 69 if x <= x1: 70 d = d1 71 elif x >= x2: 72 d = d2 73 else: 74 # Interpolate 75 d = d1 + (x - x1) * scale 76 77 out.append(d) 78 79 return zip(*out_arrays) 80 81def iup_contour(deltas : _DeltaOrNoneSegment, 82 coords : _PointSegment) -> _DeltaSegment: 83 """For the contour given in `coords`, interpolate any missing 84 delta values in delta vector `deltas`. 85 86 Returns fully filled-out delta vector.""" 87 88 assert len(deltas) == len(coords) 89 if None not in deltas: 90 return deltas 91 92 n = len(deltas) 93 # indices of points with explicit deltas 94 indices = [i for i,v in enumerate(deltas) if v is not None] 95 if not indices: 96 # All deltas are None. Return 0,0 for all. 97 return [(0,0)]*n 98 99 out = [] 100 it = iter(indices) 101 start = next(it) 102 if start != 0: 103 # Initial segment that wraps around 104 i1, i2, ri1, ri2 = 0, start, start, indices[-1] 105 out.extend(iup_segment(coords[i1:i2], coords[ri1], deltas[ri1], coords[ri2], deltas[ri2])) 106 out.append(deltas[start]) 107 for end in it: 108 if end - start > 1: 109 i1, i2, ri1, ri2 = start+1, end, start, end 110 out.extend(iup_segment(coords[i1:i2], coords[ri1], deltas[ri1], coords[ri2], deltas[ri2])) 111 out.append(deltas[end]) 112 start = end 113 if start != n-1: 114 # Final segment that wraps around 115 i1, i2, ri1, ri2 = start+1, n, start, indices[0] 116 out.extend(iup_segment(coords[i1:i2], coords[ri1], deltas[ri1], coords[ri2], deltas[ri2])) 117 118 assert len(deltas) == len(out), (len(deltas), len(out)) 119 return out 120 121def iup_delta(deltas : _DeltaOrNoneSegment, 122 coords : _PointSegment, 123 ends: _Endpoints) -> _DeltaSegment: 124 """For the outline given in `coords`, with contour endpoints given 125 in sorted increasing order in `ends`, interpolate any missing 126 delta values in delta vector `deltas`. 127 128 Returns fully filled-out delta vector.""" 129 130 assert sorted(ends) == ends and len(coords) == (ends[-1]+1 if ends else 0) + 4 131 n = len(coords) 132 ends = ends + [n-4, n-3, n-2, n-1] 133 out = [] 134 start = 0 135 for end in ends: 136 end += 1 137 contour = iup_contour(deltas[start:end], coords[start:end]) 138 out.extend(contour) 139 start = end 140 141 return out 142 143# Optimizer 144 145def can_iup_in_between(deltas : _DeltaSegment, 146 coords : _PointSegment, 147 i : Integral, 148 j : Integral, 149 tolerance : Real) -> bool: 150 """Return true if the deltas for points at `i` and `j` (`i < j`) can be 151 successfully used to interpolate deltas for points in between them within 152 provided error tolerance.""" 153 154 assert j - i >= 2 155 interp = list(iup_segment(coords[i+1:j], coords[i], deltas[i], coords[j], deltas[j])) 156 deltas = deltas[i+1:j] 157 158 assert len(deltas) == len(interp) 159 160 return all(abs(complex(x-p, y-q)) <= tolerance for (x,y),(p,q) in zip(deltas, interp)) 161 162def _iup_contour_bound_forced_set(deltas : _DeltaSegment, 163 coords : _PointSegment, 164 tolerance : Real = 0) -> set: 165 """The forced set is a conservative set of points on the contour that must be encoded 166 explicitly (ie. cannot be interpolated). Calculating this set allows for significantly 167 speeding up the dynamic-programming, as well as resolve circularity in DP. 168 169 The set is precise; that is, if an index is in the returned set, then there is no way 170 that IUP can generate delta for that point, given `coords` and `deltas`. 171 """ 172 assert len(deltas) == len(coords) 173 174 n = len(deltas) 175 forced = set() 176 # Track "last" and "next" points on the contour as we sweep. 177 for i in range(len(deltas)-1, -1, -1): 178 ld, lc = deltas[i-1], coords[i-1] 179 d, c = deltas[i], coords[i] 180 nd, nc = deltas[i-n+1], coords[i-n+1] 181 182 for j in (0,1): # For X and for Y 183 cj = c[j] 184 dj = d[j] 185 lcj = lc[j] 186 ldj = ld[j] 187 ncj = nc[j] 188 ndj = nd[j] 189 190 if lcj <= ncj: 191 c1, c2 = lcj, ncj 192 d1, d2 = ldj, ndj 193 else: 194 c1, c2 = ncj, lcj 195 d1, d2 = ndj, ldj 196 197 force = False 198 199 # If the two coordinates are the same, then the interpolation 200 # algorithm produces the same delta if both deltas are equal, 201 # and zero if they differ. 202 # 203 # This test has to be before the next one. 204 if c1 == c2: 205 if abs(d1 - d2) > tolerance and abs(dj) > tolerance: 206 force = True 207 208 # If coordinate for current point is between coordinate of adjacent 209 # points on the two sides, but the delta for current point is NOT 210 # between delta for those adjacent points (considering tolerance 211 # allowance), then there is no way that current point can be IUP-ed. 212 # Mark it forced. 213 elif c1 <= cj <= c2: # and c1 != c2 214 if not (min(d1,d2)-tolerance <= dj <= max(d1,d2)+tolerance): 215 force = True 216 217 # Otherwise, the delta should either match the closest, or have the 218 # same sign as the interpolation of the two deltas. 219 else: # cj < c1 or c2 < cj 220 if d1 != d2: 221 if cj < c1: 222 if abs(dj) > tolerance and abs(dj - d1) > tolerance and ((dj-tolerance < d1) != (d1 < d2)): 223 force = True 224 else: # c2 < cj 225 if abs(dj) > tolerance and abs(dj - d2) > tolerance and ((d2 < dj+tolerance) != (d1 < d2)): 226 force = True 227 228 if force: 229 forced.add(i) 230 break 231 232 return forced 233 234def _iup_contour_optimize_dp(deltas : _DeltaSegment, 235 coords : _PointSegment, 236 forced={}, 237 tolerance : Real = 0, 238 lookback : Integral =None): 239 """Straightforward Dynamic-Programming. For each index i, find least-costly encoding of 240 points 0 to i where i is explicitly encoded. We find this by considering all previous 241 explicit points j and check whether interpolation can fill points between j and i. 242 243 Note that solution always encodes last point explicitly. Higher-level is responsible 244 for removing that restriction. 245 246 As major speedup, we stop looking further whenever we see a "forced" point.""" 247 248 n = len(deltas) 249 if lookback is None: 250 lookback = n 251 lookback = min(lookback, MAX_LOOKBACK) 252 costs = {-1:0} 253 chain = {-1:None} 254 for i in range(0, n): 255 best_cost = costs[i-1] + 1 256 257 costs[i] = best_cost 258 chain[i] = i - 1 259 260 if i - 1 in forced: 261 continue 262 263 for j in range(i-2, max(i-lookback, -2), -1): 264 265 cost = costs[j] + 1 266 267 if cost < best_cost and can_iup_in_between(deltas, coords, j, i, tolerance): 268 costs[i] = best_cost = cost 269 chain[i] = j 270 271 if j in forced: 272 break 273 274 return chain, costs 275 276def _rot_list(l : list, k : int): 277 """Rotate list by k items forward. Ie. item at position 0 will be 278 at position k in returned list. Negative k is allowed.""" 279 n = len(l) 280 k %= n 281 if not k: return l 282 return l[n-k:] + l[:n-k] 283 284def _rot_set(s : set, k : int, n : int): 285 k %= n 286 if not k: return s 287 return {(v + k) % n for v in s} 288 289def iup_contour_optimize(deltas : _DeltaSegment, 290 coords : _PointSegment, 291 tolerance : Real = 0.) -> _DeltaOrNoneSegment: 292 """For contour with coordinates `coords`, optimize a set of delta 293 values `deltas` within error `tolerance`. 294 295 Returns delta vector that has most number of None items instead of 296 the input delta. 297 """ 298 299 n = len(deltas) 300 301 # Get the easy cases out of the way: 302 303 # If all are within tolerance distance of 0, encode nothing: 304 if all(abs(complex(*p)) <= tolerance for p in deltas): 305 return [None] * n 306 307 # If there's exactly one point, return it: 308 if n == 1: 309 return deltas 310 311 # If all deltas are exactly the same, return just one (the first one): 312 d0 = deltas[0] 313 if all(d0 == d for d in deltas): 314 return [d0] + [None] * (n-1) 315 316 # Else, solve the general problem using Dynamic Programming. 317 318 forced = _iup_contour_bound_forced_set(deltas, coords, tolerance) 319 # The _iup_contour_optimize_dp() routine returns the optimal encoding 320 # solution given the constraint that the last point is always encoded. 321 # To remove this constraint, we use two different methods, depending on 322 # whether forced set is non-empty or not: 323 324 # Debugging: Make the next if always take the second branch and observe 325 # if the font size changes (reduced); that would mean the forced-set 326 # has members it should not have. 327 if forced: 328 # Forced set is non-empty: rotate the contour start point 329 # such that the last point in the list is a forced point. 330 k = (n-1) - max(forced) 331 assert k >= 0 332 333 deltas = _rot_list(deltas, k) 334 coords = _rot_list(coords, k) 335 forced = _rot_set(forced, k, n) 336 337 # Debugging: Pass a set() instead of forced variable to the next call 338 # to exercise forced-set computation for under-counting. 339 chain, costs = _iup_contour_optimize_dp(deltas, coords, forced, tolerance) 340 341 # Assemble solution. 342 solution = set() 343 i = n - 1 344 while i is not None: 345 solution.add(i) 346 i = chain[i] 347 solution.remove(-1) 348 349 #if not forced <= solution: 350 # print("coord", coords) 351 # print("deltas", deltas) 352 # print("len", len(deltas)) 353 assert forced <= solution, (forced, solution) 354 355 deltas = [deltas[i] if i in solution else None for i in range(n)] 356 357 deltas = _rot_list(deltas, -k) 358 else: 359 # Repeat the contour an extra time, solve the new case, then look for solutions of the 360 # circular n-length problem in the solution for new linear case. I cannot prove that 361 # this always produces the optimal solution... 362 chain, costs = _iup_contour_optimize_dp(deltas+deltas, coords+coords, forced, tolerance, n) 363 best_sol, best_cost = None, n+1 364 365 for start in range(n-1, len(costs) - 1): 366 # Assemble solution. 367 solution = set() 368 i = start 369 while i > start - n: 370 solution.add(i % n) 371 i = chain[i] 372 if i == start - n: 373 cost = costs[start] - costs[start - n] 374 if cost <= best_cost: 375 best_sol, best_cost = solution, cost 376 377 #if not forced <= best_sol: 378 # print("coord", coords) 379 # print("deltas", deltas) 380 # print("len", len(deltas)) 381 assert forced <= best_sol, (forced, best_sol) 382 383 deltas = [deltas[i] if i in best_sol else None for i in range(n)] 384 385 386 return deltas 387 388def iup_delta_optimize(deltas : _DeltaSegment, 389 coords : _PointSegment, 390 ends : _Endpoints, 391 tolerance : Real = 0.) -> _DeltaOrNoneSegment: 392 """For the outline given in `coords`, with contour endpoints given 393 in sorted increasing order in `ends`, optimize a set of delta 394 values `deltas` within error `tolerance`. 395 396 Returns delta vector that has most number of None items instead of 397 the input delta. 398 """ 399 assert sorted(ends) == ends and len(coords) == (ends[-1]+1 if ends else 0) + 4 400 n = len(coords) 401 ends = ends + [n-4, n-3, n-2, n-1] 402 out = [] 403 start = 0 404 for end in ends: 405 contour = iup_contour_optimize(deltas[start:end+1], coords[start:end+1], tolerance) 406 assert len(contour) == end - start + 1 407 out.extend(contour) 408 start = end+1 409 410 return out 411