如何基于图约束数据程序化计算顶点坐标以重构图形？

问题背景 #

需根据给定的几何约束数据程序化计算顶点坐标，重构相似形状（比例正确、视觉合理即可）。约束数据采用类Markdown语法，包含：

• 顶点间的连接关系（可选附带长度）
• 部分角度信息
• 角度与距离的代数关系

示例约束数据：

:::geometry 
    ::vertex A [ B | x ] [ C ] [ D ]
    ::vertex B [ D | 4 ] [ C | 7 ]
    ::vertex C [ D | 3 ]
    ::vertex D [ A ]

    ::angle [ A B C | 2a ]
    ::angle [ A D C | 90 ]
    ::angle [ D A C | a ]
    ::angle [ B D C | 180 ]
:::

约束语法格式：

::vertex <name> [ <connection 1 vertex> | <length> ] [ <connection 2 vertex> ]
::angle [ <arm 1> <vertex> <arm2> | <angle> ]

现有方案困境 #

当前将约束转化为非线性方程组（基于欧氏距离和向量夹角公式），用SymPy进行符号求解耗时极久且无可用结果；因缺乏初始猜测值，数值求解也无法开展。示例对应的方程组如下：

x^2 = ( v_A_x - v_B_x )^2 + ( v_A_y - v_B_y )^2

4^2 = ( v_B_x - v_D_x )^2 + ( v_B_y - v_D_y )^2

7^2 = ( v_B_x - v_C_x )^2 + ( v_B_y - v_C_y )^2

3^2 = ( v_C_x - v_D_x )^2 + ( v_C_y - v_D_y )^2

cos(2a) = 
            ( (v_A_x - v_B_x) * (v_C_x - v_B_x) + (v_A_y - v_B_y) * (v_C_y - v_B_y) ) /
            ( sqrt( (v_A_x - v_B_x)^2 + (v_A_y - v_B_y)^2 ) * sqrt( (v_C_x - v_B_x)^2 + (v_C_y - v_B_y)^2 ) )

cos(90) = 
            ( (v_A_x - v_D_x) * (v_C_x - v_D_x) + (v_A_y - v_D_y) * (v_C_y - v_D_y) ) /
            ( sqrt( (v_A_x - v_D_x)^2 + (v_A_y - v_D_y)^2 ) * sqrt( (v_C_x - v_D_x)^2 + (v_C_y - v_D_y)^2 ) )

cos(a) = 
            ( (v_D_x - v_A_x) * (v_C_x - v_A_x) + (v_D_y - v_A_y) * (v_C_y - v_A_y) ) /
            ( sqrt( (v_D_x - v_A_x)^2 + (v_D_y - v_A_y)^2 ) * sqrt( (v_C_x - v_A_x)^2 + (v_C_y - v_A_y)^2 ) )

cos(180) = 
            ( (v_B_x - v_D_x) * (v_C_x - v_D_x) + (v_B_y - v_D_y) * (v_C_y - v_D_y) ) /
            ( sqrt( (v_B_x - v_D_x)^2 + (v_B_y - v_D_y)^2 ) * sqrt( (v_C_x - v_D_x)^2 + (v_C_y - v_D_y)^2 ) )

// set point A to (0,0)
v_A_x = 0
v_A_y = 0

可行解决方案 #

1. 分步几何构造（优先推荐） #

利用几何定理逐步推导坐标，避开全量非线性方程组的求解：

• 固定基准：先固定一个顶点（如A点设为(0,0)），再固定一条边的方向（如设AD在x轴上，D点坐标设为(d, 0)，d作为待求变量）
• 处理线性约束：优先解析线性关系约束，比如示例中∠BDC=180°说明B、D、C共线，结合BD=4、DC=3、BC=7的边长约束，可直接确定三点位置：若D在(d,0)，则B为(d+4, 0)，C为(d-3, 0)
• 代入角度约束求解：将上述坐标代入剩余角度约束，转化为单变量方程。比如示例中∠ADC=90°意味着AC⊥DC，DC在x轴上则AC垂直x轴，即C点x坐标为0，可得d-3=0 → d=3，由此确定D(3,0)、B(7,0)、C(0, y)，再通过∠DAC=a和∠ABC=2a的三角函数关系（二倍角公式）求解y值。

2. 数值优化（适用于复杂约束场景） #

当无法分步拆解约束时，采用数值优化迭代求解：

• 生成初始猜测：基于图的连通性生成初始坐标（如随机布局或树状展开布局），代数变量（如示例中的a）可设为合理初始值（如π/6）
• 构造误差函数：将每个约束转化为误差项，总误差为各项误差之和：
  • 边长约束：(计算长度 - 约束长度)^2
  • 角度约束：(计算夹角余弦值 - 约束夹角余弦值)^2
  • 代数关系约束：将代数变量纳入优化变量，同步优化坐标和代数参数
• 执行优化：通过SciPy的scipy.optimize.minimize调用L-BFGS或梯度下降算法，最小化总误差，直到误差满足视觉合理的阈值（如总误差<1e-3）

3. Pyodide集成方案 #

在TypeScript环境中通过Pyodide调用Python工具链简化开发：

• 用sympy先简化代数约束，求解出代数变量（如示例中的a），再代入计算坐标
• 用shapely验证几何约束的满足情况，辅助调试
• 用scipy.optimize执行数值优化，避免在TypeScript中实现复杂优化逻辑

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