from __future__ import annotations import math import os import re import sys import xml.etree.ElementTree as ET from dataclasses import dataclass from datetime import datetime, timezone from pathlib import Path Point = tuple[float, float] Matrix = tuple[float, float, float, float, float, float] Segment = tuple[int, float, float, float, float, float, float, float, float] SVG_NS_RE = re.compile(r"\{[^}]+\}") PATH_TOKEN_RE = re.compile( r"[AaCcHhLlMmQqSsTtVvZz]|[-+]?(?:(?:\d*\.\d+)|(?:\d+\.?))(?:[eE][-+]?\d+)?" ) TRANSFORM_RE = re.compile(r"([a-zA-Z]+)\(([^)]*)\)") NUMBER_RE = re.compile(r"[-+]?(?:(?:\d*\.\d+)|(?:\d+\.?))(?:[eE][-+]?\d+)?") PATH_PARAM_COUNTS = { "a": 7, "c": 6, "h": 1, "l": 2, "m": 2, "q": 4, "s": 4, "t": 2, "v": 1, } DPI = 96 MM_PER_INCH = 25.4 IDENTITY: Matrix = (1.0, 0.0, 0.0, 1.0, 0.0, 0.0) @dataclass(frozen=True) class SvgLineSpacingResult: percentile: float spacingPx: float spacingMm: float minSpacingPx: float minSpacingMm: float sampleStep: float curveCount: int segmentCount: int nearestCount: int sourceWidth: float sourceHeight: float elementWidth: float elementHeight: float computedAt: str closestPoints: dict[str, float] | None = None def as_dict(self) -> dict: return { "percentile": self.percentile, "spacingPx": self.spacingPx, "spacingMm": self.spacingMm, "minSpacingPx": self.minSpacingPx, "minSpacingMm": self.minSpacingMm, "sampleStep": self.sampleStep, "curveCount": self.curveCount, "segmentCount": self.segmentCount, "nearestCount": self.nearestCount, "sourceWidth": self.sourceWidth, "sourceHeight": self.sourceHeight, "elementWidth": self.elementWidth, "elementHeight": self.elementHeight, "computedAt": self.computedAt, "closestPoints": self.closestPoints, } def analyze_svg_line_spacing_file( svg_path: Path, *, percentile: float, element_width: float, element_height: float, sample_step: float = 2.0, ) -> SvgLineSpacingResult: svg_text = svg_path.read_text(encoding="utf-8", errors="replace") return analyze_svg_line_spacing( svg_text, percentile=percentile, element_width=element_width, element_height=element_height, sample_step=sample_step, ) def analyze_svg_line_spacing( svg_text: str, *, percentile: float, element_width: float, element_height: float, sample_step: float = 2.0, ) -> SvgLineSpacingResult: if element_width <= 0 or element_height <= 0: raise ValueError("element size must be positive") percentile = max(0.0, min(100.0, float(percentile))) sample_step = max(0.5, float(sample_step or 2.0)) try: root = ET.fromstring(svg_text) except ET.ParseError as exc: raise ValueError("无法解析 SVG") from exc source_width, source_height = read_svg_size(root) segments, curve_count = collect_segments(root, sample_step) if len(segments) < 2: raise ValueError("SVG 中可分析的轮廓线太少") nearest_distances, min_distance, closest_points = compute_nearest_spacing( segments, max(8.0, sample_step * 8.0), ) if not nearest_distances or not math.isfinite(min_distance): raise ValueError("没有找到可比较的不同轮廓曲线") nearest_distances.sort() percentile_distance = percentile_value(nearest_distances, percentile) scale = min(element_width / source_width, element_height / source_height) spacing_px = percentile_distance * scale min_spacing_px = min_distance * scale return SvgLineSpacingResult( percentile=percentile, spacingPx=spacing_px, spacingMm=px_to_mm(spacing_px), minSpacingPx=min_spacing_px, minSpacingMm=px_to_mm(min_spacing_px), sampleStep=sample_step, curveCount=curve_count, segmentCount=len(segments), nearestCount=len(nearest_distances), sourceWidth=source_width, sourceHeight=source_height, elementWidth=element_width, elementHeight=element_height, computedAt=datetime.now(timezone.utc).isoformat(), closestPoints=scale_closest_points(closest_points, scale), ) def read_svg_size(root: ET.Element) -> tuple[float, float]: view_box = root.attrib.get("viewBox") or root.attrib.get("viewbox") if view_box: values = [parse_float(item) for item in re.split(r"[\s,]+", view_box.strip()) if item] if len(values) >= 4 and all(math.isfinite(v) for v in values[:4]) and values[2] > 0 and values[3] > 0: return values[2], values[3] width = parse_svg_length(root.attrib.get("width")) height = parse_svg_length(root.attrib.get("height")) if width > 0 and height > 0: return width, height return 1000.0, 1000.0 def collect_segments(root: ET.Element, sample_step: float) -> tuple[list[Segment], int]: segments: list[Segment] = [] next_curve_id = 0 def visit(node: ET.Element, matrix: Matrix, hidden: bool) -> None: nonlocal next_curve_id hidden = hidden or element_hidden(node) node_matrix = multiply_matrix(matrix, parse_transform(node.attrib.get("transform", ""))) tag = strip_ns(node.tag) if not hidden and drawable_geometry(node): if tag == "path": next_curve_id = append_path_segments( node.attrib.get("d", ""), next_curve_id, sample_step, node_matrix, segments, ) elif tag == "line": next_curve_id = append_line_element(node, next_curve_id, sample_step, node_matrix, segments) elif tag in {"polyline", "polygon"}: next_curve_id = append_poly_element(node, next_curve_id, sample_step, node_matrix, segments, tag == "polygon") elif tag == "rect": next_curve_id = append_rect_element(node, next_curve_id, sample_step, node_matrix, segments) elif tag in {"circle", "ellipse"}: next_curve_id = append_ellipse_element(node, next_curve_id, sample_step, node_matrix, segments, tag) if tag not in {"defs", "clipPath", "mask", "pattern", "symbol"}: for child in list(node): visit(child, node_matrix, hidden) visit(root, IDENTITY, False) return segments, next_curve_id def strip_ns(tag: str) -> str: return SVG_NS_RE.sub("", tag) def element_hidden(node: ET.Element) -> bool: style = parse_style(node.attrib.get("style", "")) display = (node.attrib.get("display") or style.get("display") or "").strip().lower() visibility = (node.attrib.get("visibility") or style.get("visibility") or "").strip().lower() return display == "none" or visibility == "hidden" def drawable_geometry(node: ET.Element) -> bool: tag = strip_ns(node.tag) if tag not in {"path", "line", "polyline", "polygon", "rect", "circle", "ellipse"}: return False style = parse_style(node.attrib.get("style", "")) stroke = (node.attrib.get("stroke") or style.get("stroke") or "").strip().lower() fill = (node.attrib.get("fill") or style.get("fill") or "").strip().lower() if stroke and stroke not in {"none", "transparent"}: return True if not fill or fill not in {"none", "transparent"}: return True return False def parse_style(raw: str) -> dict[str, str]: result: dict[str, str] = {} for part in raw.split(";"): if ":" not in part: continue key, value = part.split(":", 1) result[key.strip().lower()] = value.strip() return result def append_path_segments( path_data: str, curve_id: int, sample_step: float, matrix: Matrix, output: list[Segment], ) -> int: tokens = tokenize_path(path_data) if not tokens: return curve_id index = 0 command = "" current: Point = (0.0, 0.0) subpath_start: Point = (0.0, 0.0) active_curve_id = curve_id - 1 last_cubic_control: Point | None = None last_quad_control: Point | None = None previous_command = "" while index < len(tokens): token = tokens[index] if isinstance(token, str): command = token index += 1 if not command: break lower = command.lower() if lower == "z": if active_curve_id >= curve_id: append_sampled_line(current, subpath_start, active_curve_id, sample_step, matrix, output) current = subpath_start last_cubic_control = None last_quad_control = None previous_command = command command = "" continue param_count = PATH_PARAM_COUNTS.get(lower) if not param_count: break first_move = lower == "m" while has_number_run(tokens, index, param_count): values = [float(tokens[index + offset]) for offset in range(param_count)] index += param_count if lower == "m": point = absolute_point(command, current, values[0], values[1]) if first_move: active_curve_id = curve_id curve_id += 1 subpath_start = point current = point first_move = False else: append_sampled_line(current, point, active_curve_id, sample_step, matrix, output) current = point last_cubic_control = None last_quad_control = None elif lower == "l": point = absolute_point(command, current, values[0], values[1]) append_sampled_line(current, point, active_curve_id, sample_step, matrix, output) current = point last_cubic_control = None last_quad_control = None elif lower == "h": x = current[0] + values[0] if command.islower() else values[0] point = (x, current[1]) append_sampled_line(current, point, active_curve_id, sample_step, matrix, output) current = point last_cubic_control = None last_quad_control = None elif lower == "v": y = current[1] + values[0] if command.islower() else values[0] point = (current[0], y) append_sampled_line(current, point, active_curve_id, sample_step, matrix, output) current = point last_cubic_control = None last_quad_control = None elif lower == "c": p1 = absolute_point(command, current, values[0], values[1]) p2 = absolute_point(command, current, values[2], values[3]) point = absolute_point(command, current, values[4], values[5]) append_cubic(current, p1, p2, point, active_curve_id, sample_step, matrix, output) current = point last_cubic_control = p2 last_quad_control = None elif lower == "s": p1 = reflect_point(current, last_cubic_control) if previous_command.lower() in {"c", "s"} else current p2 = absolute_point(command, current, values[0], values[1]) point = absolute_point(command, current, values[2], values[3]) append_cubic(current, p1, p2, point, active_curve_id, sample_step, matrix, output) current = point last_cubic_control = p2 last_quad_control = None elif lower == "q": p1 = absolute_point(command, current, values[0], values[1]) point = absolute_point(command, current, values[2], values[3]) append_quadratic(current, p1, point, active_curve_id, sample_step, matrix, output) current = point last_quad_control = p1 last_cubic_control = None elif lower == "t": p1 = reflect_point(current, last_quad_control) if previous_command.lower() in {"q", "t"} else current point = absolute_point(command, current, values[0], values[1]) append_quadratic(current, p1, point, active_curve_id, sample_step, matrix, output) current = point last_quad_control = p1 last_cubic_control = None elif lower == "a": rx, ry, angle, large_arc, sweep, x, y = values point = absolute_point(command, current, x, y) append_arc(current, rx, ry, angle, large_arc, sweep, point, active_curve_id, sample_step, matrix, output) current = point last_cubic_control = None last_quad_control = None previous_command = command if index < len(tokens) and isinstance(tokens[index], str): break return curve_id def tokenize_path(path_data: str) -> list[str | float]: tokens: list[str | float] = [] for match in PATH_TOKEN_RE.finditer(path_data): raw = match.group(0) if re.fullmatch(r"[AaCcHhLlMmQqSsTtVvZz]", raw): tokens.append(raw) else: tokens.append(float(raw)) return tokens def has_number_run(tokens: list[str | float], index: int, count: int) -> bool: if index + count > len(tokens): return False return all(not isinstance(tokens[index + offset], str) for offset in range(count)) def absolute_point(command: str, current: Point, x: float, y: float) -> Point: if command.islower(): return current[0] + x, current[1] + y return x, y def reflect_point(origin: Point, point: Point | None) -> Point: if point is None: return origin return 2 * origin[0] - point[0], 2 * origin[1] - point[1] def append_line_element(node: ET.Element, curve_id: int, sample_step: float, matrix: Matrix, output: list[Segment]) -> int: p1 = (parse_svg_length(node.attrib.get("x1")), parse_svg_length(node.attrib.get("y1"))) p2 = (parse_svg_length(node.attrib.get("x2")), parse_svg_length(node.attrib.get("y2"))) append_sampled_line(p1, p2, curve_id, sample_step, matrix, output) return curve_id + 1 def append_poly_element( node: ET.Element, curve_id: int, sample_step: float, matrix: Matrix, output: list[Segment], close: bool, ) -> int: points = parse_points(node.attrib.get("points", "")) if len(points) < 2: return curve_id for p1, p2 in zip(points, points[1:]): append_sampled_line(p1, p2, curve_id, sample_step, matrix, output) if close: append_sampled_line(points[-1], points[0], curve_id, sample_step, matrix, output) return curve_id + 1 def append_rect_element(node: ET.Element, curve_id: int, sample_step: float, matrix: Matrix, output: list[Segment]) -> int: x = parse_svg_length(node.attrib.get("x")) y = parse_svg_length(node.attrib.get("y")) width = parse_svg_length(node.attrib.get("width")) height = parse_svg_length(node.attrib.get("height")) if width <= 0 or height <= 0: return curve_id points = [(x, y), (x + width, y), (x + width, y + height), (x, y + height)] for p1, p2 in zip(points, points[1:] + points[:1]): append_sampled_line(p1, p2, curve_id, sample_step, matrix, output) return curve_id + 1 def append_ellipse_element( node: ET.Element, curve_id: int, sample_step: float, matrix: Matrix, output: list[Segment], tag: str, ) -> int: if tag == "circle": cx = parse_svg_length(node.attrib.get("cx")) cy = parse_svg_length(node.attrib.get("cy")) rx = ry = parse_svg_length(node.attrib.get("r")) else: cx = parse_svg_length(node.attrib.get("cx")) cy = parse_svg_length(node.attrib.get("cy")) rx = parse_svg_length(node.attrib.get("rx")) ry = parse_svg_length(node.attrib.get("ry")) if rx <= 0 or ry <= 0: return curve_id circumference = math.pi * (3 * (rx + ry) - math.sqrt((3 * rx + ry) * (rx + 3 * ry))) steps = max(24, int(math.ceil(circumference / sample_step))) raw_points = [ (cx + math.cos((math.tau * i) / steps) * rx, cy + math.sin((math.tau * i) / steps) * ry) for i in range(steps + 1) ] append_points(raw_points, curve_id, matrix, output) return curve_id + 1 def append_sampled_line(p1: Point, p2: Point, curve_id: int, sample_step: float, matrix: Matrix, output: list[Segment]) -> None: if curve_id < 0: return tp1 = transform_point(matrix, p1) tp2 = transform_point(matrix, p2) distance = point_distance(tp1, tp2) steps = max(1, int(math.ceil(distance / sample_step))) points = [lerp_point(p1, p2, i / steps) for i in range(steps + 1)] append_points(points, curve_id, matrix, output) def append_quadratic( p0: Point, p1: Point, p2: Point, curve_id: int, sample_step: float, matrix: Matrix, output: list[Segment], ) -> None: tp = [transform_point(matrix, p) for p in (p0, p1, p2)] control_length = point_distance(tp[0], tp[1]) + point_distance(tp[1], tp[2]) steps = max(4, int(math.ceil(control_length / sample_step))) points = [] for i in range(steps + 1): t = i / steps mt = 1 - t points.append(( mt * mt * p0[0] + 2 * mt * t * p1[0] + t * t * p2[0], mt * mt * p0[1] + 2 * mt * t * p1[1] + t * t * p2[1], )) append_points(points, curve_id, matrix, output) def append_cubic( p0: Point, p1: Point, p2: Point, p3: Point, curve_id: int, sample_step: float, matrix: Matrix, output: list[Segment], ) -> None: tp = [transform_point(matrix, p) for p in (p0, p1, p2, p3)] control_length = point_distance(tp[0], tp[1]) + point_distance(tp[1], tp[2]) + point_distance(tp[2], tp[3]) steps = max(6, int(math.ceil(control_length / sample_step))) points = [] for i in range(steps + 1): t = i / steps mt = 1 - t points.append(( mt**3 * p0[0] + 3 * mt * mt * t * p1[0] + 3 * mt * t * t * p2[0] + t**3 * p3[0], mt**3 * p0[1] + 3 * mt * mt * t * p1[1] + 3 * mt * t * t * p2[1] + t**3 * p3[1], )) append_points(points, curve_id, matrix, output) def append_arc( start: Point, rx: float, ry: float, angle_degrees: float, large_arc: float, sweep: float, end: Point, curve_id: int, sample_step: float, matrix: Matrix, output: list[Segment], ) -> None: if rx == 0 or ry == 0 or start == end: append_sampled_line(start, end, curve_id, sample_step, matrix, output) return rx = abs(rx) ry = abs(ry) phi = math.radians(angle_degrees % 360) cos_phi = math.cos(phi) sin_phi = math.sin(phi) dx = (start[0] - end[0]) / 2 dy = (start[1] - end[1]) / 2 x1p = cos_phi * dx + sin_phi * dy y1p = -sin_phi * dx + cos_phi * dy radii_check = (x1p * x1p) / (rx * rx) + (y1p * y1p) / (ry * ry) if radii_check > 1: scale = math.sqrt(radii_check) rx *= scale ry *= scale sign = -1 if bool(large_arc) == bool(sweep) else 1 numerator = rx * rx * ry * ry - rx * rx * y1p * y1p - ry * ry * x1p * x1p denominator = rx * rx * y1p * y1p + ry * ry * x1p * x1p factor = sign * math.sqrt(max(0.0, numerator / denominator)) if denominator else 0.0 cxp = factor * (rx * y1p / ry) cyp = factor * (-ry * x1p / rx) cx = cos_phi * cxp - sin_phi * cyp + (start[0] + end[0]) / 2 cy = sin_phi * cxp + cos_phi * cyp + (start[1] + end[1]) / 2 theta1 = vector_angle((1, 0), ((x1p - cxp) / rx, (y1p - cyp) / ry)) delta = vector_angle( ((x1p - cxp) / rx, (y1p - cyp) / ry), ((-x1p - cxp) / rx, (-y1p - cyp) / ry), ) if not sweep and delta > 0: delta -= math.tau elif sweep and delta < 0: delta += math.tau arc_length = abs(delta) * max(rx, ry) steps = max(4, int(math.ceil(arc_length / sample_step))) points = [] for i in range(steps + 1): theta = theta1 + delta * (i / steps) x = cx + cos_phi * rx * math.cos(theta) - sin_phi * ry * math.sin(theta) y = cy + sin_phi * rx * math.cos(theta) + cos_phi * ry * math.sin(theta) points.append((x, y)) append_points(points, curve_id, matrix, output) def vector_angle(u: Point, v: Point) -> float: dot_value = u[0] * v[0] + u[1] * v[1] det_value = u[0] * v[1] - u[1] * v[0] return math.atan2(det_value, dot_value) def append_points(points: list[Point], curve_id: int, matrix: Matrix, output: list[Segment]) -> None: transformed = [transform_point(matrix, point) for point in points] for a, b in zip(transformed, transformed[1:]): length = point_distance(a, b) if length <= 0.0001: continue ax, ay = a bx, by = b output.append(( curve_id, ax, ay, bx, by, min(ax, bx), min(ay, by), max(ax, bx), max(ay, by), )) def compute_nearest_spacing( segments: list[Segment], cell_size: float, ) -> tuple[list[float], float, dict[str, float] | None]: try: return compute_nearest_spacing_kdtree(segments) except ImportError: return compute_nearest_spacing_grid(segments, cell_size) def compute_nearest_spacing_kdtree(segments: list[Segment]) -> tuple[list[float], float, dict[str, float] | None]: try: import numpy as np from scipy.spatial import cKDTree except ImportError: scipy_site = os.environ.get("WORDCLOUD_SCIPY_SITE", "") if scipy_site and scipy_site not in sys.path: sys.path.append(scipy_site) import numpy as np from scipy.spatial import cKDTree points = sample_points_from_segments(segments) if len(points) < 2: return [], math.inf, None coordinates = np.asarray([(point[1], point[2]) for point in points], dtype=np.float64) curve_ids = np.asarray([point[0] for point in points], dtype=np.int32) tree = cKDTree(coordinates) k = min(128, len(points)) chunk_size = 50000 nearest_distances: list[float] = [] min_distance = math.inf closest_points: dict[str, float] | None = None for start in range(0, len(points), chunk_size): stop = min(start + chunk_size, len(points)) try: distances, indices = tree.query(coordinates[start:stop], k=k, workers=-1) except TypeError: distances, indices = tree.query(coordinates[start:stop], k=k) if k == 1: distances = distances[:, np.newaxis] indices = indices[:, np.newaxis] candidate_curve_ids = curve_ids[indices] current_curve_ids = curve_ids[start:stop, np.newaxis] valid = candidate_curve_ids != current_curve_ids found = valid.any(axis=1) if not found.any(): continue first_valid = valid.argmax(axis=1) row_numbers = np.arange(stop - start) found_rows = row_numbers[found] found_columns = first_valid[found] values = distances[found_rows, found_columns] finite = np.isfinite(values) if not finite.any(): continue values = values[finite] found_rows = found_rows[finite] found_columns = found_columns[finite] nearest_distances.extend(values.tolist()) local_min_index = int(np.argmin(values)) local_min = float(values[local_min_index]) if local_min < min_distance: source_index = start + int(found_rows[local_min_index]) target_index = int(indices[found_rows[local_min_index], found_columns[local_min_index]]) min_distance = local_min closest_points = { "ax": float(coordinates[source_index, 0]), "ay": float(coordinates[source_index, 1]), "bx": float(coordinates[target_index, 0]), "by": float(coordinates[target_index, 1]), } return nearest_distances, min_distance, closest_points def compute_nearest_spacing_grid( segments: list[Segment], cell_size: float, ) -> tuple[list[float], float, dict[str, float] | None]: points = sample_points_from_segments(segments) grid: dict[tuple[int, int], list[int]] = {} min_grid_x = min_grid_y = math.inf max_grid_x = max_grid_y = -math.inf for index, (_, x, y) in enumerate(points): cx = math.floor(x / cell_size) cy = math.floor(y / cell_size) min_grid_x = min(min_grid_x, cx) min_grid_y = min(min_grid_y, cy) max_grid_x = max(max_grid_x, cx) max_grid_y = max(max_grid_y, cy) grid.setdefault((cx, cy), []).append(index) max_ring = int(max(max_grid_x - min_grid_x, max_grid_y - min_grid_y) + 2) if math.isfinite(min_grid_x) else 0 nearest_distances: list[float] = [] min_distance = math.inf closest_points: dict[str, float] | None = None for index, point in enumerate(points): curve_id, x, y = point base_cx = math.floor(x / cell_size) base_cy = math.floor(y / cell_size) seen: set[int] = set() nearest_sq = math.inf for ring in range(max_ring + 1): for cx in range(base_cx - ring, base_cx + ring + 1): for cy in range(base_cy - ring, base_cy + ring + 1): if ring > 0 and base_cx - ring < cx < base_cx + ring and base_cy - ring < cy < base_cy + ring: continue bucket = grid.get((cx, cy)) if not bucket: continue for candidate_index in bucket: if candidate_index == index or candidate_index in seen: continue seen.add(candidate_index) candidate_curve_id, candidate_x, candidate_y = points[candidate_index] if candidate_curve_id == curve_id: continue dx = x - candidate_x dy = y - candidate_y distance_sq = dx * dx + dy * dy if distance_sq < nearest_sq: nearest_sq = distance_sq if distance_sq < min_distance * min_distance: distance = math.sqrt(distance_sq) min_distance = distance closest_points = { "ax": x, "ay": y, "bx": candidate_x, "by": candidate_y, } if math.isfinite(nearest_sq) and ring * cell_size > math.sqrt(nearest_sq) + cell_size * 2: break if math.isfinite(nearest_sq): nearest_distances.append(math.sqrt(nearest_sq)) return nearest_distances, min_distance, closest_points def sample_points_from_segments(segments: list[Segment]) -> list[tuple[int, float, float]]: points: list[tuple[int, float, float]] = [] for index, segment in enumerate(segments): curve_id = int(segment[0]) points.append((curve_id, segment[1], segment[2])) next_segment = segments[index + 1] if index + 1 < len(segments) else None if next_segment is None or int(next_segment[0]) != curve_id: points.append((curve_id, segment[3], segment[4])) return points def cell_bounds(segment: Segment, cell_size: float) -> tuple[int, int, int, int]: return ( math.floor(segment[5] / cell_size), math.floor(segment[6] / cell_size), math.floor(segment[7] / cell_size), math.floor(segment[8] / cell_size), ) def segment_distance(a: Segment, b: Segment) -> tuple[float, Point, Point]: pa, pb = closest_segment_points((a[1], a[2]), (a[3], a[4]), (b[1], b[2]), (b[3], b[4])) return point_distance(pa, pb), pa, pb def closest_segment_points(p1: Point, q1: Point, p2: Point, q2: Point) -> tuple[Point, Point]: d1 = sub(q1, p1) d2 = sub(q2, p2) r = sub(p1, p2) a = dot(d1, d1) e = dot(d2, d2) f = dot(d2, r) s = 0.0 t = 0.0 epsilon = 1e-9 if a <= epsilon and e <= epsilon: return p1, p2 if a <= epsilon: t = clamp01(f / e) else: c = dot(d1, r) if e <= epsilon: s = clamp01(-c / a) else: b = dot(d1, d2) denom = a * e - b * b s = clamp01((b * f - c * e) / denom) if denom != 0 else 0.0 t_nom = b * s + f if t_nom < 0: t = 0.0 s = clamp01(-c / a) elif t_nom > e: t = 1.0 s = clamp01((b - c) / a) else: t = t_nom / e return add(p1, mul(d1, s)), add(p2, mul(d2, t)) def parse_transform(raw: str) -> Matrix: matrix = IDENTITY for name, args_raw in TRANSFORM_RE.findall(raw): args = [parse_float(item) for item in NUMBER_RE.findall(args_raw)] name = name.lower() next_matrix = IDENTITY if name == "matrix" and len(args) >= 6: next_matrix = (args[0], args[1], args[2], args[3], args[4], args[5]) elif name == "translate" and args: next_matrix = (1.0, 0.0, 0.0, 1.0, args[0], args[1] if len(args) > 1 else 0.0) elif name == "scale" and args: sx = args[0] sy = args[1] if len(args) > 1 else sx next_matrix = (sx, 0.0, 0.0, sy, 0.0, 0.0) elif name == "rotate" and args: angle = math.radians(args[0]) cos_a = math.cos(angle) sin_a = math.sin(angle) rotate = (cos_a, sin_a, -sin_a, cos_a, 0.0, 0.0) if len(args) >= 3: next_matrix = multiply_matrix( multiply_matrix((1.0, 0.0, 0.0, 1.0, args[1], args[2]), rotate), (1.0, 0.0, 0.0, 1.0, -args[1], -args[2]), ) else: next_matrix = rotate elif name == "skewx" and args: next_matrix = (1.0, 0.0, math.tan(math.radians(args[0])), 1.0, 0.0, 0.0) elif name == "skewy" and args: next_matrix = (1.0, math.tan(math.radians(args[0])), 0.0, 1.0, 0.0, 0.0) matrix = multiply_matrix(matrix, next_matrix) return matrix def multiply_matrix(left: Matrix, right: Matrix) -> Matrix: a1, b1, c1, d1, e1, f1 = left a2, b2, c2, d2, e2, f2 = right return ( a1 * a2 + c1 * b2, b1 * a2 + d1 * b2, a1 * c2 + c1 * d2, b1 * c2 + d1 * d2, a1 * e2 + c1 * f2 + e1, b1 * e2 + d1 * f2 + f1, ) def transform_point(matrix: Matrix, point: Point) -> Point: a, b, c, d, e, f = matrix x, y = point return a * x + c * y + e, b * x + d * y + f def parse_points(raw: str) -> list[Point]: values = [parse_float(item) for item in NUMBER_RE.findall(raw)] return [(values[i], values[i + 1]) for i in range(0, len(values) - 1, 2)] def parse_svg_length(raw: str | None) -> float: if not raw: return 0.0 return parse_float(raw) def parse_float(raw: str | float) -> float: if isinstance(raw, float): return raw try: return float(raw) except ValueError: match = NUMBER_RE.search(raw) return float(match.group(0)) if match else 0.0 def percentile_value(sorted_values: list[float], percentile: float) -> float: if not sorted_values: return math.inf if percentile <= 0: return sorted_values[0] index = math.floor((percentile / 100.0) * (len(sorted_values) - 1)) return sorted_values[max(0, min(len(sorted_values) - 1, index))] def px_to_mm(px: float) -> float: return (px / DPI) * MM_PER_INCH def scale_closest_points(points: dict[str, float] | None, scale: float) -> dict[str, float] | None: if not points: return None return {key: value * scale for key, value in points.items()} def point_distance(a: Point, b: Point) -> float: return math.hypot(a[0] - b[0], a[1] - b[1]) def lerp_point(a: Point, b: Point, t: float) -> Point: return a[0] + (b[0] - a[0]) * t, a[1] + (b[1] - a[1]) * t def sub(a: Point, b: Point) -> Point: return a[0] - b[0], a[1] - b[1] def add(a: Point, b: Point) -> Point: return a[0] + b[0], a[1] + b[1] def mul(a: Point, value: float) -> Point: return a[0] * value, a[1] * value def dot(a: Point, b: Point) -> float: return a[0] * b[0] + a[1] * b[1] def clamp01(value: float) -> float: return max(0.0, min(1.0, value))