Last active
September 26, 2025 10:16
-
-
Save typoman/3d2c27a55f452a5f931276632243e50c to your computer and use it in GitHub Desktop.
A pen object that finds the closest point on a glyph's contours to a given target point using analytical method.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from fontgadgets.decorators import font_cached_method, font_method | |
| import fontgadgets; fontgadgets.tools.DEBUG = True | |
| from fontTools.pens.basePen import BasePen, DecomposingPen, MissingComponentError | |
| import math | |
| def bezier_curve(p0, p1, p2, p3, t): | |
| x = (1 - t) ** 3 * p0[0] + 3 * (1 - t) ** 2 * t * p1[0] + 3 * (1 - t) * t ** 2 * p2[0] + t ** 3 * p3[0] | |
| y = (1 - t) ** 3 * p0[1] + 3 * (1 - t) ** 2 * t * p1[1] + 3 * (1 - t) * t ** 2 * p2[1] + t ** 3 * p3[1] | |
| return (x, y) | |
| def bezier_curve_derivative(p0, p1, p2, p3, t): | |
| x = 3 * (1 - t) ** 2 * (p1[0] - p0[0]) + 6 * (1 - t) * t * (p2[0] - p1[0]) + 3 * t ** 2 * (p3[0] - p2[0]) | |
| y = 3 * (1 - t) ** 2 * (p1[1] - p0[1]) + 6 * (1 - t) * t * (p2[1] - p1[1]) + 3 * t ** 2 * (p3[1] - p2[1]) | |
| return (x, y) | |
| def align_to_x(p0, p1, p2, p3): | |
| p0 = complex(*p0) | |
| p1 = complex(*p1) | |
| p2 = complex(*p2) | |
| p3 = complex(*p3) | |
| p1 -= p0 | |
| p2 -= p0 | |
| p3 -= p0 | |
| if p3.real == 0: | |
| if p3.imag > 0: | |
| rotation = complex(0, -1) | |
| elif p3.imag < 0: | |
| rotation = complex(0, 1) | |
| else: | |
| rotation = complex(1, 0) | |
| else: | |
| angle = p3.imag / p3.real | |
| rotation = complex(1, -angle) / (1 + angle ** 2) ** 0.5 | |
| p1 *= rotation | |
| p2 *= rotation | |
| p3 *= rotation | |
| return ((0, 0), (p1.real, p1.imag), (p2.real, p2.imag), (p3.real, p3.imag)) | |
| def calculate_inflection_points(p0, p1, p2, p3): | |
| _p0, _p1, _p2, _p3 = align_to_x(p0, p1, p2, p3) | |
| x2, y2 = _p1 | |
| x3, y3 = _p2 | |
| x4, _ = _p3 | |
| a = x3 * y2 | |
| b = x4 * y2 | |
| c = x2 * y3 | |
| d = x4 * y3 | |
| x = -3 * a + 2 * b + 3 * c - d | |
| y = 3 * a - b - 3 * c | |
| z = c - a | |
| if y ** 2 - 4 * x * z < 0 or x == 0: | |
| return [] | |
| t1 = (-y + (y ** 2 - 4 * x * z) ** 0.5) / (2 * x) | |
| t2 = (-y - (y ** 2 - 4 * x * z) ** 0.5) / (2 * x) | |
| inflection_points = [t for t in [t1, t2] if 0 <= t <= 1] | |
| return inflection_points | |
| def vector(p1, p2): | |
| return (p2[0] - p1[0], p2[1] - p1[1]) | |
| def length(v): | |
| return math.hypot(*v) | |
| def fill_inbetween(input_list, num_steps=5): | |
| output_list = [input_list[0]] | |
| for start, end in zip(input_list, input_list[1:]): | |
| step_size = (end - start) / num_steps | |
| output_list += [start + i * step_size for i in range(1, num_steps + 1)] | |
| return output_list | |
| def closest_point_on_bezier(p0, p1, p2, p3, target): | |
| t_intervals = [0] | |
| t_intervals.extend(calculate_inflection_points(p0, p1, p2, p3)) | |
| t_intervals.append(1) | |
| t_intervals = fill_inbetween(t_intervals) | |
| t_gaps = [t_intervals[i] - t_intervals[i - 1] for i in range(1, len(t_intervals))] | |
| LUT = [] | |
| for i, t in enumerate(t_intervals): | |
| point = bezier_curve(p0, p1, p2, p3, t) | |
| v = vector(target, point) | |
| dist = length(v) | |
| LUT.append({'t': t, 'd': dist, 'i': i}) | |
| T_D = {} | |
| def refine_t(p0, p1, p2, p3, t0, t1, target): | |
| while t1 - t0 > 0.001: | |
| t_m = (t0 + t1) / 2 | |
| p = bezier_curve(p0, p1, p2, p3, t_m) | |
| d_m = bezier_curve_derivative(p0, p1, p2, p3, t_m) | |
| distance_vector = vector(target, p) | |
| dot_product = d_m[0] * distance_vector[0] + d_m[1] * distance_vector[1] | |
| if abs(dot_product) < 0.01: | |
| break | |
| elif dot_product < 0: | |
| t0 = t_m | |
| else: | |
| t1 = t_m | |
| else: | |
| # the gap is too small already befor the loop begins | |
| t_m = t0 | |
| p = bezier_curve(p0, p1, p2, p3, t0) | |
| distance_vector = vector(target, p) | |
| T_D[t_m] = length(distance_vector) | |
| bestCandids = list(sorted(LUT, key=lambda p: p['d']))[:4] | |
| for p in bestCandids: | |
| i = p['i'] | |
| t_m = t_intervals[i] | |
| try: | |
| t_g = t_gaps[i] / 2 | |
| except IndexError: | |
| t_g = t_gaps[-1] / 2 | |
| t0 = max(t_m - t_g, 0) | |
| t1 = min(t_m + t_g, 1) | |
| refine_t(p0, p1, p2, p3, t0, t1, target) | |
| min_d = min(T_D.values()) | |
| return {t for t, d in T_D.items() if d - min_d < 1} | |
| def closest_point_on_line(line, target): | |
| p1, p2 = line | |
| (x1, y1), (x2, y2), (x3, y3) = (p1, p2, target) | |
| dx, dy = (x2 - x1, y2 - y1) | |
| if dx == 0 and dy == 0: | |
| return p1 | |
| det = dx * dx + dy * dy | |
| a = (dy * (y3 - y1) + dx * (x3 - x1)) / det | |
| a = max(0, min(1, a)) | |
| closest_x = x1 + a * dx | |
| closest_y = y1 + a * dy | |
| return (closest_x, closest_y) | |
| def closest_point_on_pointset(point_list, target): | |
| return min(point_list, key=lambda p: length(vector(target, p))) | |
| class ClosestPointPen(BasePen): | |
| """A pen object that finds the closest point on a glyph's contours to a | |
| given target point. | |
| The pen processes the contours of a glyph and calculates the point on the | |
| outline that is nearest to the specified `targetPoint`. | |
| Usage: | |
| pen = ClosestPointPen(targetPoint=(100, 150)) | |
| glyph.draw(pen) | |
| closest_point = pen.closest # Returns (x, y) tuple or None | |
| Args: | |
| targetPoint (tuple): | |
| A tuple `(x, y)` representing the point from which to measure | |
| the distance. | |
| precision (float, optional): | |
| If provided, the pen uses an approximate method for Bézier curves | |
| by sampling points along the curve. The `precision` value controls | |
| the approximate distance between these points. A smaller value | |
| increases the number of sample points, improving accuracy but | |
| reducing speed. If `None` (the default), an analytical method is | |
| used. The analytical method is faster for high-precision results, | |
| so leave this value as `None` if you need a precise result. For a | |
| faster but less precise results, use a value greater than 10. | |
| glyphSet (dict, optional): | |
| A glyph set dict (the font glyphs). Pass the argument if you want | |
| components to be included in the calculation. | |
| """ | |
| def __init__(self, targetPoint, precision=None, glyphSet=None): | |
| BasePen.__init__(self, glyphSet) | |
| self._targetPoint = targetPoint | |
| self._closestPoints = set() | |
| self._solvedClosestPoint = None | |
| self._lastPoint = None | |
| self._firstPoint = None | |
| if precision is not None: | |
| self.precision = precision | |
| self._curveToOne = self._curveToOne_approx | |
| def _moveTo(self, pt): | |
| self._lastPoint = pt | |
| self._firstPoint = pt | |
| def _lineTo(self, pt): | |
| line = (self._lastPoint, pt) | |
| closests = closest_point_on_line(line, self._targetPoint) | |
| self._closestPoints.add(closests) | |
| self._lastPoint = pt | |
| def _curveToOne(self, p1, p2, p3): | |
| p0 = self._lastPoint | |
| curve = (p0, p1, p2, p3) | |
| ts = closest_point_on_bezier(*curve, self._targetPoint) | |
| best_t = ts.pop() | |
| p = bezier_curve(p0, p1, p2, p3, best_t) | |
| self._closestPoints.add(p) | |
| self._lastPoint = p3 | |
| def _curveToOne_approx(self, p1, p2, p3): | |
| p0 = self._lastPoint | |
| dist = length(vector(p0, p3)) | |
| if dist == 0: | |
| self._closestPoints.add(p0) | |
| self._lastPoint = p3 | |
| return | |
| num_steps = int(dist / self.precision) | |
| if num_steps < 1: | |
| num_steps = 1 | |
| points_on_curve = [bezier_curve(p0, p1, p2, p3, i / num_steps) for i in range(num_steps + 1)] | |
| sorted_points = sorted(points_on_curve, key=lambda p: length(vector(self._targetPoint, p))) | |
| line = (sorted_points[0], sorted_points[1]) | |
| closest = closest_point_on_line(line, self._targetPoint) | |
| self._closestPoints.add(closest) | |
| self._lastPoint = p3 | |
| def _closePath(self): | |
| if not self._firstPoint == self._lastPoint: | |
| self._lineTo(self._firstPoint) | |
| def _findClosestPoint(self): | |
| if not self._closestPoints: | |
| return None | |
| self._solvedClosestPoint = closest_point_on_pointset(self._closestPoints, self._targetPoint) | |
| def addPoint(self, pt): | |
| self._closestPoints.add(pt) | |
| @property | |
| def closest(self): | |
| if self._solvedClosestPoint is None: | |
| self._findClosestPoint() | |
| return self._solvedClosestPoint | |
| @font_cached_method("Contour.PointsChanged",) | |
| def _closestPointToTarget(contour, targetPoint, precision=None, components=True): | |
| pen = ClosestPointPen(targetPoint, precision, glyphSet=None) | |
| contour.draw(pen) | |
| return pen.closest | |
| @font_cached_method( | |
| "Glyph.ContoursChanged", "Glyph.ComponentsChanged", "Component.BaseGlyphChanged" | |
| ) | |
| def closestPointToTarget(glyph, targetPoint, precision=None, components=True): | |
| glyphSet = None | |
| if components is True: | |
| glyphSet = glyph.layer | |
| pen = ClosestPointPen(targetPoint, precision, glyphSet) | |
| for contour in glyph: | |
| pt = contour._closestPointToTarget(targetPoint, precision) | |
| pen.addPoint(pt) | |
| if components is True: | |
| for comp in glyph.components: | |
| pen.addComponent(comp.baseGlyph, comp.transformation) | |
| return pen.closest | |
| if __name__ == '__main__': | |
| g = CurrentGlyph() | |
| t = (-400, 100) | |
| print(g.closestPointToTarget(t)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment