Overlap Removal by Stochastic Gradient Descent with(out) Shape Awareness

IEEE Trans Vis Comput Graph. 2024 Jan 9:PP. doi: 10.1109/TVCG.2024.3351479. Online ahead of print.

Abstract

In many 2D visualizations, data points are projected without considering their surface area, although they are often represented as shapes in visualization tools. These shapes support the display of information such as labels or encode data with size or color. However, inappropriate shape and size selections can lead to overlaps that obscure information and hinder the visualization's exploration. Overlap Removal (OR) algorithms have been developed as a layout post-processing solution to ensure that the visible graphical elements accurately represent the underlying data. As the original data layout contains vital information about its topology, it is essential for OR algorithms to preserve it as much as possible. This article presents an extension of the previously published FORBID algorithm by introducing a new approach that models OR as a joint stress and scaling optimization problem, utilizing efficient stochastic gradient descent. The goal is to produce an overlap-free layout that proposes a compromise between compactness (to ensure the encoded data is still readable) and preservation of the original layout (to preserve the structures that convey information about the data). Additionally, this article proposes SORDID, a shape-aware adaptation of FORBID that can handle the OR task on data points having any polygonal shape. Our approaches are compared against state-of-the-art algorithms, and several quality metrics demonstrate their effectiveness in removing overlaps while retaining the compactness and structures of the input layouts.