Automatic line routing algorithm for visual models

OData support
Dr. Mezei Gergely
Department of Automation and Applied Informatics

Nowadays, graphical modelling languages are very popular. The graphical representation of a model facilitates the work of the user, but in case of big models the aesthetic arrangement of the elements takes a lot of time. If the modelling environment does not determine routing of the line automatically, it is a time consuming task to arrange the breakpoints. I implemented an automatic line routing algorithm for an existing graphical modelling environment. The aim of the algorithm is to find an optimal line between two elements using horizontal and vertical segments only. Moreover, the line cannot cross an other element. I provided a solution to this basic problem and I improved the algorithm with useful additions.

In the thesis, firstly I look into the base of existing line routing algorithms then I examine the features of the selected modelling environment. I planned the algorithm based on these steps.

Secondly, I introduce the basic algorithm which draws an optimal line between two elements. The line cannot cross an other element and has to consist of right angles and straight segments. At this stage a line is said optimal if it is as short as possible.

Thirdly, I improve the algorithm to handle the breakpoints of the line. We can set the priority between the length and the number of breakpoints with a ratio between them. Afterwards, I optimize the algorithm models containing ports in order to optimize the performance. Furthermore, I modify the algorithm to avoid crossing lines. The environment is now able to arrange every line automatically with this option.

At the end, I illustrate the mechanisms of the algorithm through a realistic example and I mention a few future directions.


Please sign in to download the files of this thesis.