基于Python与svgpathtools递归查找样条网格对齐切线点的技术问询

你当前通过步进采样的方式查找样条曲线的水平/垂直切线点，虽然精度足够时有效，但效率和精度优化空间很大。以下是成熟的解决方案和搜索范围缩小指引：

当前实现代码 #

def approx_flex_points_recursive(spline, start=0, end=1, precision=10000):
    number_of_steps = precision
    step = 1 / (number_of_steps - 1)
    p = start
    e = 10 / number_of_steps

    relevant_points = []

    while p <= end:
        unit = spline.unit_tangent(p)

        if (abs(unit.real) < e) or (abs(unit.imag) < e):
            relevant_points.append([ p, unit.real, unit.imag])
        p += step    
    return relevant_points    

成熟解决方案与优化思路 #

1. 用数值优化方法替代递归遍历 #

• 二分法：找到初步候选区间后，在区间内用二分法迭代求解切线实部（垂直切线）或虚部（水平切线）趋近于0的点。这种方法收敛速度远快于步进采样，精度可控。
• 利用scipy优化模块：使用scipy.optimize.root_scalar直接求解目标方程（unit_tangent(t).real = 0 或 unit_tangent(t).imag = 0），无需自行实现递归，稳定性更高。

2. 缩小搜索范围的关键步骤 #

• 粗采样定位候选区间：先用低精度（如100步）快速扫描曲线，找到切线实部/虚部接近阈值的区间（而非单个点）。后续仅在这些区间内精细搜索，避免全局高采样的资源浪费。
• 利用样条导数特性：svgpathtools中的样条曲线导数是低阶多项式（如贝塞尔曲线的导数是低阶贝塞尔曲线），可先推导导数的根的大致范围，这些范围就是水平/垂直切线可能出现的区域，进一步缩小搜索范围。

改进实现示例 #

import svgpathtools as svg

def find_candidate_intervals(spline, coarse_precision=100, threshold=0.1):
    intervals = []
    step = 1 / (coarse_precision - 1)
    prev_t = 0
    prev_unit = spline.unit_tangent(prev_t)
    for i in range(1, coarse_precision):
        t = i * step
        unit = spline.unit_tangent(t)
        # 检测跨越切线阈值的区间
        if (abs(unit.real) < threshold or abs(prev_unit.real) < threshold) and (unit.real * prev_unit.real <= 0):
            intervals.append((prev_t, t))
        if (abs(unit.imag) < threshold or abs(prev_unit.imag) < threshold) and (unit.imag * prev_unit.imag <= 0):
            intervals.append((prev_t, t))
        prev_t = t
        prev_unit = unit
    # 去重相邻区间
    unique_intervals = []
    for interval in intervals:
        if not unique_intervals or interval[0] > unique_intervals[-1][1] + 1e-6:
            unique_intervals.append(interval)
    return unique_intervals

def refine_with_bisection(spline, interval, target='vertical', tol=1e-8, max_iter=50):
    t_start, t_end = interval
    def func(t):
        unit = spline.unit_tangent(t)
        return unit.real if target == 'vertical' else unit.imag
    
    # 二分法迭代求解
    for _ in range(max_iter):
        t_mid = (t_start + t_end) / 2
        f_mid = func(t_mid)
        f_start = func(t_start)
        if abs(f_mid) < tol:
            return t_mid
        if f_mid * f_start < 0:
            t_end = t_mid
        else:
            t_start = t_mid
    return (t_start + t_end) / 2

def find_flex_points(spline):
    intervals = find_candidate_intervals(spline)
    flex_points = []
    for interval in intervals:
        # 优化垂直切线点
        t_vert = refine_with_bisection(spline, interval, 'vertical')
        if abs(spline.unit_tangent(t_vert).real) < 1e-6:
            flex_points.append(('vertical', t_vert, spline.point(t_vert)))
        # 优化水平切线点
        t_horiz = refine_with_bisection(spline, interval, 'horizontal')
        if abs(spline.unit_tangent(t_horiz).imag) < 1e-6:
            flex_points.append(('horizontal', t_horiz, spline.point(t_horiz)))
    # 去重相近点
    unique_points = []
    seen_ts = set()
    for pt in flex_points:
        t_val = pt[1]
        if not any(abs(t_val - t) < 1e-6 for t in seen_ts):
            seen_ts.add(t_val)
            unique_points.append(pt)
    return unique_points

这个实现先通过粗采样锁定候选区间，再用二分法精细求解，兼顾了效率和精度，比原递归步进方案更高效可靠。

内容的提问来源于stack exchange，提问作者simone