I am given a bunch of graph contrain data:

• Which vertex is connected to which vertex, optionally with length
• Some angles
• Angles and distances may be algebra relations

How can I use them to programmatically calculate the coordinates of each vertex so I can reconstruct the graph? The result only needs to be a similar shape, aka proportionally correct & scales freely. The result does not have to be highly accurate, it only has to "look about right".

For example: I have these data:

:::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 ]
:::

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

I need to reconstruct this shape from the given data (geometry problem in image is not relevant)

The markdown-like syntax can represent any shape made of vertex and edges, as long as everything is connected.

If it helps, I'm on typescript with access to some python libraries via pyodide.

My current approach is to express the data as a system of equations that solves to the coordinates. Currently, I'm using the Euclidean distance formula and the angle between two vector formula. However, these equations are highly non-linear and complicated. Solving symbolically using sympy takes way too long and does not produce a usable final result. I can't solve by estimating either because I don't have any starting guess.

For example, for the data above, I have these equations

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

I am given a bunch of graph contrain data:

• Which vertex is connected to which vertex, optionally with length
• Some angles
• Angles and distances may be algebra relations

How can I use them to programmatically calculate the coordinates of each vertex so I can reconstruct the graph? The result only needs to be a similar shape, aka proportionally correct & scales freely. The result does not have to be highly accurate, it only has to "look about right".

For example: I have these data:

:::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 ]
:::

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

I need to reconstruct this shape from the given data (geometry problem in image is not relevant)

The markdown-like syntax can represent any shape made of vertex and edges, as long as everything is connected.

If it helps, I'm on typescript with access to some python libraries via pyodide.

My current approach is to express the data as a system of equations that solves to the coordinates. Currently, I'm using the Euclidean distance formula and the angle between two vector formula. However, these equations are highly non-linear and complicated. Solving symbolically using sympy takes way too long and does not produce a usable final result. I can't solve by estimating either because I don't have any starting guess.

For example, for the data above, I have these equations

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

• typescript
• graph-theory
• computational-geometry

• I would try an iterative solution. First, notice that any solution can be freely rotated or translated. This means you're allowed to choose an edge of known length and fix its position (fix its two incident vertices: if edge AB has length L, fix A (0,0) and B(L,0)). I suggest choosing two such vertices that have the most neighbours with known information. Then iteratively try to increase the number of vertices that have a known position. You can fix a vertex C if you already have fixed A and B, and know angle ABC and length BC; or (up to 2 positions) if you know lengths AC and BC. – Stef Commented Mar 11 at 15:36

1 Answer 1

• In the triangle BAD:
  • BDA is a right-angle;
  • ABD = 2α;
  • Since the interior angles of a triangle add up to 180° then BAD = 90-2α.
• In the triangle ACD:
  • ADC is a right-angle;
  • DAC = α; therefore
  • Since the interior angles of a triangle add up to 180° then ACD = 90-α
• Considering the triangle ABC then
  • ABC = 2α
  • BCA = DCA = 90-α
  • CAB = CAD + DAB = α + 90-2α = 90-α
• Since the triangle ABC has two identical angles, it is an isosceles triangle and the distance AB = BC = 7.

Programmatically, you can spot that:

• Vertices B, D and C all lie on a straight line and, for example, could be represented with the co-ordinates (0, 4), (0, 0) and (0, -3).
• Vertex A lies on a line which goes through D and is perpendicular to the BC line so could have the co-ordinates (y, 0).
• You then have two right-angle triangles that share the edge AD with an unknown length y.
• Using basic trigonometry functions:
  • tan(2α) = AD/BD = y/4
  • tan(α) = CD/AD = 3/y
• Rearranging and substituting one equation into the other gives you tan(2α)tan(α) = 3/4
• You can find an approximate solution using numerical methods such as interval bisection which gives you a solution that α is approximately 0.4812 radians.
• Again, using basic trigonometry, cos(2α) = BD/AB.
• Rearranging, then AB = BD/cos(2α) ~= 4/cos(0.9624) ~= 7.000495 (very close to 7 given that we are only using an approximation of α).