Research On Edge Sampling And Edge Bundling Algorithm Based On Optimal Transportation Theory

Data visualization is mainly to interpret the data by using graphic means so that users can conduct in-depth observation and analysis of the data.Many visualization methods exist today.Among many objects of visualization,the node-link diagram is a basic and important structure,which is composed of vertexes and edges.It is suitable for representing the relationship between entities.Entities are represented by vertexes,and the relationships between entities are represented by edges.With the increasing of data scale,the visual clutter in the visualization scheme of the node-link diagram makes the recognition degree of information drop sharply,and the edge bundling method is an important way to solve the visual clutter.This thesis summarizes and analyzes the existing edge bundling algorithms.To improve the effectiveness of the edge bundling algorithm,control the bundling tightness flexibly,and display the main structure of the whole data set,this thesis proposes an edge bundling algorithm based on edge clustering and edge sampling.The details are as follows:1.An edge clustering method based on direction and distance is proposed.This method uses hierarchical clustering and different distance functions to cluster the edges twice based on direction and distance.The Pearson distance is used to cluster the edges with similar directions.Based on the direction clustering,the Euclidean distance is used to cluster edges with similar space.In particular,a cluster of short edges will be generated during the first clustering,and it will not perform the second clustering in this method.2.An edge bundling method based on optimal transportation is proposed.Firstly,different distance functions are used to cluster edges.Secondly,the optimal transportation theory is used to find the Wasserstein Barycenter of the probability distribution on each edge set,and the Wasserstein Barycenter is the sampling edge.Then,to achieve the purpose of visual clustering,the initial edges of each edge set are bundled to the sampling edge by two Bezier curves.After that,different positions of the final drawn curves are set with different transparency to emphasize the bundling.The Bezier curves are set to the middle transparency,the line at the endpoints of the curves are set to the highest transparency,and the short edges are set to the lowest transparency.Finally,the Open GL rendering technique is used to further emphasize the bundling by measuring the amount of overdraw.