Shot Density Passes Tests
Are Rectangles Open, or Closed
One thing Chet and I talked about Thursday, when we started using the Rectangle2D, was whether Java Rectangles are open or closed. In geometry, a rectangle is “open” if its low x edge and low y edge are included in the rectangle, but the high x edge and high y edge are not.
That is, if you have a rectangle that starts at 0,0 and is of size 1,1, is the point 1,1 in, or out? If it’s in, then there is a small chance of overlap, i.e. a Hit showing up in two different grid elements. If it’s out, then each Hit can occur in one and only one grid location.
I had surfed the Web a few times and never found the answer. So I wrote the following test. I’ll comment below on the whole thing, and on the highlighted bits.
public class Rectangle2DTest { Rectangle2D rect; Double epsilon; Double nearlyOne; @Before public void setUp() throws Exception { rect = new Rectangle2D.Double(0,0,1,1); epsilon = Math.ulp(1.0); nearlyOne = 1.0 - epsilon; } @Test public void contains() { assertTrue(rect.contains(0.5, 0.5)); assertFalse(rect.contains(2, 2)); assertTrue(rect.contains(0, 0)); assertTrue(rect.contains(0, nearlyOne)); assertTrue(rect.contains(nearlyOne, 0)); assertFalse(rect.contains(1, 1)); } @Test public void rectangleIsOpen() { assertFalse(rect.contains(0, 1)); assertFalse(rect.contains(1, 0)); assertFalse(rect.contains(1, 1)); } }
For our setup, we create a rectangle origined at 0,0, and of size 1,1. Skip the rest, and look first at the tests. The contains() test is the first one I wrote, and it just tests that 0,5,0.5 is in, that 2,2 is not, that 0,0 is. Then it tests that 0,nearlyOne and nearlyOne,0 are both in, and that 1,1 is right out.
Those are the results I wanted, because I wanted there to be no overlap between rectangles like (0,0,1,1) and (0,1,1,2), two adjacent rectangles in a row. And the test runs, which is good. Then I wrote the rectangleIsOpen() test, just to communicate a little better what I cared about, namely that Rectangle2D.Double elements are open.
Now for a brief digression about epsilon, ulp, and nearlyOne. After ascertaining that the value 1 was not present in the rectangle, either in x or y, I wanted to be sure that values very close to 1, but just barely smaller, were considered inside. So I needed a very small floating point value to substract from one.
(I could have just used 0.9999999, but I wanted to be more precise.) ULP stands for Unit in the Last Place, and refers to the distance between two floating point numbers that are minimally distinguishable. The ULP is a function of the number you have in mind, because there are different numbers of digits to play with depending on the numbers. So, 1 - ulp(1) is the largest floating point number you can represent that is still less than one. And that’s what I wanted.
So epsilon is the ulp size at 1, and nearlyOne is one minus that, or 1 - epsilon. Fun, huh? I didn’t know that … I searched around in Math, found ulp, which didn’t mean anything to me, and checked its definition. It turned out tob e just what I needed.
So the result of this little test is that I have solid information on whether rectangles are open, and I learned a little bit about Java Math. That was a fun exercise for 5 AM. Now let’s get back to density.
Returning to Density
Chet and I met at Amer’s Deli in Brighton, where they have free Internet and free refills on the sodas. Also good sandwiches for lunch. We ran into our acquaintance Dan, who we used to run into at Borders. We hadn’t seen him yet this year. Turns out he has transferred his office to Amer’s “full time”.
We left last time with our unit test running red. The test was this:
@Test public void grid00() { pattern = new ShotPattern(folder+"tm1subset.bmp", 4.0, 3.0); RectangularGrid grid2x2 = new RectangularGrid(pattern,1,1); assertEquals(1, grid2x2.hitsIn(0,0)); }
This test was red, because this code didn’t work yet:
public int countHits(Rectangle2D rectangle) {
int count = 0;
for (Hit hit: hits) {
if (rectangle.contains(hit.getX(), hit.getY()))
count++;
}
return count;
}
The issue is that our rectangle is recorded in inches, while hits are recorded in pixels, not inches, and are translated from having 0,0 at the top left, to an origin in the middle of the picture. We think now that both of these were not good decisions. Hits should probably be recorded in inches, and our customer has decided that an origin in the top left of the page is simpler, and probably just as easy to use.
So this is, as we mentioned last time, a “major refactoring”. We’re changing a fundamental assumption “of the whole system”. Now it’s true that we don’t have a billion lines of code here, but even so we want to make the necessary changes without breaking our existing tests.
Therefore we begin by positing two new methods on Hit, returning their coordinates in inches:
public int countHits(Rectangle2D rectangle) { int count = 0; for (Hit hit: hits) { if (rectangle.contains(hit.getXinInches(), hit.getYinInches())) count++; } return count; }
Following our noses, or the little X’s in Eclipse, we write one method:
public Rectangle2D getXinInches() { int xInPixels = getX() - xOffset; return xInPixels / xPixelsPerInch; }
This code first gets the X in 0,0-based pixels, by subtracting out the xOffset, and then scaling by dividing by the number of x pixels per inch. The Hit object doesn’t know either the xOffset or the xPixelsPerInch. To get the offsets, we add fields, and set them in our translate call:
public void translateBMP(int xOffset, int yOffset) {
this.xOffset = xOffset;
this.yOffset = yOffset;
for (Point point: points)
point.translateBMP(xOffset, yOffset);
}
Now the object knows its offsets. This makes it a bit heavier, but when we remove the translation later, we figure that will go away. And it probably doesn’t matter anyway, since there are only a few thousand Hit objects anyway.
What about the pixelsPerInch? Where can we get that information? We need to get it from the ShotPattern. It should be created knowing how many inches wide and high it is, and it should get the pixels information from the PatterningSheet, which reads the BMP file. So we begin by renaming the ShotPattern’s existing width and height fields to widthInPixels and heightInPixels, and we add new fields for width and height in inches, and for pixels per inch.
public class ShotPattern { int widthInPixels; int heightInPixels; List<Hit> hits = new ArrayList<Hit>(); private double widthInInches; private double heightInInches; private double xPixelsPerInch; private double yPixelsPerInch; public ShotPattern(int width, int height) { this.heightInPixels = height; this.widthInPixels = width; } public ShotPattern(String fileName) { this.widthInPixels = 2048; this.heightInPixels = 1536; PatterningSheet sheet = new PatterningSheet(fileName); hits = sheet.getHits(); } public ShotPattern(String fileName, double widthInInches, double heightInInches) { this.widthInInches = widthInInches; this.heightInInches = heightInInches; PatterningSheet sheet = new PatterningSheet(fileName); hits = sheet.getHits(); widthInPixels = sheet.widthInPixels(); heightInPixels = sheet.heightInPixels(); initPixelsPerInch(); } private void initPixelsPerInch() { xPixelsPerInch = widthInPixels / widthInInches; yPixelsPerInch = heightInPixels / heightInInches; }
We added the symmetric variables for x and y, even though we only have the code for the x coordinate being called. A small YAGNI violation perhaps, but we are typing in the code we see pretty clearly, not speculating about what we may in the future need. If we had written the getYinInches method, which we do need, all this would be called for. So sue us.
We note that our earlier ShotPattern constructors are not setting these variables up consistently, but on the other hand, all our tests would still run, except for grid00, which is what we’re working on.
We still don’t have the pixel per inch information in the get in inches methods in Hit. Our plan is to pass the conversion factor in from the ShotPattern, who does know it:
public int countHits(Rectangle2D rectangle) { int count = 0; for (Hit hit: hits) { if (rectangle.contains(hit.getXinInches(xPixelsPerInch), hit.getYinInches(yPixelsPerInch))) count++; } return count; }
Finally, we complete the methods in Hit:
public double getXinInches(double xPixelsPerInch) { int xInPixels = getX() + xOffset; return xInPixels / xPixelsPerInch; } public double getYinInches(double yPixelsPerInch) { int yInPixels = getY() - yOffset; return yInPixels / yPixelsPerInch; }
The test should run. But it doesn’t. After a bit of thinking, we realize that we’ve not adjusted the y coordinate correctly. We try again:
public double getYinInches(double yPixelsPerInch) {
int yInPixels = - (getY() + yOffset);
return yInPixels / yPixelsPerInch;
}
Still doesn’t work, so this time we work one out by hand:
public double getYinInches(double yPixelsPerInch) {
int yInPixels = yOffset - getY();
return yInPixels / yPixelsPerInch;
}
This makes our test pass. We celebrate for a moment, and then write three more tests:
@Test public void grid32() { pattern = new ShotPattern(folder+"tm1subset.bmp", 4.0, 3.0); RectangularGrid grid2x2 = new RectangularGrid(pattern,1,1); assertEquals(7, grid2x2.hitsIn(3,2)); } @Test public void grid02() { pattern = new ShotPattern(folder+"tm1subset.bmp", 4.0, 3.0); RectangularGrid grid2x2 = new RectangularGrid(pattern,1,1); assertEquals(2, grid2x2.hitsIn(0,2)); } @Test public void grid30() { pattern = new ShotPattern(folder+"tm1subset.bmp", 4.0, 3.0); RectangularGrid grid2x2 = new RectangularGrid(pattern,1,1); assertEquals(4, grid2x2.hitsIn(3,0)); }
Basically these are the corners of the test pattern, which we found easy to count. They run as well. We’re sure we’re done, with a much more robust way of calculating the densities.
As a final step, we grid the BMP file manually, count all the cells, and upgrade the FitNesse test:
The tests are all green. We have a structure in place for rectangular density counting, with most of the information being held in, and provided from, the right object. And it was 11 AM, which is lunch time for Chet and Ron.
Next time, we’ll go through, remove duplication, and refactor the whole system into a cleaner structure. But we have just implemented our “major change” by moving forward, rather than by moving backwards or sideways with “refactoring”. Now our refactoring will, we expect, consist mostly of removal of duplication, including code that is now unnecessary, plus bringing some code into line using the new constructors and methods. We expect that we’ll just remove the original spike versions that showed us roughly how to proceed, but that aren’t being used in this new code.
Some of the conclusions will need to be left to the next session, but I’d like to reflect a bit now as well.
Reflection | noitcelfeR
The most amazing bit of all this is that we went for two hours without a green bar. As frequent readers know, our standard cycle is more like ten minutes, not two hours. Yet we never felt nervous, and never really got in trouble. (There was the removal of the pixel translation that took three tries. I’ll come back to that.) Were we just lucky that this went so smoothly, or what?
There was just one edgy moment, during the pixel translation removal, when we had tried twice and had our line of code not work. Chet suggested writing a fine-grain unit test to check the conversion. As he was saying that, I had picked up our printout of the bitmap, and wrote down the real coordinates of a point, its translated coordinates, and the calcualtion necessary to bring it back to what it was. I was pretty sure I had it right, so I asked to be allowed to type it in and run the test – and it ran. Had it not run, we’d have drilled down with a finer-grain test.
We were almost entirely following our “by intention” expression of how to do the job. Almost everything we coded was a direct response to another intention-driven line of code. Most of our code was driven by Eclipse telling us that something would not yet compile.
The effect of this was that a clear intention of what we wanted, a couple of simple design decisions about where certain kinds of information should live, and following our noses and Eclipse’s nose, took us, step by step, right to the answer.
It’s common to have this experience in Smalltalk. You type a method and run it. It breaks because something is missing. You add the missing code in the debugger, and proceed. It breaks on the next missing thing. You repeat, following the code down to the bottom. It works smoothly and is part of the joy of working in Smalltalk. That same feeling is pretty rare in Java and C#, at least for us.
So it felt good. Still, it was two hours with no green bar. There were probably some opportunities in there for some smaller simple tests, helping us build smaller bridges from one place to another. I like to think that had we gotten in trouble, we’d have been sensitive to it and would have backed off. We usually manage to do that, and the trouble we got in a few days ago raised our sensitivity.
Bottom line, I’m on the cusp here. Things went very smoothly, nearly as close to “effortless perfection” as we ever get. Yet we were walking further from our usual test-focused path. I’m calling the lesson this way:
- Keep in mind the difference between spike code and real code, and don't try to build on a spike.
- Give a little more thought to what we really want, sticking a little closer to stories rather than speculation.
- Continue to do a few minutes of up front design on complex features, considering a couple of ways to go before diving in.
- Try to bear down a bit on getting a test running every ten minutes or so.
Use of Time (Added)
Starting from Shooting for the Foot – and Missing, we have six hours in. In that article, we spent two hours doing density, and decided that our spike code wasn’t good enough. We knew we had to clean up and refactor. In the next two articles, Shooting for Shibumi and this one, we report on four more hours. Of those four, we spent a full 90 minutes on the first day, revisiting what the requirement was, deciding on the best way to represent the grid, and discussing three alternative approaches. That’s 90 minutes out of 240 if we just count the last two days, or out of 360 if we include the foot-shooting episode. You can choose.
Either way, we spent 1/4 to 3/8 of our time talking about how to do this, planning our approach. Then we coded according to our plan, talking as we went along, discovering what we really meant when we chose our course, and working out the details in code. That’s rather more time than we usually spend in explicit analysis and designing. It was also quite productive, since it moved us from a very chaotic first attempt to a second attempt that went very smoothly.
Conclusion? Well, when you’re lost, look at a map. Learn to notice when things aren’t going well, and when they’re not, stop and take a bit more time to look around and figure out what to do and how to do it well. How frequently? Well, remember that these past three articles, like most of our articles here, represent just two hours of programming. If we assess where we are at least every couple of hours, we do a lot better. And, of course, you’ll see in most articles that we do a smaller assessment of what’s next just about every ten lines of code or so.
The lesson here, though, is that we profited from noticing that we were far from the ideal of smooth development, “effortless perfection”, and took the time to go back to basics. It made things better for us. Might it for you?
Wrapping Up ...
It has been a productive few sessions, resulting in code that works the way we want. We’ll have a couple of hours of cleaning up to do, and will display more of the code, before and after, that time. Thanks for joining in, and stay tuned.