Removing Overlaps in Label Layouts Using Multi-sphere Scheme ?
Takashi Imamichi, Yohei Arahori, Jaeseong Gim, Seok-Hee Hong, Hiroshi Nagamochi · 2008
Abstract. In this paper, we consider the problem of removing overlaps of labels in a given layout by changing locations of some of the overlapping labels, and present a new method for the problem based on a packing approach, called multi-sphere scheme. Based on this scheme, each label in a given layout is approximated by a set of circles, and a cost function that penalizes the overlap between two objects is introduced. By minimizing the penalty function using a quasi-Newton method, we compute a layout of the set of circles as an approximate solution to the original problem. We consider two new variations of the label overlap problem, inspired by real world applications, and provide a solution to each problem. Our new approach is very flexible to support various operations such as translation, translation with direction constraints, and rotation. Further, our method can support labels with arbitrary shapes in both 2D and 3D layout settings. Our extensive experimental results show that our new approach is very effective for removing label overlaps.