TaskJuggler::CollisionDetector

    # File lib/taskjuggler/reports/CollisionDetector.rb, line 22
22:     def initialize(width, height)
23:       @width = width
24:       @height = height
25: 
26:       # The zones are stored as Arrays of line segments. Horizontal blocks are
27:       # stored separately from vertical blocks. Blocked segments for a
28:       # particular x coordinate are stored in @vLines, for y coordinates in
29:       # @hLines. Each entry is an Array of [ start, end ] values that describe
30:       # the blocked segments of that particular line. Start and end point are
31:       # part of the segment. A listed segment will not be overwritten during
32:       # routing.
33:       @hLines = Array.new(@height) { |i| i = [] }
34:       @vLines = Array.new(@width) { |i| i = [] }
35:     end

    # File lib/taskjuggler/reports/CollisionDetector.rb, line 41
41:     def addBlockedZone(x, y, w, h, horiz, vert)
42:       # Clip the input rectangle to fit within the handled area of this router.
43:       x = clip(x.to_i, @width - 1)
44:       y = clip(y.to_i, @height - 1)
45:       w = clip(w.to_i, @width - x)
46:       h = clip(h.to_i, @height - y)
47: 
48:       # We can ignore empty zones.
49:       return if w == 0 || h == 0
50: 
51:       # Break the rectangle into line segments and add them to the appropriate
52:       # line Arrays.
53:       if horiz
54:         y.upto(y + h - 1) do |i|
55:           addSegment(@hLines[i], [ x, x + w - 1 ])
56:         end
57:       end
58:       if vert
59:         x.upto(x + w - 1) do |i|
60:           addSegment(@vLines[i], [ y, y + h - 1 ])
61:         end
62:       end
63:     end

    # File lib/taskjuggler/reports/CollisionDetector.rb, line 68
68:     def collision?(pos, segment, horizontal)
69:       line = (horizontal ? @hLines : @vLines)[pos]
70: 
71:       # For complex charts, the segment lists can be rather long. We use a
72:       # binary search to be fairly efficient.
73:       l = 0
74:       u = line.length - 1
75:       while l <= u
76:         # Look at the element in the middle between l and u.
77:         p = l + ((u - l) / 2).to_i
78:         return true if overlaps?(line[p], segment)
79: 
80:         if segment[0] > line[p][1]
81:           # The potential target is above p. Adjust lower bound.
82:           l = p + 1
83:         else
84:           # The potential target is below p. Adjust upper bound.
85:           u = p - 1
86:         end
87:       end
88:       false
89:     end

     # File lib/taskjuggler/reports/CollisionDetector.rb, line 91
 91:     def to_html
 92:       html = []
 93:       # Change this to determine what zones you want to see.
 94:       if true
 95:         # Show vertical blocks
 96:         x = 0
 97:         @vLines.each do |line|
 98:           line.each do |segment|
 99:             html << lineToHTML(x, segment[0], x, segment[1], 'white')
100:           end
101:           x += 1
102:         end
103:       else
104:         # Show horizontal blocks
105:         y = 0
106:         @hLines.each do |line|
107:           line.each do |segment|
108:             html << lineToHTML(segment[0], y, segment[1], y, 'white')
109:           end
110:           y += 1
111:         end
112:       end
113:       html
114:     end

     # File lib/taskjuggler/reports/CollisionDetector.rb, line 128
128:     def addSegment(line, newSegment)
129:       # Search for overlaping or directly attaching segments in the list.
130:       i = 0
131:       while (i < line.length)
132:         segment = line[i]
133:         if mergeable?(newSegment, segment)
134:           # Merge exiting segment into new one
135:           merge(newSegment, segment)
136:           # Remove the old one from the list and restart with the newly created
137:           # one at the same position.
138:           line.delete_at(i)
139:           next
140:         elsif segment[0] > newSegment[1]
141:           # Segments are stored in ascending order. If the next segment starts
142:           # with a larger value, we insert the new segment before the larger
143:           # one.
144:           line.insert(i, newSegment)
145:           return
146:         end
147:         i += 1
148:       end
149:       # Append new segment
150:       line << newSegment
151:     end

     # File lib/taskjuggler/reports/CollisionDetector.rb, line 119
119:     def clip(v, max)
120:       v = 0 if v < 0
121:       v = max if v > max
122:       v
123:     end

     # File lib/taskjuggler/reports/CollisionDetector.rb, line 170
170:     def merge(dst, seg)
171:       dst[0] = seg[0] if seg[0] < dst[0]
172:       dst[1] = seg[1] if seg[1] > dst[1]
173:     end

     # File lib/taskjuggler/reports/CollisionDetector.rb, line 163
163:     def mergeable?(s1, s2)
164:       overlaps?(s1, s2) ||
165:       (s1[1] + 1 == s2[0]) ||
166:       (s2[1] + 1 == s1[0])
167:     end

     # File lib/taskjuggler/reports/CollisionDetector.rb, line 156
156:     def overlaps?(s1, s2)
157:       (s1[0] <= s2[0] && s2[0] <= s1[1]) ||
158:       (s2[0] <= s1[0] && s1[0] <= s2[1])
159:     end