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