Page 71 - 2024S

64 UEC Int’l Mini-Conference No.52

Design and Optimization of LineSets

Xianghan WEI Yoshio OKAMOTO
School of Computer Science and Engineering Department of Computer and Network Engineering
University of Electronic Science and Technology of China University of Electro­Communications
Chengdu, China Tokyo, Japan
Introduction Optimization of Curvature
1.Method
We use the Sequential Least Squares Programming on the
position of control points by each segment. The objective of
optimization is the maximum curvature of the segment. We
added collinear conditions to the control points on both
sides of the knots so that the curves remain C1 continuous.
2.Balance Between Length and Curvature
Reducing the maximum curvature usually means an increase
in the length of the curve, so a balance needs to be found.
We set different weights of curvature/length in optimization
Example of LineSets in Map and Social Network¹ objective, the results are as follow:
LineSets is a method for giving a visual summary of point
sets in the plane. It can be used on Geographic Information
System ﴾GIS﴿, social network, Bio‐infomatics, and so on.
A well‐designed Lineset can effectively represent the
information of point sets, but automatically generated
LineSets is often not visually ideal. The goal of this research
is to design and optimize the curves of LineSets for better
visualization performance.

Construction of Curves
Cubic spline is a classical method that generates a smooth When the weight is lower than 100, the curve is close to
curve which pass through a set of known data points. The linear segments. As the weight increases, the length of the
points that curves must pass through are called "knots", and curve increases, and even self‐intersecting occurs. In this
there are two invisible control points between each knots. case, 500 is an optimal weight.
There are multiple kinds of cubic spline. 3.Curve Subdivision
When the distance between two knots is too large, the curve
usually behaves stiffer. We subdivide the longer segments by
adding "virtual knots" to achieve fine control of curve shape.

Optimization of Congestion
It is often difficult to discern the affiliation of knots at the
Bézier spline is simple and has good local control, which intersections of multiple curves. Here we applied force‐
provides the possibility for further edit and optimization. directed method³ on control points near the congestion area
Catmull‐Rom spline has better shape and continuity, but is
fixed with given knots. Luckily, it can be converted into to increase the spacing between different curves.
Bézier form. So here, we initialize the spline with Catmull‐
Rom and convert it into Bézier spline for optimization.
Optimization of Length

Representing the same set with shorter curve will Implementation and Results
significantly reduce visual strain. Here, we use LKH‐3² LP‐
solver to find the shortest Hamilton path as drawing order. The drawing framework is implemented by C++ and Qt, and
It significantly reduces the curve length while avoiding self‐ the optimization part is implemented by Python and Scipy.
intersecting.

Reference:[1] Alper, Basak & Henry Riche, Nathalie & Ramos, Gonzalo & Czerwinski, Mary. (2011). Design Study of LineSets, a Novel Set Visualization Technique. IEEE transactions on visualization and computer graphics. 17. 2259­67. 10.1109/TVCG.2011.186. [2] Helsgaun, Keld.
(2017). An Extension of the Lin­Kernighan­Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems. 10.13140/RG.2.2.25569.40807. [3] Kobourov, Stephen G. (2012), Spring Embedders and Force­Directed Graph Drawing Algorithms, arXiv 1201.3011