class TaskJuggler::GanttRouter

The GanttRouter is used by the GanttChart to route the dependency lines from the start to the end point. The chart is a rectangular area with a certain width and height. The graphical elements of the Gantt chart can be registered as don’t-cross-zones. These zones block the either horizontal or vertical lines (or both) from crossing the zone. Zones can be registered by calling addZone(). The route() method returns routed path from start to end point.

Constants

MinEndGap: Minimum distance between the last turning point and the tip of the arrow.
MinStartGap: Minimum distance between the starting point and the first turning point.

Public Class Methods

new(width, height) click to toggle source

Create a GanttRouter object. width and height describe the size of the rectangular area this router is operating on.

# File lib/taskjuggler/reports/GanttRouter.rb, line 35
def initialize(width, height)
  @width = width.to_i
  @height = height.to_i

  @detector = CollisionDetector.new(@width, @height)
end

Public Instance Methods

addZone(x, y, w, h, horiz, vert) click to toggle source

# File lib/taskjuggler/reports/GanttRouter.rb, line 42
def addZone(x, y, w, h, horiz, vert)
  @detector.addBlockedZone(x, y, w, h, horiz, vert)
end

route(startX, startY, endX, endY) click to toggle source

Find a non-blocked route from the startPoint [ x, y ] to the endPoint [ x, y ]. The route always starts from the start point towards the right side of the chart and reaches the end point from the left side of the chart. All lines are always strictly horizontal or vertical. There are no diagonal lines. The result is an Array of [ x, y ] points that include the startPoint as first and endPoint as last element.

# File lib/taskjuggler/reports/GanttRouter.rb, line 95
def route(startX, startY, endX, endY)
  points = [ [ startX, startY ] ]
  startGap = MinStartGap
  endGap = MinEndGap

  if endX - startX > startGap + endGap + 2
    # If the horizontal distance between start and end point is large enough
    # we can try a direct route.
    #
    #                       xSeg
    #              |startGap|
    # startX/endX  X--------1
    #                       |
    #                       |
    #                       2------X endX/endY
    #                       |endGap|
    #
    xSeg = placeLine([ startY + (startY < endY ?  1 : -1), endY ],
                     false, startX + startGap, 1)
    if xSeg && xSeg < endX - endGap
      # The simple version works. Add the lines.
      addLineTo(points, xSeg, startY)  # Point 1
      addLineTo(points, xSeg, endY)    # Point 2
      addLineTo(points, endX, endY)
      return points
    end
  end

  # If the simple approach above fails, the try a more complex routing
  # strategy.
  #
  #                         x1
  #                |startGap|
  # startX/startY  X--------1 yLS
  #                         |
  #         3---------------2 ySeg
  #         |
  #         4------X endX/endY
  #         |endGap|
  #         x2

  # Place horizontal segue. We don't know the width yet, so we have to
  # assume full width. That's acceptable for horizontal lines.
  deltaY = startY < endY ? 1 : -1
  ySeg = placeLine([ 0, @width - 1 ], true, startY + 2 * deltaY, deltaY)
  raise "Routing failed" unless ySeg

  # Place 1st vertical
  x1 = placeLine([ startY + deltaY, ySeg ], false, startX + startGap, 1)
  raise "Routing failed" unless x1

  # Place 2nd vertical
  x2 = placeLine([ ySeg + deltaY, endY ], false, endX - endGap, -1)
  raise "Routing failed" unless x2

  # Now add the points 1 - 4 to the list and mark the zones around them. For
  # vertical lines, we only mark vertical zones and vice versa.
  addLineTo(points, x1, startY)  # Point 1
  if x1 != x2
    addLineTo(points, x1, ySeg)          # Point 2
    addLineTo(points, x2, ySeg)          # Point 3
  end
  addLineTo(points, x2, endY)     # Point 4
  addLineTo(points, endX, endY)

  points
end

routeLines(fromToPoints) click to toggle source

# File lib/taskjuggler/reports/GanttRouter.rb, line 46
def routeLines(fromToPoints)
  # We first convert the fromToPoints list into a more readable list of
  # Hash objects.
  routes = []
  fromToPoints.each do |touple|
    routes << {
      :startX => touple[0],
      :startY => touple[1],
      :endX => touple[2],
      :endY => touple[3],
      :id => touple[4]
    }
  end

  # To make sure that we minimize the crossings of arrows that
  # originate from the same position, we sort the arrows by the
  # smallest angle between the vertical line through the task end
  # and the line between the start and end of the arrow.
  routes.each do |r|
    adjLeg = (r[:endX] - MinEndGap) - (r[:startX] + MinStartGap)
    oppLeg = (r[:startY] - r[:endY]).abs
    r[:distance] = Math.sqrt(adjLeg ** 2 + oppLeg ** 2)
    # We can now calculate the sinus values of the angle between the
    # vertical and a line through the coordinates.
    sinus = oppLeg.abs / r[:distance]
    r[:angle] = (adjLeg < 0 ? Math::PI / 2 + Math.asin(Math::PI/2 - sinus) :
                              Math.asin(sinus)) / (Math::PI / (2 * 90))
  end
  # We sort the arrows from small to a large angle. In case the angle is
  # identical, we use the length of the line as second criteria.
  routes.sort! { |r1, r2| (r1[:angle] / 5).to_i == (r2[:angle] / 5).to_i ?
                          -(r1[:distance] <=> r2[:distance]) :
                          -(r1[:angle] <=> r2[:angle]) }

  # Now that the routes are in proper order, we can actually lay the
  # routes.
  routePoints = []
  routes.each do |r|
    routePoints << route(r[:startX], r[:startY], r[:endX], r[:endY])
  end
  routePoints
end

to_html() click to toggle source

This function is only intended for debugging purposes. It marks either the vertical or horizontal zones in the chart.

# File lib/taskjuggler/reports/GanttRouter.rb, line 165
def to_html
  @detector.to_html
end