0

I have the following algorithm for my d3.js charts which detects colliding value labels in my charts. This operation has to be done once all labels are rendered, and hence the reason why I use d3.selectAll().

Right now, what it does is, I select all the value labels on the div. For each value label, I get their coordinates to generate two points of x and y coordinates of the corners of the rectangle. More info can be found in this SO answer.

I then check for collisions by checking all points previously added to the valueLabelPositions array. So this operation is like O(n^2), which is super slow. I also checked the JS call stack timeline, and it takes over 2000 milliseconds for graphs with 4 axis. Here's an example of the graph with collision detection on labels:

enter image description here

This is the code I wrote.

  removeOverlappingLabelText: ->
    valueLabelPositions = []
    d3.selectAll('.value-labels text')[0].forEach (t) ->
      currentBox = t.getBoundingClientRect()

      # Check this for deeper summary: https://stackoverflow.com/a/32088787/1913389
      #         _________________  x2, y2
      #        |                 |
      #        |                 |
      #        |                 |
      #        |                 |
      # x1, y1 |_________________|

      # Position of bottom-left coordinate of current rect
      x1 = currentBox.left
      y1 = currentBox.top

      # Position of top-right coordinate of current rect
      x2 = currentBox.right
      y2 = currentBox.bottom

      for i in valueLabelPositions
        # Second rect
        x3 = i.left
        y3 = i.top
        x4 = i.right
        y4 = i.bottom
        if(x3 > x2 || y3 > y2 || x1 > x4 || y1 > y4)
          # No overlaps
        else
          # Overlap found, so remove
          t.remove()

      valueLabelPositions.push(currentBox)

I am curious how I can optimize this so it's faster than n^2?

Community
  • 1
  • 1
theGreenCabbage
  • 5,197
  • 19
  • 79
  • 169
  • 1
    You would need some spatial data structure like kd-trees to improve time complexity. But checking the 28 labels in the example should not take 2 seconds. If it does, there is something else going on. You might also want to consider grouping the labels by x-coordinate if the labels will always be stacked as in the example. – Nico Schertler Sep 28 '16 at 23:43
  • @NicoSchertler I am trying to find a generalized solution. I was considering stacking the x-coordinates as well, but there are definitely cases within line graph where it's not just x-coordinates that collide (i.e. when the vertical screen size is very restricted), but also y-coordinates. Also, column/bar charts is also another graph type where simply comparing x-coordinates isn't enough. – theGreenCabbage Sep 29 '16 at 16:56

0 Answers0