Drawing technology flow chart orthogonal connection algorithm

Orthogonal lines are the most commonly used connection form in flowcharts. They can clearly express the logical relationship between graphic elements. They are simple and beautiful to use. The black connection in the figure below is an orthogonal connection:

Orthogonal connection diagram

The so-called orthogonal connection means that its line segments must be orthogonal to each other. From the above figure, we can basically see the characteristics of the orthogonal connection in the flow chart:

1. Lines cannot be traversed through graphic elements
2. The connection is usually the shortest
3. For the sake of beauty, the connection should generally be symmetrical based on the center line.
4. Scenes surrounding graphic elements need to reserve a certain amount of space (as shown in the figure below)

Orthogonal lines loop through graphics

Today I will mainly share how to implement such an orthogonal connection path. The core is divided into three parts:

1. Explanation of ideas
2. Shortest path algorithm
3. Algorithm execution process

Explanation of ideas

Idea 1: Based on exhaustion

At first, we didn’t know much about this technology when we implemented the connection, so we directly borrowed the connection implementation of react-flow. It is a simple implementation method: distinguish the position relationship of two nodes and the orientation of the connection point, based on different situations determine different wiring rules.

I define this implementation as exhaustive. The main problem with this idea is that it has to consider and distinguish a lot of situations, and even if it is classified, there may be very many situations.

Idea 2: Based on the shortest path algorithm

This is also a solution that has been discussed and implemented a lot in the community, because orthogonal connections have some similarities with the shortest path based on graphs. The orthogonal connection of a graph is essentially a shortest path, and it is also used in the shortest path algorithm. There are implementations similar to A* that are both efficient and flexibly scalable. Today we will mainly share the implementation of orthogonal connections based on the shortest path algorithm. Its advantage over the exhaustive approach is that it can easily distinguish complex situations. Different situations all point to the shortest path, so the shortest path algorithm is used to resolve the complexity.

Shortest path algorithm

Here is a brief introduction to the shortest path algorithm. I believe everyone should be familiar with it. It is an algorithm based on graph data structure. Common implementations include Dijkstra algorithm, A* algorithm, etc. Here is a brief introduction to these two algorithms, so that everyone can better understand the A algorithm we use and understand why it can better match the orthogonal connection requirements.

In order to better understand these two, let’s start with the Breadth-First Search algorithm.

Breadth First Search

Explore equally in all directions. This is a very useful algorithm not only for general pathfinding, but also for procedural map generation, flow field pathfinding, distance plots, and other types of map analysis.

Dijkstra’s Algorithm

(also called uniform cost search) allows us to prioritize which paths to explore. Rather than exploring all possible paths equally, it favors the less costly path. We can assign lower costs to encourage movement on certain paths, higher costs to avoid moving on certain paths, and so on. We use it instead of breadth-first search when moving costs are considered, and Dijkstra adds caching during the cost calculation, so it is more efficient than breadth-first search.

A*

A* is a modified version of Dijkstra’s algorithm, optimized for a single destination. Dijkstra’s algorithm can find paths to all places, A finds the path to a location or the closest location among multiple locations. It prioritizes those paths that appear to be closer to the goal, a process accomplished by adding a Heuristic function.

Heuristic function

With breadth-first search and Dijkstra’s algorithm, the boundary expands in all directions. This is a reasonable choice if you are trying to find a path to all locations or many locations. However, a common situation is to find a path that only reaches one location. Let’s expand the boundaries toward the goal, not the other way around. At this point, we need a heuristic function that tells us how close we are to the goal:

def heuristic(a, b):
   # Manhattan distance on a square grid
   return abs(a.x - b.x) + abs(a.y - b.y)

The logic of this heuristic function is also very simple, which is to calculate the sum of the horizontal and vertical distances between the expanded boundary point and the final target. The result is: the algorithm will tend to expand to the boundary where the target position is located first.

Algorithm description

First of all, both Dijkstra and A* are based on the Breadth First Search algorithm.

Dijkstra added a concept of cost in the process of calculating the shortest path, which is the cost of different paths. For example, the path length in the screen coordinate system can be used as cost. The shorter the path distance, the smaller the cost, the algorithm will be better when traversing nodes. Traverse the path with the smallest cost first.

The A* algorithm is a modified version of Dijkstra’s, optimized for a single destination. Dijkstra’s algorithm can find paths to all places, A finds the path to a location or the closest of multiple locations, it prioritizes those paths that appear to be closer to the goal.

The A* algorithm considers the closer to the target position and the cost in Dijkstra as the traversal priority by adding a Heuristic function (generally calculating the sum of the absolute values of the horizontal and vertical distances between the current point and the target point). It traverses first, and the A* algorithm ends immediately once it finds the target algorithm, so it can only get one shortest path.

Algorithm limitations

① Minimum turning points

In the orthogonal line scene of our flow chart, there are actually countless shortest paths that comply with the connection rules, but only one path is what we expect. Among them, more turning point paths are important interference items, because the increase in the turning points of the connection actually the length of the connection is not increased, so the path with more turning points according to the algorithm logic is also the correct path, but it is incorrect in our orthogonal connection scene:

Fewer turning points vs more turning points

We hope that the algorithm can find a path with the fewest turns in the red color, rather than a path with more turns like the blue color. This can be slightly improved on the A* algorithm. When the path has turns, increase its cost to make the path more inclined to walk in a straight line, in order to obtain the path with the fewest turns.

② Passing through the center line

In some cases, the path with the fewest turns is not our ideal path, as shown in the previous diagram. What we ultimately need is the black path shown in the lower diagram. We hope that the connecting path can preferably pass through the center line, making the connection look more symmetrical.

Based on least turning points vs passing through the center line

This requirement tormented us for a while. Initially, we wanted to make improvements to the A* algorithm, but we found that determining whether there are center lines (horizontal and vertical) between the shapes, and whether we should follow the center lines (for example, in the upper diagram, we should follow the vertical center line rather than the horizontal center line) is too complex. Following the center line requires a reduction in cost, while the previous logic of minimizing turns involves an increase in cost, which created a conflict and could easily prevent the A* algorithm from exiting properly. Finally, we came up with the solution of center line correction. This means that we do not handle the logic of following the center line in the A* algorithm, but instead perform center line correction based on the result of the A* algorithm. After verification, we found that this solution is feasible and both the complexity and effectiveness are quite ideal. The details of center line correction will be explained in detail in the section [Algorithm Execution process-> Center Line Correction]. Here, I just want to point out that its logic has gone beyond the scope of the A* algorithm, and what was previously mentioned as ‘minimizing turns’ is actually just a slight improvement in the path weighting logic within the scope of the A* algorithm.

For a detailed introduction to the shortest path algorithm, refer to: https://www.redblobgames.com/pathfinding/a-star/introduction.html. The article contains example code for various algorithms, animated explanations of algorithm execution processes, and is a very good learning resource.

Algorithm execution process

The algorithm mentioned here does not only refer to the ‘shortest path algorithm,’ but rather the entire process of connection route, including the construction of data structures and center line correction in addition to A*.

General process

1. Data preparation
2. Build grid points
3. Build graph structure
4. Run the A* algorithm
5. Center line correction

In order for everyone to better understand the general process of algorithm execution, I created an online demo that illustrates the overall algorithm execution process, disassembles the algorithm execution process, and adds auxiliary elements to the intermediate results so that everyone can see the results of each process execution more clearly.

1、Data preparation

As shown in the following figure, we need to first construct the rectangle and outerRectangle (purple) based on the source shape, and the rectangle and outerRectangle (red) based on the target shape:

The rectangle is essentially the boundary of the source or target shape, while the outerRectangle is defined based on the shape boundary to create a protected area. This means that the connection can pass along the boundary of the outerRectangle but cannot cross it. The exception to this rule is the connection points (points where the connection intersects with the rectangle) and the next points (points where the connection intersects with the outerRectangle).

2、Build grid points

As shown in the figure below, the orange points are the constructed connection points. The construction idea is simple: it involves finding the intersections of 7 horizontal lines and 7 vertical lines. There are 7 horizontal lines: 2 on the upper and lower boundaries of the source/target shape’s outerRectangle (a total of 4), 1 on the center line of the source/target shape (a total of 2), and 1 on the vertical center line of the source/target shape:

3、Build graph structure

Based on the connection points and their connectivity, a graph data structure is constructed in preparation for running the A* algorithm. Points in the horizontal and vertical directions generally need to be connected to each other, while points crossing the outerRectangle cannot be connected. The graphical representation of the graph structure is shown in the figure below, as indicated by the orange points and green lines:

4、Run the A* algorithm

When we mentioned the shortest path algorithm earlier, we mentioned that the A* algorithm used here is slightly modified. When calculating the cost of the connection, we need to consider not only the length of the path and the Manhattan distance but also avoid turning points. The core code is as follows:

let newCost = costSoFar.get(current!.node)! + this.heuristic(next.data, current!.node.data);
const previousNode = this.cameFrom.get(current!.node);
// Turning point weight, if a turning point appears, then cost + 1 to avoid turning point paths
// Determine if there is a turning point with three points in a line
const previousPoint = previousNode ? previousNode.data : previousStart;
const x = previousPoint[0] === current?.node.data[0] && previousPoint[0] === next.data[0];
const y = previousPoint[1] === current?.node.data[1] && previousPoint[1] === next.data[1];
if (!x && !y) {
  newCost = newCost + 1;
}

At this point, the shortest path generated by the A* algorithm is shown by the red line in the figure below (with a minimum number of turning points, only two):

5、Center line correction

This is a relatively difficult part of the overall implementation because the idea and implementation were gradually developed. The idea is based on a known path (the shortest path with the fewest turning points) and the center line matching logic is relatively simple. The idea is to find whether there are line segments parallel to the center line in this known path. If there are, it indicates the possibility of mapping to the center line and can be corrected. If not, then the path obtained by the A* algorithm is the final path.

The general steps are as follows:

// Center line correction: Correct the shortest path route based on the horizontal centerline/vertical centerline
// 1. Find the horizontal center line (centerX)/vertical center line (centerY)
// 2. Find the point that intersects centerX/centerY in route, and find the line segment parallel to centerX/centerY in route
// 3. Construct a rectangle based on the intersection points and parallel lines found in the previous step.
// 4. Determine whether the rectangle intersects with the element. If it does not intersect, the center line can be mapped based on the rectangle constructed in the previous step.
// 5. Determine whether the path after mapping the center line meets the constraints (inflection point cannot be increased)

The intersection points and parallel lines in the previous example are illustrated in the following figure:

A rectangle can be constructed from the upper and lower endpoints of the parallel lines and the intersection point, and then the path can be mapped to the center line (following the two blue edges). The specific implementation details are not discussed here. If you are interested, you can refer to this source code. The final corrected path is shown in the following figure (in green):

Finally get the blue path

Review and Reflection on Implementation

Looking back on the process of implementing orthogonal connections based on the shortest path, it feels worth summarizing briefly. We encountered some pitfalls, such as not initially understanding the real problem that the algorithm solves, over-reliance on open-source implementations without understanding the implementation details, which led to a lack of direction and a lack of a clear approach when facing problems. Later, we started from scratch to deduce the overall implementation approach, build our own data structures, implement the A* algorithm ourselves, and then consider solutions based on the problem, gradually getting back on track.

I think it is worth reflecting on the fact that from the beginning, we should have organized the implementation approach and understood the algorithm details. It is also important to try to build the implementation code step by step ourselves. Blindly importing open-source implementations can lead to corresponding issues in some complex problems. Finally, when encountering problems, it is important to continuously try possible solutions. The “center line correction” introduced earlier is a solution found through continuous exploration.

Summarize

This article mainly introduces our recent implementation ideas and core technology of flow chart orthogonal connection based on shortest path reconstruction.

In order to explain the execution process of the algorithm more clearly, I wrote an online demo. Each stage of the algorithm execution and the intermediate results of the stages are marked on the demo code:

Online address: https://plait-gamma.vercel.app/?init=route

Demo code: https://github.com/worktile/plait/blob/develop/src/app/plugins/with-line-route.ts

The core logic can refer to our implementation in the plait framework:

Framework repository: https://github.com/worktile/plait

Code location: https://github.com/worktile/plait/blob/develop/packages/common/src/utils/elbow-line-route.ts

During the implementation process, the community’s technical information and open source implementation provided many important ideas, and I would like to thank you for this.

Core reference:

routing-orthogonal-diagram-connectors-in-javascript

https://www.redblobgames.com/pathfinding/a-star/introduction.html

https://github.com/toeverything