Good rain knows the season, when spring is happening. The wind into the night, moisten things silently. – du fu

The introduction

There are a lot of curve-related scenes in the field of graph visualization, but it is not easy to get a suitable curve. I recently encountered this problem with AntV G6. The shape is flat, the arrow direction is inconsistent with the line trend, the line start and end are hidden, and so on. Beautiful curves are always similar, while ugly curves have their own problems. How do I get a nice curve? Check it out.

The problem

AntV G6 has a cubic vertical line, that is, a third-order Bezier curve in the vertical direction, but this line does not support incoming control points. The wire itself is ugly and can’t handle some extreme cases, as shown below. The curve in FIG. 2 is too flat, and the deviation Angle of the line trend and the end arrow direction is too large. In Figure 3, the arrow and the starting point of the line are completely obscured.

Figure 1

Figure 2

Figure 3

Other graph editing products wired

The stone of another mountain can attack jade. In order to improve the user’s connection experience, we compared the connection scheme of other graph editing products. A total of 4 similar well-known products were found. IO and Processon are more graph-editing oriented, and both support Bezier curves, allowing users to change the shape of curves by dragging and dropping control points. But this kind of interaction leaves the task of optimizing the curve to the user, which is different from our goal. In addition, DataV’s Blueprint editor and AntV X6 examples are lightweight graph editing scenarios, both of which are optimized by adjusting Bessel curves three times for better connection. Each connection scheme is detailed below.

Draw.io

Draw. IO is very focused on graph editing, support for third-order Bezier curves, higher-order Bezier curves, users can drag and drop control points to generate arbitrary complex, arbitrary shape curves. As you can see below, draw. IO allows you to add or subtract control points while dragging curves, adjust the connection position of anchor points, and adjust the direction of the end arrows.

Figure 4.

The advantages of draw.io are:

  1. Support dynamic add and delete control points, users can draw almost any shape of the curve.
  2. When dragging a curve or control point, the position of the anchor point connection and the direction of the arrow at the end can be adjusted adaptively for better results. As shown above.

Its disadvantages are:

  1. The interaction is more complex and difficult to get started.
  2. Complex implementation, dynamic add and delete control point logic complex.

ProcessOn

Processon also focuses on graph editing, but only supports third-order Bezier curves. You can adjust the shape of the curves by dragging and dropping control points, which automatically adjust the direction of the arrows. The control point of Processon is outside the curve, conforming to the original definition of Bezier curve. In addition, there are auxiliary lines between the control point and the beginning and end of the curve, so that users can perceive the action mode of the control point on the curve shape.

Figure 5

The advantages of Processon are:

  1. The direction of the end arrow is automatically adjusted as you drag the control point.
  2. The interaction of control points is simple and there are guides to help the user understand.

Its disadvantages are:

  1. After dragging the curve and then dragging the node, the shape of the curve changed greatly.
  2. As with Draw. IO, curve shape optimization is left to the user.

DataV’s blueprint editor

DataV’s blueprint editor only supports third-order Bezier curves and does not support drag and drop control points, but the wiring works well and the arrows at the end of the wiring adjust their shape adaptively as they drag nodes.

In addition, the blueprint editor restricts whether the anchor points are output or input, such as specifying that the anchor points to the left of the node only support input and the anchor points to the right of the node only support output. This setting reduces the number of special cases that need to be handled by the wire.

Figure 6.

The benefits of the DataV blueprint editor are:

  1. The line is a simple Bessel third-order curve, which only adjusts the parameters of control points to adapt to the shape formed by dragging nodes.
  2. When the node is dragged, the connection changes smoothly.

Its disadvantages are:

  1. The shape of the end arrow and the curve do not fit perfectly, as shown by the orange arrow in the figure above.

AntV X6

AntV X6 has similar effects to the blueprint editor, but is implemented differently. The example also restricts whether an anchor is input or output based on its position relative to the node. The X6 example achieves better alignment by adding two straight lines to each end of the Bezier curve, as shown below.

Figure 7.

The advantages of X6 implementation are:

  1. The realization method is simple, only add straight lines at both ends of Bezier curve, and the parameters of Bezier curve are fixed.
  2. The interaction effect is relatively smooth.

Its disadvantages are:

  1. Bezier curve parameters are fixed and the curve is too “bent” when the nodes are close to each other, as shown in the figure below.

Figure 8.

Attachment to optimize

This curve optimization is mainly based on AntV X6 examples and DataV blueprint editor ideas.

Add the line

Design ideas

The first is to use X6’s idea to add straight lines at both ends of the line. The focus of this scheme is to calculate the starting point and end point of the first and last two straight lines. As shown in the figure below, the straight line extends in different directions according to the direction of the anchor point relative to the node. In the figure, the connecting anchor point of the left starting node is located below the node, so the starting line extends downward, while the connecting anchor point of the ending node is located above the node, so the ending line extends upward. The connection anchor point of the starting node in the figure on the right is located on the right side of the node, so the connection of the starting end should extend to the right.

Figure 9.

Implementation scheme

To verify the correctness of our thinking, we first analyze the curve of AntV X6.

Collect data
The attachment shape Path
M -335 -185 L -335 -181 C -335 -101 -165 -194 -165 -114 L -165 -110
M -375 -75 L -375 -71 C -375 9 -165 -194 -165 -114 L -165 -110
M -255 -95 L -255 -91 C -255 -11 -175 -324 -175 -244 L -175 -240
The reflex law

According to the data of path column in the table above, it can be seen that AntV X6 can add lines at both ends of Bezier Curve in the following ways: MoveTo starting point, LineTo starting point of Bezier Curve, Curve, third-order Bezier Curve, and finally LineTo ending point. In the third case, m-255-95 is to move to the point (-255, -95), and then L-255-91 is to draw a line from the point (-255, -95) to the point (-255, -91). Then, c-255-11-175-324-175-244 takes (-255, -11) as the first control point, (-175, -324) as the second control point, and (-175, -244) as the end point of Bezier curve to draw Bezier curve. Finally l-175-240 is to draw a straight line from (-175, -244) to (-175, -240). To summarize, the coordinates in the first and last commands are the starting and ending points of the line, respectively. The two lines are 4 units away from the starting (ending) point in the y direction, and the y coordinates of the two control points of the Bessel curve are respectively the y coordinates of the starting (ending) point + (-) 80, and the X coordinates of the two control points are the same as the X coordinates of the starting (ending) point.

Expressed in the formula:

startPoint, endPoint
M startPoint.x  startPoint.y
L startPoint.x   startPoint.y+4
C startPoint.x  startPoint.y+4+80   endPoint.x endPoint.y-4-80  endPoint.x endPoint.y-4
L endPoint.x endPoint.y
Copy the code

The actual effect

According to the position of the anchor point relative to the node, the extension direction of the straight lines at both ends can keep the arrow at the end of the line in the correct direction. Meanwhile, the straight lines at the beginning and end of the line also ensure that the direction of the line can be accurately perceived by the user. As shown in the figure below, the left side of the figure is the default cubic-vertical curve. The line in the red circle in the figure either cannot show the direction of the anchor point relative to the node at the starting end, or the arrow at the end is hidden, both of which will seriously affect the user’s perception of the line direction. The line in the picture on the right completely avoids these two problems, and the line direction is clearer, smoother and more in line with the user’s psychological perception.

Figure 10.

To be improved

However, this solution is not perfect, and there are still two problems to be solved simply by adding lines at both ends of the Bezier curve.

  1. The above scheme uses a Magic Numbe, constant 80, when calculating the control points of the middle Bezier curve, resulting in a strange shape of the curve when the two nodes are close to each other, as shown in the figure below.

    Figure 11.

The core of the above problem lies in that we do not have an accurate understanding of the relationship between the control points of Bessel curve and the curve shape, and cannot understand the principle behind Magic Number. The corresponding solution is to understand the control points of Bessel curve. Change the Magic Number to Func (startPoint, endPoint).

  1. The above scheme does not perceive the user’s connection direction in the process of curve connection, resulting in great changes in the shape of arrows and curves in the process and results of curve connection. As shown in the figure below, the left is the shape and arrow direction of the curve during the connection process, and the right is the shape and arrow direction of the curve after the connection is completed. The core of this problem is to accurately perceive the direction that users want to connect in the process of connection. The approach of the above scheme is to directly equate the connection direction with the opposite direction of the starting connection anchor point to the node.

    Figure 12

The solution to this problem is to determine the direction of the connection line according to the position of the coordinate at the end of the connection line relative to startPoint. The transformation effect is shown in the figure below.

Figure 13

Optimize the parameters of bezier curve

In addition to the AntV X6 wiring scheme, we also want to borrow Bessel curves from the DataV Blueprint Editor. Having “reverse-engineered” the wiring in the AntV X6 example above, we intend to do the same for Bessel curves in the DataV Blueprint Editor.

Implementation scheme

Collect data
The curve shape Path Shift the starting point to the origin of coordinates
M 586.5 336 C 532.7496710549095 336 545.2503289450905 335.5 491.5 335.5 M 0 0 C -54 0 -41 0 -95 0
M 662.5229 C 603.0729185103246 229 626.9270814896754 159.5 567.5 159.5 M 0 0 C -60 0 -36 -70 -96 -70
M 640.5 304 C 571.5182334289478 304 648.481766571022 160.5 579.5 160.5 M 0 0 C -69 0 8 -144 -61 -144
M 457.5 345 C 372.2029329439616 345 664.7970670560384 160.5 579.5 160.5 M 0 0 C – 85 0 207 -185 122 -185
M 310.5 302 C 204.51346747613758 302 685.4865325238624 160.5 579.5 160.5 M 0 0 C -106 0 375 -142 269 -142
M 269.5 15c 164.2498961794736 158 675.7501038205264 157.5 570.5 157.5 M 0 0 C -105 0 406 0 301 0
M sx sy, C x1 y1 x2 y2 x3 y3, sy === y1, y2 === y3 M 0 0, C x1 y1 x2 y2 x3 y3, x1 + x2 === x3, y1 + y2 === y3

As shown in the above table, we collected paths corresponding to Bessel curves of different shapes and tried to find out the rules directly. The first column is the shape of the curve, the second column is the Path corresponding to the curve, and the third column is the data after the starting point of the curve is shifted to the origin of the coordinates.

Find a pattern?

As shown in the last row of the table above, the second column only finds the law of y1 and y2 coordinates, that is, the way of calculating the y coordinates of control point 1 and control point 2. In the equation described in the third column, there is only one ** binary equation about x1 and x2. ** at this time, x1 and x2 cannot be solved. We need at least one equation about x1 and x2 to find the coordinates of the control points.

But how do you find another equation for x1 and x2? Try combining number and form first, number invisible is not intuitive.

Figure 14

As shown in the figure above, the black curve in the figure corresponds to the four data in the table above. We use the data in the third column to draw this figure, hoping to facilitate comparison and discovery of rules by centralizing the starting points to the origin. Each bend of the red curve in the figure is a control point.

We can learn the following from the picture:

  1. The two control points are symmetric with respect to the midpoint of the curve, that is, only one control point is required to obtain the other control point.
  2. The distance between the two control points in the x direction is greater than the distance between the two starting points in the x direction.
  3. The distance from the control point to the starting point in the x direction is different for curves with different shapes, that is, the distance from the control point to the starting point in the X direction is not constant.

After these conclusions, combined with the rules in the table, we found that in fact, as long as we calculate the coordinates of a single control point, we can get the coordinates of another control point. The only coordinate required for a single control point is its X coordinate, that is to say, only the distance from the control point in the X direction to the starting point is required.

To put it another way, we should only know the beginning and end of a curve before drawing it. That is, the controlPoint x coordinate should be calculated according to the starting point and ending point, that is, controlPoint. X = F (startPoint, endPoint). X = F (startpoint.x, endpoint.x), that is, the x-coordinate of the controlPoint is only determined by the x-coordinate of the starting point and ending point.

Get some more data to verify it!

The curve shape Path
M 490.5-146 C 439.937215047561-146 494.0627849524329-213.5 443.5-213.5
M 490.5-89 C 427.23097348884403-89 506.76902651115597-213.5 443.5-213.5

As shown in the above table, the x coordinates of the starting and ending points of the two curves are the same respectively, but the control points are also different because of the different shapes of the curves! X = F (startPoint, endPoint)

But how do you figure out F?

Dig out

By observing controlPoint. X = F (startPoint, endPoint) and combining with FIG. 14, we can find that coordinate translation does not change the shape of the curve, and the meaningful data for calculating control points should be the distance between the starting point and ending point in the x direction and the y direction. That is, controlPoint.x = F(startPoint, endPoint) ctrlDistanceX = F(distanceX, distanceY).

Looking for F is really looking for patterns. Can you use the method in probability and statistics to fit it? Maybe the rules are simple enough, but you can draw them first. But the first step is to collect more data.

  1. More data

To make it easier to collect more data, we will directly click the code in the console of the Blueprint editor page.

const data = [];
const func = () = > {
  const targetPath = document.querySelector('.butterflies-link');
  data.push(targetPath.getAttribute('d'));
}
const intervalId = setInterval(func, 1000);
Copy the code

Then drag the node, change the shape of the curve, and finally clearInterval(intervalId), and then enter data in the console, copy and paste the obtained data.

The data after de-weighting is as follows:

        "M 524.5 72 C 402.67229108270203 72 527.327708917298-275.5 405.5-275.5"."M 587.5-53 C 485.63630523692785-53 507.36369476307215-275.5 405.5-275.5"."M 523.5-85 C 437.4786592002655-85 491.5213407997345-275.5 405.5-275.5"."M 407.5 173 C 265.3738851783404 173 547.6261148216596-275.5 405.5-275.5"."M 600.517c 482.61468766056527 17 523.3853123394347-275.5 405.5-275.5"."M 600.517c 481.18236106456914 17 939.8176389354309-264.5 820.5-264.5"."M 514.5-1c 383.54572507813253-1 951.4542749218674-264.5 820.5-264.5"."M 355.5-25c 194.73655661844936-25 981.26344315506-264.5 820.5-264.5"."M 355.5-25 C 203.2729443821868-25 952.7270556178132-227.5 800.5-227.5"."M 355.5-25 C 251.76642131972704-25 751.2335786802729-66.5 67.5-66.5"."M 609.592 C 538.7521089502782 92 718.2478910497218-66.5 67.5-66.5"."M 609.592 C 538.5661738289713 92 717.4338261710287-67.5 66.5-67.5"."M 609.5 9c 473.7472665837899 92 461.2527334162101-221.5 325.5-221.5"."M 309.5 12c 193.03243021224662 124 441.9675697877534-221.5 325.5-221.5"."M 441.5-199 C 381.95950872107915-199 385.04049127892085-221.5 325.5-221.5"."M 441.5-255 C 360.8441452051197-255 428.1558547948803-75.5 347.5-75.5"."M 441.5-255 C 301.5519298714161 -255 496.4480701285839 176.5 356.5 176.5"."M 242.5-257 C 100.44023636915881-257 498.559736308412 176.5 356.5 176.5"."M 242.5-257 C 93.61264522666846-257"."M 649.5-258c 544.334246633342-2589 40.5 613.5 40.5"."M 649.5-257c 560.515759520021-25712.484240479979-23.5 63.5-23.5"."M 649.5-258c 597.489704113753-2589 614.5102958862437-244.5"."M 649.5-259c 597.4202440004424-259.76-250.5 561.5-250.5"."M 641.5-242 C 591.3874261965307-242 611.6125738034693-250.5 561.5-250.5"."M 317.529c 194.74486200215108 29 684.2551379978489-250.5 561.5-250.5"."M 600.5-79c 526.5303726988732-79 635.4696273011268-250.5 561.5-250.5"."M 600.5-79c 525.5554160660041-79 685.4445839339959-258.5 610.5-258.5"."M 600.5-79c 491.4951544207572-79 1025.5048455792428-75.5 916.5-75.5"."M 570.5 140 C 438.59432977012517 140 1048.4056702298749-75.5 916.5-75.5"."M 568.5 176 C 465.1543925991474 176 800.8456074008526-87.5 697.5-87.5"."M 568.5 176 C 453.3999669506527 176 537.6000330493473-131.5 422.5-131.5".Copy the code
  1. Process the data

Convert the data format to calculate the distance from the first control point in the x direction to the starting point, the distance between the starting point and the end point in the X direction, and the distance between the starting point and the end point in the Y direction.

     // The distance between the first control point in the X direction and the starting point
     [
        121.82770891729797.101.86369476307215.86.0213407997345.142.1261148216596.117.88531233943473.119.31763893543086.130.95427492186747.160.76344338155064.152.2270556178132.103.73357868027296.70.74789104972183.70.93382617102873.135.7527334162101.116.46756978775338.59.540491278920854.80.65585479488033.139.94807012858388.142.0597636308412.148.88735477333154.105.16575433666583.88.98424047997901.52.01029588624374.52.07975599955762.50.11257380346933.122.75513799784892.73.96962730112682.74.94458393399589.109.00484557924278.131.90567022987483.103.3456074008526.115.1000330493473,]// The distance between the beginning and the end in the X direction
			[
        119.182.118.2.195.220.306.465.445.292.38.37.284.16.116.94.85.114.371.36.26.87.88.80.244.39.10.316.346.129.146,]// The distance between the starting point and the ending point in the Y direction
      [
        347.5.222.5.190.5.448.5.292.5.281.5.263.5.239.5.202.5.41.5.158.5.159.5.313.5.345.5.22.5.179.5.431.5.433.5.297.5.298.5.234.5.13.5.7.5.8.5.279.5.171.5.179.5.3.5.215.5.263.5.307.5,]Copy the code

  1. Try to analysis

    I can’t see anything directly. Let’s draw a picture.

    Figure 15

    In the figure, the abscissa is the ID of different Bezier curves, the ordinate is the distance, the red broken line is the distance from the first control point to the starting point in the x direction, the blue broken line is the distance between the starting point and the ending point in the X direction, and the green broken line is the distance between the starting point and the ending point in the y direction.

    I can’t seem to see any trends, so make a list.

    Figure 16

    The red line is always between the blue line and the green line, and it’s kind of like a mean relationship, so it should be of the form z = Ax + by. Here, I tried a = b = 0.5 | 0.4… And observe the fitting degree of the broken line and red broken line obtained by different calculation results. As shown in the figure below, the black discount is the calculation result when a = b = 0.5, but the optimal result is definitely not a trial result…

    Figure 17

  2. Least square method

One way to fit a curve is the least square method, but I won’t show you how it works here. Anyway, assuming that the red polyline fits the blue polyline and the green polyline in the form of z = ax + BY, the least square method will help us find the most accurate a and B.

import numpy as np
from scipy import optimize		# Least square fitting


def func(x, y, p) :
	Z =ax+by :param x: independent variable x: param y: independent variable y: param p: fitting parameters a, b ""
	a, b = p
	return a * x + b * y

def residuals(p, z, x, y) :
	Obtain the difference between the data z and the fitting function.
	return z - func(x, y, p)

xSource = [80.87.88.116.38.37.39.10.94.118.26.182.129.292.36.316.146.16.195.220.119.244.306.346.284.85.114.2.371.445.465]
ySource = [8.5.13.5.7.5.22.5.158.5.159.5.171.5.179.5.179.5.190.5.234.5.222.5.263.5.41.5.298.5.3.5.307.5.345.5.292.5.281.5.347.5.279.5.263.5.215.5.313.5.431.5.433.5.448.5.297.5.202.5.239.5]
cSource = [50.11.52.01.52.07.59.54.70.74.70.93.73.96.74.94.80.65.86.02.88.98.101.86.103.34.103.73.105.16.109.0.115.1.116.46.117.88.119.31.121.82.122.75.130.95.131.9.135.75.139.94.142.05.142.12.148.88.152.22.160.76]
	

def main() :

  x = np.array(xSource)
  y = np.array(ySource)
  z = np.array(cSource)  # Data is arbitrary
  
  plsq = optimize.leastsq(residuals, np.array([0.0]), args=(z, x, y))  # Least square fitting
	# [0, 0] is the initial value of parameters A and b
  
  a, b = plsq[0]  # Obtain the fitting results
  print("what >>>>>")
  print("Fitting result :\na = {}".format(a))
  print("b = {}".format(b))

main()
Copy the code

A = 0.22320872185884902, b = 0.28534578186377385, corresponding to the figure is the following effect. The red broken line is the target broken line, and the black broken line is the fitting result.

Figure 18

With a and B, there is a method for calculating the control points of the Bezier curve. Let’s go back to the canvas.

The actual effect

Compare the legacy issues in the previous section, “To be improved,” as shown in the figure below. As you can see, we’ve solved the problem in the last video perfectly by modifying the way we calculate the control points of the Bezier curve.
Figure 19

Looking to the future

The problem that remains is that we only know why, not why. We can provide the best Bessel curve shape in graph editing scenario, but it is not clear how to describe the rule of influence of control points on curve shape, so we cannot provide Bessel curve of arbitrary shape (style). In the future, we can consider making a small tool that first allows users to drag and drop control points to generate several curves of a certain style, and then deduce the calculation method of control points through the program and output it to the user.

conclusion

Aiming at the problem of line optimization in graph editing scene, we refer to the AntV X6 example and the line optimization in DataV blueprint editor, and optimize the curve shape by adding lines at both ends of Bezier curve and optimizing the calculation method of control points of Bezier curve. Compared with the original cubic-vertical curve in AntV G6, the user experience of the connection is greatly improved.

Author: ES2049 / Jinks

The article can be reproduced at will, but please keep this link to the original text.

You are welcome to join ES2049 Studio. Please send your resume to [email protected]