Page 70 - 2024S

UEC Int’l Mini-Conference No.52 63

Design and Optimization of LineSets

Xianghan WEI ∗1 and Yoshio OKAMOTO 2

1 UEC Exchange Study Program (JUSST Program)
2 Department of Computer and Network Engineering
The University of Electro-Communications, Tokyo, Japan

Keywords: Information Visualization, Cubic Spline, Method of Optimization.

Abstract
LineSets is a method for visualizing point sets in the plane, widely used in Geographic Information
Systems (GIS), social networks, and bioinformatics. However, automatically generated LineSets often
lack ideal visual quality. This research aims to design and optimize the curves of LineSets for better
visualization performance. We initialize the spline with Catmull-Rom and convert it to B´ezier spline
for optimization, achieving good local control and overall shape. Using the LKH-3 LP solver, we
significantly reduce the curve length while avoiding self-intersections. To optimize curvature, we apply
Sequential Least Squares Programming on the position of control points for each segment, ensuring C1
continuity. We balance curve length and curvature by setting different optimization weights, finding
the optimal weight. For large distances between knots, we subdivide the curve by adding virtual knots
for finer control. To address the difficulty in discerning point affiliations at intersections, we apply
a force-directed method to control points near the intersection area, increasing the spacing between
different curves. The drawing framework is implemented using C++ and Qt, while the optimization is
carried out with Python and Scipy. Our experimental results demonstrate that the optimized LineSets
are more visually intuitive and effective.

∗
The author is supported by JASSO Scholarship.