Orthogonal lines in drawing technology support custom turning points

The core content of this article is written by @huanhuanwa , a girl from our drawing team, who introduces the magic function recently supported for flow charts: orthogonal lines support custom turning points. The following is the text.

Introduction

The connections in our flowchart business currently support three forms: straight lines, curves and orthogonal lines. The most complex of these is the orthogonal line. Previous articles on the implementation of orthogonal lines have been introduced in detail ( Drawing technology flow chart orthogonal connection algorithm ), and what I want to share today is based on this Supports custom turning points.

What is a custom turning point? Everyone knows that two points determine a straight line. Looking at the orthogonal line below, we can see that it is composed of four points:

The path of this connection is determined based on the A* algorithm(through source and target). Points a and b are calculated points and are not stored in the data. So if I want to drag the connection between the source and target, I can To convert to other forms, you need to store a specific turning point on this line to complete.

As shown in the figure below, when the [source, a] connection is dragged upward, points [d, a’] are added. These data points that are not on the default orthogonal connection are called custom turning points.

Technical process

The implementation process can be said to be very difficult, and a total of four versions were modified before and after to achieve the current effect.

Version 1.0

Let’s take this connection as an example, because by default the drawing of the orthogonal connection is calculated based on the source and target, points a and b are not actually stored in the data points, which makes it impossible to directly draw based on the existing data. Click to add/modify points, so the solution for version 1.0 is:

• When dragging is detected, obtain the index of the current dragged line segment in the entire orthogonal connecting line segment
• Get all the turning points on the orthogonal connection
• Find the turning point to be modified based on the point and index obtained above, and modify the turning point according to the drag distance
• Store the modified data points into the data together with other turning points on the connection line

Because all points are stored in the data, each drag is rendered based on the result of the previous drag. This is convenient for calculation to a certain extent, but the core problem is also this, because all points are stored in the data. , it means that it is impossible to distinguish whether the point has been dragged based on the data. There are several scenarios where this cannot be achieved:

1. Unable to distinguish on the UI: dragged line segments and undragged line segments
2. If you drag the source and target nodes of the connection, the default orthogonal connection will be recalculated, but at this time all the turning points on the current connection have been recorded in the data, and some automatic adjustments cannot be made

So after discussion, a general direction of implementation was confirmed: When dragging, only the points that have been dragged in the orthogonal connection are stored, and when the source and target are dragged, the stored data points are not modified.

Version 2.0

There are two conditions for adding points. The first is to determine where to insert, and the second is to determine how to insert. So the processing idea of this version is as follows:

• When drag is detected, get the index of the current dragged line segment
• Based on the actually rendered turning points (renderKeyPoints) of the orthogonal connection and the points in the data (dataPoints), confirm the following modification situations (3 situations), and obtain the corresponding deleteCount and index
• Modify the data in dataPoints based on index and deleteCount

① Add two points: The data in dataPoints does not exist in renderKeyPoints, deleteCount = 0, index = 1 In the figure below, the red points represent points that already exist in dataPoints, purple represents modified points, and blue represents new points:

Move the dotted line A to the right, and add two new points [a, b] at the position of index=1 in dataPoints（dataPoints is a field of line, which stores connection points. [0] and [length-1] represent the starting point and end point, and the middle point represents a custom point）

② Add a point, modify a point: The data in dataPoints exists in renderKeyPoints, deleteCount = 1, index = 1)

Move the dotted line A downward, find the position of index = 1 in dataPoints, delete point a, and add point a’ b

③ Modify two points: There are two data in dataPoints in renderKeyPoints, deleteCount = 2, index = 1

Move the dotted line A to the right, find the position of index = 1 in dataPoints, delete points a, b, and add a’, b’

This version has actually determined the general processing idea, but the scenario considered when calculating deleteCount at the beginning was too simple. These judgment conditions are no problem when the connected source and target are not dragged. Once dragged, the data in dataPoints There is no correspondence in renderKeyPoints.

As shown in the figure below, when the source element is moved upward, point a in dataPoints is no longer on the actual rendering connection (solid line). At this time, the correct result cannot be obtained by simply judging the renderKeyPoints in dataPoints. When dragging [a’, b] to the right, according to the original algorithm, the result is “add one point, modify one point”, but in fact it should be “modify two points”.

Description of the situation:
1. The dotted line in the figure represents the position before dragging, and the solid line represents the position after dragging (after dragging, the data points will not completely match the real path, resulting in dirty path points)
2. dataPoints refers to the custom turning points stored in the data structure, which is the data that needs to be persisted.
3. renderKeyPoints is the turning point of the currently rendered orthogonal line, which needs to be calculated dynamically.

Drag [a’,b] to the right, modify point a to a’ and point b to b’ in dataPoints

Version 3.0

This version mainly deals with errors in obtaining deleteCount and index. This error occurs after dragging the source and target of the connection. We cannot find the corresponding point in the existing data points dataPoints based on the actually rendered connection renderKeyPoints. , it is impossible to determine the index and deleteCount of the data to be modified. To solve this situation, we adopt the idea of n-point collinearity.

For example, in the above figure, although point a is not on the connection line, points a, a’, and b are on a straight line. When dragging the line segment [a’, b], the actual modification can be determined by using three points on a straight line. The point is [a, b], thus getting the correct index and deleteCount

For another example, in the above picture, points a and b are not on the connecting line, but points a, b, a’, b’ are on a straight line, so when dragging the line segment [a’, b’], through Four points are collinear to find the point [a,b] to be modified, so as to obtain the correct index and deleteCount

Just when we thought we were finally done, we discovered that this calculation method could not cover all scenarios.

As shown in the figure above, when two points [a, b] are first generated in dataPoints, drag the source, and then drag the line segment A. At this time, the [c, d] at both ends of the line segment A are not the same as the original data [a, b]. Without any connection, it is impossible to determine the index of data to be inserted.

Version 4.0

In addition to solving the problems of version 3.0, this version also solves the most important data rendering problem.

In version 1.0, we confirmed that when dragging the source and target, the data will not be modified. Then the problem arises. As shown in the figure below, when two points [b, c] are first generated in dataPoints, then the source and target are dragged. , the points stored in the data at this time are [a, b, c, d], but if the connections are rendered in this order, it is definitely not what we want. So how to render the correct connections based on the data points?

This question may be more basic, because in this case only the connection is as expected, and the subsequent drag adjustment of the turning point may be correct. The solid connection in the above picture should be an orthogonal line as expected. It can be seen that the actual The rendered connection passes through the straight line where the custom turning point [b, c] formed by dragging is located, but does not pass through the [b, c] point. There is a rule here: After the position of the element associated with the orthogonal connection changes, the actual The rendered turning point needs to be appropriately corrected based on the position of the associated element, but it must be ensured that it passes through the straight line where the custom turning point is located.

The implementation of this block relies on two key functions, getMidKeyPoints and getMirrorDataPoints. You can first look at the explanation in the following paragraphs:

midKeyPoints:

The points of the standard orthogonal connection between two data points. If the connection between the two data points is not connected (the straight line formed by the two points is not horizontal or vertical), then there may be two One situation is that the data points need to be corrected because the position of the associated element changes as mentioned earlier. The other situation is that there are standard orthogonal connecting points between the two data points. This situation occurs in (below) (Picture diagram):

1. Starting point -> Customized turning point

2. Customized turning point -> end point

3. Customized turning point -> Customized turning point

mirrorDataPoints:

mirrorDataPoints is a point on the line connecting dataPoints to the actual rendered points:
1. he length of mirrorDataPoints is the same as the length of dataPoints
2. Each of their points also corresponds to one-to-one, but the value of each position may be different
3. After the node is dragged, the points on dataPoints will be inconsistent with the points on the actual rendered connection. However, the one-to-one correspondence between the points on mirrorDataPoints and the points on dataPoints can effectively locate the data points based on the actual rendering points.

getMirrorDataPoints

Get the function of mirrorDataPoints introduced above. The calculation idea is as follows (it is the process of calculating the corrected actual point based on the custom turning point and the position of the associated element):

1. Correction based on parallel lines

2. Correction based on front and back points

There are two keyPoints between the custom turning point and the end point

There are two keyPoints points between the custom turning point and the custom turning point

The following introduces the two corrections of getMirrorDataPoints (the core is parallel line correction):

1. The dotted line source is the state before movement, and the solid line source is the state after movement.
2. The red points a and b are custom turning points added after dragging.
3. The red dotted line is the standard orthogonal connection path (when there is no custom turning point)
4. At this time, the connection point p1 and the first custom turning point a cannot directly form a horizontal or vertical connection. In this case, parallel line correction is required.

The reference standard for parallel line correction is actually the standard orthogonal connection, which is the red dotted line in the above picture. The so-called parallel line correction is to find parallel lines. As can be seen in the above picture, the red points a and b and the standard orthogonal lines The key1 point and the key2 point are parallel, so they can form a rectangle, as shown in the blue box in the following figure:

There may be some constraints at this time, that is, the constructed rectangle cannot cross the source and target nodes. The above picture meets the conditions, so based on some conditions, the a’ mapping point in the following picture can be obtained:

Correction of front and back points:

When parallel line correction does not work (parallel lines cannot be found, or some constraints cannot be met), a back-up logic is needed, which is correction based on front and rear points.

The rationality of the orthogonal connection is no longer considered when correcting the front and rear points. It only needs to ensure that the connection is a horizontal or vertical orthogonal line. In this case, the connection may cross the graphics.

1. The two customized turning points are red point a and point b.
2. The red dotted line is a standard orthogonal line connection
3. Parallel correction does not work
4. Correct to a’ and b’ based on the front and rear points p1 and p2

Based on this solution, the problems encountered in solution 3.0 can also be solved:

1. Find the data mirrorDataPoints through the getMirrorDataPoints method ([a, b] -> [a, b])
2. When dragging line segment A, you need to determine the position of the newly inserted [c, d]. Then you need to find the position of b. You can get the corresponding relationship between b and b through mirrorDataPoints, and get the index of b` (defined as previousIndex )
3. previousIndex + 1 is the position we need to insert correctly, here it is 3

In addition to the above functions, we also support functions such as merging custom turning points and line adsorption.

Summarize

This article mainly introduces the technical ideas for supporting custom inflection points for orthogonal lines in flow charts. I hope it can provide some reference for students who are interested or have similar needs.

In fact, when I first started working on this function, I didn’t expect it to be so complicated. The main reason was that there were too many scenarios to deal with. Every time I felt that it was handled well, I found many new problems until the concept of mirrorDataPoints was finally extracted. After establishing the corresponding relationship between the offset custom inflection point and the actual rendered inflection point, the problem was gradually converged. Although the process was quite difficult and I made many mistakes in the process, this should be normal. This requirement is indeed difficult.

Plait framework introduction:

An open source, modern drawing framework for building integrated whiteboard tool products, such as mind maps, flow charts, free-hand, etc.

Plait uses plugin mechanism to support the development of specific business functions. It currently supports basic mind map plugin（plait/mind）and flow chart plugins（plait/draw）.

Basic function see: Showdown, we are making a drawing framework! ! ! _bilibili_bilibili

Github repo: https://github.com/worktile/plait

Star support is welcome. If you have any technical or interactive questions, please free to submit an issue.