| try: |
| import cython |
| |
| COMPILED = cython.compiled |
| except (AttributeError, ImportError): |
| # if cython not installed, use mock module with no-op decorators and types |
| from fontTools.misc import cython |
| |
| COMPILED = False |
| |
| from typing import ( |
| Sequence, |
| Tuple, |
| Union, |
| ) |
| from numbers import Integral, Real |
| |
| |
| _Point = Tuple[Real, Real] |
| _Delta = Tuple[Real, Real] |
| _PointSegment = Sequence[_Point] |
| _DeltaSegment = Sequence[_Delta] |
| _DeltaOrNone = Union[_Delta, None] |
| _DeltaOrNoneSegment = Sequence[_DeltaOrNone] |
| _Endpoints = Sequence[Integral] |
| |
| |
| MAX_LOOKBACK = 8 |
| |
| |
| @cython.cfunc |
| @cython.locals( |
| j=cython.int, |
| n=cython.int, |
| x1=cython.double, |
| x2=cython.double, |
| d1=cython.double, |
| d2=cython.double, |
| scale=cython.double, |
| x=cython.double, |
| d=cython.double, |
| ) |
| def iup_segment( |
| coords: _PointSegment, rc1: _Point, rd1: _Delta, rc2: _Point, rd2: _Delta |
| ): # -> _DeltaSegment: |
| """Given two reference coordinates `rc1` & `rc2` and their respective |
| delta vectors `rd1` & `rd2`, returns interpolated deltas for the set of |
| coordinates `coords`.""" |
| |
| # rc1 = reference coord 1 |
| # rd1 = reference delta 1 |
| out_arrays = [None, None] |
| for j in 0, 1: |
| out_arrays[j] = out = [] |
| x1, x2, d1, d2 = rc1[j], rc2[j], rd1[j], rd2[j] |
| |
| if x1 == x2: |
| n = len(coords) |
| if d1 == d2: |
| out.extend([d1] * n) |
| else: |
| out.extend([0] * n) |
| continue |
| |
| if x1 > x2: |
| x1, x2 = x2, x1 |
| d1, d2 = d2, d1 |
| |
| # x1 < x2 |
| scale = (d2 - d1) / (x2 - x1) |
| for pair in coords: |
| x = pair[j] |
| |
| if x <= x1: |
| d = d1 |
| elif x >= x2: |
| d = d2 |
| else: |
| # Interpolate |
| d = d1 + (x - x1) * scale |
| |
| out.append(d) |
| |
| return zip(*out_arrays) |
| |
| |
| def iup_contour(deltas: _DeltaOrNoneSegment, coords: _PointSegment) -> _DeltaSegment: |
| """For the contour given in `coords`, interpolate any missing |
| delta values in delta vector `deltas`. |
| |
| Returns fully filled-out delta vector.""" |
| |
| assert len(deltas) == len(coords) |
| if None not in deltas: |
| return deltas |
| |
| n = len(deltas) |
| # indices of points with explicit deltas |
| indices = [i for i, v in enumerate(deltas) if v is not None] |
| if not indices: |
| # All deltas are None. Return 0,0 for all. |
| return [(0, 0)] * n |
| |
| out = [] |
| it = iter(indices) |
| start = next(it) |
| if start != 0: |
| # Initial segment that wraps around |
| i1, i2, ri1, ri2 = 0, start, start, indices[-1] |
| out.extend( |
| iup_segment( |
| coords[i1:i2], coords[ri1], deltas[ri1], coords[ri2], deltas[ri2] |
| ) |
| ) |
| out.append(deltas[start]) |
| for end in it: |
| if end - start > 1: |
| i1, i2, ri1, ri2 = start + 1, end, start, end |
| out.extend( |
| iup_segment( |
| coords[i1:i2], coords[ri1], deltas[ri1], coords[ri2], deltas[ri2] |
| ) |
| ) |
| out.append(deltas[end]) |
| start = end |
| if start != n - 1: |
| # Final segment that wraps around |
| i1, i2, ri1, ri2 = start + 1, n, start, indices[0] |
| out.extend( |
| iup_segment( |
| coords[i1:i2], coords[ri1], deltas[ri1], coords[ri2], deltas[ri2] |
| ) |
| ) |
| |
| assert len(deltas) == len(out), (len(deltas), len(out)) |
| return out |
| |
| |
| def iup_delta( |
| deltas: _DeltaOrNoneSegment, coords: _PointSegment, ends: _Endpoints |
| ) -> _DeltaSegment: |
| """For the outline given in `coords`, with contour endpoints given |
| in sorted increasing order in `ends`, interpolate any missing |
| delta values in delta vector `deltas`. |
| |
| Returns fully filled-out delta vector.""" |
| |
| assert sorted(ends) == ends and len(coords) == (ends[-1] + 1 if ends else 0) + 4 |
| n = len(coords) |
| ends = ends + [n - 4, n - 3, n - 2, n - 1] |
| out = [] |
| start = 0 |
| for end in ends: |
| end += 1 |
| contour = iup_contour(deltas[start:end], coords[start:end]) |
| out.extend(contour) |
| start = end |
| |
| return out |
| |
| |
| # Optimizer |
| |
| |
| @cython.cfunc |
| @cython.inline |
| @cython.locals( |
| i=cython.int, |
| j=cython.int, |
| # tolerance=cython.double, # https://github.com/fonttools/fonttools/issues/3282 |
| x=cython.double, |
| y=cython.double, |
| p=cython.double, |
| q=cython.double, |
| ) |
| @cython.returns(int) |
| def can_iup_in_between( |
| deltas: _DeltaSegment, |
| coords: _PointSegment, |
| i: Integral, |
| j: Integral, |
| tolerance: Real, |
| ): # -> bool: |
| """Return true if the deltas for points at `i` and `j` (`i < j`) can be |
| successfully used to interpolate deltas for points in between them within |
| provided error tolerance.""" |
| |
| assert j - i >= 2 |
| interp = iup_segment(coords[i + 1 : j], coords[i], deltas[i], coords[j], deltas[j]) |
| deltas = deltas[i + 1 : j] |
| |
| return all( |
| abs(complex(x - p, y - q)) <= tolerance |
| for (x, y), (p, q) in zip(deltas, interp) |
| ) |
| |
| |
| @cython.locals( |
| cj=cython.double, |
| dj=cython.double, |
| lcj=cython.double, |
| ldj=cython.double, |
| ncj=cython.double, |
| ndj=cython.double, |
| force=cython.int, |
| forced=set, |
| ) |
| def _iup_contour_bound_forced_set( |
| deltas: _DeltaSegment, coords: _PointSegment, tolerance: Real = 0 |
| ) -> set: |
| """The forced set is a conservative set of points on the contour that must be encoded |
| explicitly (ie. cannot be interpolated). Calculating this set allows for significantly |
| speeding up the dynamic-programming, as well as resolve circularity in DP. |
| |
| The set is precise; that is, if an index is in the returned set, then there is no way |
| that IUP can generate delta for that point, given `coords` and `deltas`. |
| """ |
| assert len(deltas) == len(coords) |
| |
| n = len(deltas) |
| forced = set() |
| # Track "last" and "next" points on the contour as we sweep. |
| for i in range(len(deltas) - 1, -1, -1): |
| ld, lc = deltas[i - 1], coords[i - 1] |
| d, c = deltas[i], coords[i] |
| nd, nc = deltas[i - n + 1], coords[i - n + 1] |
| |
| for j in (0, 1): # For X and for Y |
| cj = c[j] |
| dj = d[j] |
| lcj = lc[j] |
| ldj = ld[j] |
| ncj = nc[j] |
| ndj = nd[j] |
| |
| if lcj <= ncj: |
| c1, c2 = lcj, ncj |
| d1, d2 = ldj, ndj |
| else: |
| c1, c2 = ncj, lcj |
| d1, d2 = ndj, ldj |
| |
| force = False |
| |
| # If the two coordinates are the same, then the interpolation |
| # algorithm produces the same delta if both deltas are equal, |
| # and zero if they differ. |
| # |
| # This test has to be before the next one. |
| if c1 == c2: |
| if abs(d1 - d2) > tolerance and abs(dj) > tolerance: |
| force = True |
| |
| # If coordinate for current point is between coordinate of adjacent |
| # points on the two sides, but the delta for current point is NOT |
| # between delta for those adjacent points (considering tolerance |
| # allowance), then there is no way that current point can be IUP-ed. |
| # Mark it forced. |
| elif c1 <= cj <= c2: # and c1 != c2 |
| if not (min(d1, d2) - tolerance <= dj <= max(d1, d2) + tolerance): |
| force = True |
| |
| # Otherwise, the delta should either match the closest, or have the |
| # same sign as the interpolation of the two deltas. |
| else: # cj < c1 or c2 < cj |
| if d1 != d2: |
| if cj < c1: |
| if ( |
| abs(dj) > tolerance |
| and abs(dj - d1) > tolerance |
| and ((dj - tolerance < d1) != (d1 < d2)) |
| ): |
| force = True |
| else: # c2 < cj |
| if ( |
| abs(dj) > tolerance |
| and abs(dj - d2) > tolerance |
| and ((d2 < dj + tolerance) != (d1 < d2)) |
| ): |
| force = True |
| |
| if force: |
| forced.add(i) |
| break |
| |
| return forced |
| |
| |
| @cython.locals( |
| i=cython.int, |
| j=cython.int, |
| best_cost=cython.double, |
| best_j=cython.int, |
| cost=cython.double, |
| forced=set, |
| tolerance=cython.double, |
| ) |
| def _iup_contour_optimize_dp( |
| deltas: _DeltaSegment, |
| coords: _PointSegment, |
| forced=set(), |
| tolerance: Real = 0, |
| lookback: Integral = None, |
| ): |
| """Straightforward Dynamic-Programming. For each index i, find least-costly encoding of |
| points 0 to i where i is explicitly encoded. We find this by considering all previous |
| explicit points j and check whether interpolation can fill points between j and i. |
| |
| Note that solution always encodes last point explicitly. Higher-level is responsible |
| for removing that restriction. |
| |
| As major speedup, we stop looking further whenever we see a "forced" point.""" |
| |
| n = len(deltas) |
| if lookback is None: |
| lookback = n |
| lookback = min(lookback, MAX_LOOKBACK) |
| costs = {-1: 0} |
| chain = {-1: None} |
| for i in range(0, n): |
| best_cost = costs[i - 1] + 1 |
| |
| costs[i] = best_cost |
| chain[i] = i - 1 |
| |
| if i - 1 in forced: |
| continue |
| |
| for j in range(i - 2, max(i - lookback, -2), -1): |
| cost = costs[j] + 1 |
| |
| if cost < best_cost and can_iup_in_between(deltas, coords, j, i, tolerance): |
| costs[i] = best_cost = cost |
| chain[i] = j |
| |
| if j in forced: |
| break |
| |
| return chain, costs |
| |
| |
| def _rot_list(l: list, k: int): |
| """Rotate list by k items forward. Ie. item at position 0 will be |
| at position k in returned list. Negative k is allowed.""" |
| n = len(l) |
| k %= n |
| if not k: |
| return l |
| return l[n - k :] + l[: n - k] |
| |
| |
| def _rot_set(s: set, k: int, n: int): |
| k %= n |
| if not k: |
| return s |
| return {(v + k) % n for v in s} |
| |
| |
| def iup_contour_optimize( |
| deltas: _DeltaSegment, coords: _PointSegment, tolerance: Real = 0.0 |
| ) -> _DeltaOrNoneSegment: |
| """For contour with coordinates `coords`, optimize a set of delta |
| values `deltas` within error `tolerance`. |
| |
| Returns delta vector that has most number of None items instead of |
| the input delta. |
| """ |
| |
| n = len(deltas) |
| |
| # Get the easy cases out of the way: |
| |
| # If all are within tolerance distance of 0, encode nothing: |
| if all(abs(complex(*p)) <= tolerance for p in deltas): |
| return [None] * n |
| |
| # If there's exactly one point, return it: |
| if n == 1: |
| return deltas |
| |
| # If all deltas are exactly the same, return just one (the first one): |
| d0 = deltas[0] |
| if all(d0 == d for d in deltas): |
| return [d0] + [None] * (n - 1) |
| |
| # Else, solve the general problem using Dynamic Programming. |
| |
| forced = _iup_contour_bound_forced_set(deltas, coords, tolerance) |
| # The _iup_contour_optimize_dp() routine returns the optimal encoding |
| # solution given the constraint that the last point is always encoded. |
| # To remove this constraint, we use two different methods, depending on |
| # whether forced set is non-empty or not: |
| |
| # Debugging: Make the next if always take the second branch and observe |
| # if the font size changes (reduced); that would mean the forced-set |
| # has members it should not have. |
| if forced: |
| # Forced set is non-empty: rotate the contour start point |
| # such that the last point in the list is a forced point. |
| k = (n - 1) - max(forced) |
| assert k >= 0 |
| |
| deltas = _rot_list(deltas, k) |
| coords = _rot_list(coords, k) |
| forced = _rot_set(forced, k, n) |
| |
| # Debugging: Pass a set() instead of forced variable to the next call |
| # to exercise forced-set computation for under-counting. |
| chain, costs = _iup_contour_optimize_dp(deltas, coords, forced, tolerance) |
| |
| # Assemble solution. |
| solution = set() |
| i = n - 1 |
| while i is not None: |
| solution.add(i) |
| i = chain[i] |
| solution.remove(-1) |
| |
| # if not forced <= solution: |
| # print("coord", coords) |
| # print("deltas", deltas) |
| # print("len", len(deltas)) |
| assert forced <= solution, (forced, solution) |
| |
| deltas = [deltas[i] if i in solution else None for i in range(n)] |
| |
| deltas = _rot_list(deltas, -k) |
| else: |
| # Repeat the contour an extra time, solve the new case, then look for solutions of the |
| # circular n-length problem in the solution for new linear case. I cannot prove that |
| # this always produces the optimal solution... |
| chain, costs = _iup_contour_optimize_dp( |
| deltas + deltas, coords + coords, forced, tolerance, n |
| ) |
| best_sol, best_cost = None, n + 1 |
| |
| for start in range(n - 1, len(costs) - 1): |
| # Assemble solution. |
| solution = set() |
| i = start |
| while i > start - n: |
| solution.add(i % n) |
| i = chain[i] |
| if i == start - n: |
| cost = costs[start] - costs[start - n] |
| if cost <= best_cost: |
| best_sol, best_cost = solution, cost |
| |
| # if not forced <= best_sol: |
| # print("coord", coords) |
| # print("deltas", deltas) |
| # print("len", len(deltas)) |
| assert forced <= best_sol, (forced, best_sol) |
| |
| deltas = [deltas[i] if i in best_sol else None for i in range(n)] |
| |
| return deltas |
| |
| |
| def iup_delta_optimize( |
| deltas: _DeltaSegment, |
| coords: _PointSegment, |
| ends: _Endpoints, |
| tolerance: Real = 0.0, |
| ) -> _DeltaOrNoneSegment: |
| """For the outline given in `coords`, with contour endpoints given |
| in sorted increasing order in `ends`, optimize a set of delta |
| values `deltas` within error `tolerance`. |
| |
| Returns delta vector that has most number of None items instead of |
| the input delta. |
| """ |
| assert sorted(ends) == ends and len(coords) == (ends[-1] + 1 if ends else 0) + 4 |
| n = len(coords) |
| ends = ends + [n - 4, n - 3, n - 2, n - 1] |
| out = [] |
| start = 0 |
| for end in ends: |
| contour = iup_contour_optimize( |
| deltas[start : end + 1], coords[start : end + 1], tolerance |
| ) |
| assert len(contour) == end - start + 1 |
| out.extend(contour) |
| start = end + 1 |
| |
| return out |
