UW Interactive Data Lab
IDL logo

Fast and Flexible Overlap Detection for Chart Labeling with Occupancy Bitmap

Figure for Fast and Flexible Overlap Detection for Chart Labeling with Occupancy Bitmap
We rasterize a connected scatter plot onto a bitmap to mark occupied pixels, shown in orange (left). We use the 8-position model to generate candidate positions for label placements. The cyan positions are available, while the red ones are not (middle). After placing the label "1975", the pixels under the label need to be marked as occupied (right).
Materials
Abstract
Legible labels should not overlap with other marks in a chart. The state-of-the-art labeling algorithm detects overlaps using a set of points to approximate each mark's shape. This approach is inefficient for large marks or many marks as it requires too many points to detect overlaps. In response, we present a Bitmap-Based label placement algorithm, which leverages occupancy bitmaps to accelerate overlap detection. To create an occupancy bitmap, we rasterize marks onto a bitmap based on the area they occupy in the chart. With the bitmap, we can efficiently place labels without overlapping existing marks, regardless of the number and geometric complexity of the marks. This bitmap-based algorithm offers significant performance improvements over the state-of-the-art approach while placing a similar number of labels.
BibTeX
@inproceedings{2020-fast-labels,
  title = {Fast and Flexible Overlap Detection for Chart Labeling with Occupancy Bitmap},
  author = {Kittivorawang, Chanwut AND Moritz, Dominik AND Wongsuphasawat, Kanit AND Heer, Jeffrey},
  booktitle = {IEEE VIS Short Papers},
  year = {2020},
  url = {https://idl.uw.edu/papers/fast-labels},
  doi = {10.1109/VIS47514.2020.00027}
}