diff options
Diffstat (limited to 'Lib/fontTools/varLib/iup.py')
| -rw-r--r-- | Lib/fontTools/varLib/iup.py | 860 |
1 files changed, 468 insertions, 392 deletions
diff --git a/Lib/fontTools/varLib/iup.py b/Lib/fontTools/varLib/iup.py index 9c5bc35b..76555f35 100644 --- a/Lib/fontTools/varLib/iup.py +++ b/Lib/fontTools/varLib/iup.py @@ -1,25 +1,19 @@ -from typing import ( - Sequence, - Tuple, - Union, -) -from numbers import ( - Integral, - Real -) - try: - import cython -except ImportError: - # if cython not installed, use mock module with no-op decorators and types - from fontTools.misc import cython + import cython -if cython.compiled: - # Yep, I'm compiled. - COMPILED = True -else: - # Just a lowly interpreted script. - COMPILED = False + 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] @@ -33,378 +27,460 @@ _Endpoints = Sequence[Integral] MAX_LOOKBACK = 8 -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 + +@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 -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 = list(iup_segment(coords[i+1:j], coords[i], deltas[i], coords[j], deltas[j])) - deltas = deltas[i+1:j] - - assert len(deltas) == len(interp) - - return all(abs(complex(x-p, y-q)) <= tolerance for (x,y),(p,q) in zip(deltas, interp)) - -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 - -def _iup_contour_optimize_dp(deltas : _DeltaSegment, - coords : _PointSegment, - forced={}, - 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.) -> _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.) -> _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 + +@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 |