Class: TaskJuggler::GanttRouter

Inherits:
Object
  • Object
show all
Defined in:
lib/taskjuggler/reports/GanttRouter.rb

Overview

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.

Constant Summary collapse

MinStartGap =

Minimum distance between the starting point and the first turning point.

5
MinEndGap =

Minimum distance between the last turning point and the tip of the arrow.

10

Instance Method Summary collapse

Constructor Details

#initialize(width, height) ⇒ GanttRouter

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



35
36
37
38
39
40
 
# 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

Instance Method Details

#addZone(x, y, w, h, horiz, vert) ⇒ Object 



42
43
44
 
# 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) ⇒ Object

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.



95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
# 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) ⇒ Object 



46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
# 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 ⇒ Object

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



165
166
167
 
# File 'lib/taskjuggler/reports/GanttRouter.rb', line 165

def to_html
  @detector.to_html
end