Sunday, April 12, 2015

AxesDrawer.swift

I read once (Dave Winer?) that if you’re programming you should blog about what your doing so that when, in the future. you can’t understand what you did, there’s somewhere to turn to. My motivation is slightly different, I’d like other people to be able to find what I’ve done, and its seems to me that blogging about it will serve that need. As background, I’m following the Stanford University CS193p course (““Developing iOS 8 Apps in Swift “) on iTunesU, and I’ve found that one of sample pieces of code that Stanford hand out is bugged. I’ve failed to find a way of reporting the bug and now that I’ve fixed it, I thought it would be friendly to blog about it.

As part of Assignment III: “Graphing Calculator” you are given the code for an AxesDrawer class to use as part of the project. The AxesDrawer class provides a function 

   drawAxesInRect(bounds: CGRect, origin: CGPoint, pointsPerUnit: CGFloat)

which draw, and label, those portions of the x and y axes with origin “origin” which sit within the bounds “bounds” of the current view. 

The first thing to state clearly is that the code as supplied by Standford works functionally; if you use the code it draws axes correctly. I did not find the problem from using the code, only from reading the code to try and understand how the code worked. 

The tricky part of the code is labelling the axes. The code has to decide the x (or y) increment between labels, and it then has to draw all the labels which are visible. The decision about the increment between labels is made on the basis of the size of the labels and the current scaling of the axes. The code computes the increment in terms of the number of points (drawing elements) per label. The variable pointsPerHashMark is used to hold this value. 

The mechanism behind the labelling of the code is straightforward. I’ll first explain it with the assumption that the origin sits within the bounds of the current view, then I’ll explain how it works when the origin is not within the bounds. The idea is that the code works from the origin outwards. The first set of potential labels are at (pointsPerHaskMark, 0) and (-pointsPerHaskMark, 0) on the x-axis, and (0 ,pointsPerHaskMark) and (0, -pointsPerHaskMark) on the y-axis. The second set of potential labels are (2*pointsPerHaskMark, 0) and (-2*pointsPerHaskMark, 0) on the x-axis, and (0 ,2*pointsPerHaskMark) and
(0,-2*pointsPerHaskMark) on the y-axis. And so on. Of course, at given distance from the origin, not all of the labels may fall within the bounds, and so the code checks whether each potential label falls within the bounds before plotting it.

   if let leftHashmarkPoint = alignedPoint(x: bbox.minX, y: origin.y, insideBounds:bounds)
   {
      drawHashmarkAtLocation(leftHashmarkPoint, .Top("-\(label)"))
   }

Eventually, at some distance from the origin, all of the potential labels fall outside the bounds, and the labelling can stop. The way the code controls the loop which performs the labelling is interesting. Initially the code sets up a rectangle (CGRect) whose centre is at the origin and whose x and y dimensions are pointsPerHashMark * 2; that is the bounds of the rectangle (in fact a square) are +/-pointsPerHashMark.  

   var startingHashmarkRadius: CGFloat = 1

   …

   // now create a bounding box inside whose edges those four hashmarks lie
   let bboxSize = pointsPerHashmark * startingHashmarkRadius * 2            
   var bbox = CGRect(center: origin, size: CGSize(width: bboxSize, height: bboxSize))

On each iteration the size of the rectangle is increased to (by 2*pointsPerHaskMark in each dimension)) so as to include the next set of potential labels. 

   bbox.inset(dx: -pointsPerHashmark, dy: -pointsPerHashmark)

The code detects termination of the labelling process by testing whether the view (area to be plotted) sits entirely within this rectangle. Once it does, any further potential labels must sit outside the view and so do not need plotting.

   while !CGRectContainsRect(bbox, bounds)

Now lets looks at what happens when the origin is outside of the view. The mechanism used in the code will work, albeit inefficiently. Because labels are only plotted if they are in the view, no spurious labels are plotted. But more interestingly, if we start labelling from the origin outwards, and use the code’s termination test, all the necessary labels will appear and the code will terminate. As the size of the rectangle (bbox) increases on each iteration, it will eventually contain the view, at which point all labels will have been plotted and the loop will terminate.   

So to efficiency. The first potential inefficency is do any work when there are no axes to plot. This is dealt by a simple test of the start of drawAxesInRect

   if ((origin.x >= bounds.minX) && (origin.x <= bounds.maxX)) ||
      ((origin.y >= bounds.minY) && (origin.y <= bounds.maxY))
  
The second inefficiency occurs when there is an axis to plot but the origin is outside the view. Suppose the origin is at (-100, 0), the view has a minimum x value of 0 and we have decided that labels will be plotted every 10 points. In this case the view will contain a portion of the a-axis starting at 100 with labels at 100, 110, etc. If the code does nothing to deal with this case, it work out from the origin and try (and fail) to plot labels at distances of 10, 20 and up to 90 points from the origin until it starts to plot at 100 points distant from the origin. An optimisation that can be done is to detect the case that the origin is outside the view

   if !CGRectContainsPoint(bounds, origin) {

and then determine how far the first plottable label is from the origin. This is what the code attempts to do and where the bugs occur.

   let leftx = max(origin.x - bounds.maxX, 0)
   let rightx = max(bounds.minX - origin.x, 0)
   let downy = max(origin.y - bounds.minY, 0)
   let upy = max(bounds.maxY - origin.y, 0)
   startingHashmarkRadius = min(min(leftx, rightx), min(downy, upy)) / pointsPerHashmark + 1

The first bug is that one of left, right, downy or upy must be zero, hence min(min(leftx, rightx), min(downy, upy)) is also zero and startingHashmarkRadius is 1. To see that one value must be zero, without loss of generality, consider the case where the x axis will be plotted. Again, wlog, consider the case where the origin is to the left of the view. In this case origin.x - bounds.maxX will be negative and hence leftx will be zero. I won’t speculate about why the code got written like this, but unless testing beyond simple functional checks were done, this bug wouldn’t be caught.

There is a second bug also present which I ran into when I fixed the first one. I’ll leave it as an exercise until later.

Reusing the case above, for the x-axis, origin.x - bounds.maxX will be negative, but bounds.minX - origin.x, the distance of the origin to the view, will be positive. Looking at the y dimension, bounds.minY - origin.y will be negative, as will be origin.y - bounds.minY since the y-coordinate of the origin sits between the min and max y-coordinates of the view. The distance of the origin from the view is, therefore, the one positive value amongst the four. Can can therefore, take the maximum of the four values. Accordingly my first attempt at a fix was 

   let rightx =   origin.x - bounds.maxX
   let leftx  = -(origin.x - bounds.minX)
   let downy  =   origin.y - bounds.maxY
   let upy    = -(origin.y - bounds.minY)
   startingHashmarkRadius = (max(max(leftx, rightx), max(downy, upy) / pointsPerHashmark) + 1

When I used this version the effect was weird. I’d pan a view, pulling the graph and axes across the screen until one axis went out of bounds. At this point the other axis stopped panning (although the plotted graph continued panning) but the labels incremented each time I had panned by more than the distance between two labels. This was the second bug. The problem is that the code computes the distance of the origin to the view, whereas what is needed is the distance of the origin from the first label. The fix is to the floor of the division to get an integral number of labels and then to add 1. So, the code which fixes the second bug looks like

   let rightx =   origin.x - bounds.maxX
   let leftx  = -(origin.x - bounds.minX)
   let downy  =   origin.y - bounds.maxY
   let upy    = -(origin.y - bounds.minY)
   startingHashmarkRadius = floor(max(max(leftx, rightx), max(downy, upy) / pointsPerHashmark) + 1

2 comments:

Fred said...

Hi Shepherd,
Happy to read an explanation about this CS193 swift code product from Stanford.
And fews bugs that have been spotted by you.

I have a concern about one part :

"The second inefficiency occurs when there is an axis to plot but the origin is outside the view. Suppose the origin is at (-100, 0), the view has a minimum x value of 0 and we have decided that labels will be plotted every 10 points. In this case the view will contain a portion of the a-axis starting at 100 with labels at 100, 110, etc. If the code does nothing to deal with this case, it work out from the origin and try (and fail) to plot labels at distances of 10, 20 and up to 90 points from the origin until it starts to plot at 100 points distant from the origin. An optimisation that can be done is to detect the case that the origin is outside the view

if !CGRectContainsPoint(bounds, origin) {"

You are talking about the inefficiency if we are trying to plot an axis if the origin is outside the view bounds'. But i tried to understand why they wrote that in their code. If the View code is well set, we don't need it, in my view.

For example if we are setting the origin at the View bounds.midX and bounds.midY at each time we are plotting a function. Whether we need to pan, of course, we must keep the origin of the axes. But, if we are panning out of the primordial view bounds' the starting hashmark radius seems to always compute this value of 1, the same that is set before. So what the aim ?! May be i'am wrong. I'am not a developper that the reason i'am following this kind of courses.

Thank you if you are taking time to answer me and explain me the Why and the How, also i hope you will understand what i mean, cause i'am not an english native speaker.

Have a good day,

Fred.

The Editor said...

It's now so long since I worked through this code I don't immediately understand it and I don't have time to work out what was going on. Sorry.

Search This Blog