Alexander Smirnov Alexander Smirnov - 3 months ago 14
C# Question

Radial tree graph layout: fix beizer curves

i want to render nice radial tree layout and a bit stumbled with curved edges. The problem is that with different angles between source and target points the edges are drawn differently. Provided pics are from the single graph so you can see how they're differ for different edge directions. I think the point is in beizer curve control points generation and i just can't understand how to fix them.

I want them to be drawn the same way no matter what's the direction of the edge.

How can i achieve this as in Pic1?
How can i achieve this as in Pic2?

Like here: https://bl.ocks.org/mbostock/4063550

Thank you!

Code:



//draw using DrawingContext of the DrawingVisual

//gen 2 control points
double dx = target.X - source.X, dy = target.Y - source.Y;
var pts = new[]
{
new Point(source.X + 2*dx/3, source.Y),
new Point(target.X - dx/8, target.Y - dy/8)
};

//get geometry
var geometry = new StreamGeometry { FillRule = FillRule.EvenOdd };
using (var ctx = geometry.Open())
{
ctx.BeginFigure(START_POINT, false /* is filled */, false /* is closed */);
ctx.BezierTo(pts[0], pts[1], END_POINT, true, false);
}
geometry.Freeze();

//draw it
dc.DrawGeometry(DrawingBrush, DrawingPen, geometry);





UPDATE 1:
I've got the angle between previous vertex and source in radians using the following formula: Math.Atan2(prev.Y - source.Y, source.X - prev.X);
But still i get the edges like in Pic.4.

UPDATE 2
The prev vertex pos for branchAngle calculation is inaccurate so i decided to take an average angle between all edges in a branch as the branchAngle. This approach fails when edges from one brach are around the 180 deg mark and branch can have edge angles like 175, 176.. -176!! I use this code to make them all positive:

var angle = Math.Atan2(point1.Y - point2.Y, point1.X - point2.X);
while (angle < 0d)
angle += Math.PI*2;


But now the angles can be 350, 359.. 2!!! Quite difficult to calc an average :) Can you please advice me how i can work this around?

Pic1
Beizer curve edges - up

Pic2
Beizer curve edges - left

Pic3
enter image description here

Pic4
enter image description here

Answer

Looking at the graph from the link you provided each branch in the tree has it's own angle, which is used to declare the control points of the branch. This branchAngle is the same as the one of the vector going from the first node to the previous one (every branch can spawn several branches in turn). The angle of the first branch (first node = previous node = center) seems to be around -60°.

Setting the type of curve can be done by compensating this branch angle (0°, -90°, -180°,...) for all branches in the tree. Resulting in the controlAngle used for laying out the control points.

Generating the control points while taking into account the angles:

//gen per branch
 double branchAngle = 30 * Math.PI / 180; //e.g., calc vector angle here
 double cosB = Math.Cos(branchAngle);
 double sinB = Math.Sin(branchAngle);     
 //depending on the desired curve compensate -90°, -180°,...
 double controlAngle = branchAngle - (90 * Math.PI / 180); 
 double cosA = Math.Cos(controlAngle);
 double sinA = Math.Sin(controlAngle);

//gen 2 control points
 //calculate dx dy after rotation with branchAngle
 double dxbase = target.X - source.X, dybase = target.Y - source.Y;
 double dx = dxbase*sinB - dybase*cosB
 double dy = dxbase*cosB + dybase*sinB
 //control points based on controlAngle
 var pts = new[]
 {
    new Point(source.X + (2*dx/3)*cosA , source.Y + (2*dx/3)*sinA),
    new Point(target.X - (dx/8)*cosA + (dy/8)*sinA, target.Y - (dx/8)*sinA - (dy/8)*cosA)
 };

Branch

Quick check branchAngle = 30° & compensation = -90° -> controlAngle = -60°