I have the day off, and I drew a nice picture for the previous article, so I decided to work on a spike for Chet's radial pattern density chart. Let's find out what happens.

Radial Density

As I mentioned in the previous article, Chet wants to be able to measure pattern density on a circular chart, where the areas to be measured are arc-shaped areas delimited by angles on two sides, and radii on the other two. Here’s the picture again:

image

You’ll notice that I put some hits into the picture, anticipating that I would use it to define a test. There are a lot of dots in there, which make me think I’ll have to do a lot of typing, but life is cruel sometimes. Let’s dig right in. First, a …

Quick Design Session

At first glance, there appear to be two kinds of shapes in that picture. There are little pie slices on the inside, and arc-shaped pieces in the outer rings. But a bit of thinking tells us that the inner pie slices are really just arcs with the inner edge having a diameter of zero. (Standard math trick: reduce one problem to another.

Therefore, for each dot, in order to decide if it is inside a given arc, we want to ask whether its radius is larger than or equal to the inner value, and less than the outer. And we want to know whether the angle from the center to the dot is greater than or equal to the angle of one of the sides, and less than the angle of the other. As with our rectangle areas, we want to treat one side as inclusive, and the other as exclusive.

I’m aware that my customer, Chet, will probably change his mind about the size of the grid he wants, so that will have to be settable. I’m also remembering that I’ve changed the pattern density calculation as it stands to use a single rectangle that moves around the plane. It will be interesting to see whether that same style works for these arc-shaped grids.

(Odd thought. As a student of math, I’m aware that we can in principle treat the polar area as a transformation on the Cartesian plane. There is, in principle, a way to define a set of rectangles, and transform them into the arcs. The same transformation can be used to transform the points, and then the rectangle test can be used. Possibly a real mathematician would do it that way. Not me. I’m going to stick to my original plan, but stay alert to the slim possibility that some duplication will come out of this. (Slim? I can already see how it might happen …))

I’ll begin with the tedious part, typing in the hits for the test.

My Hit List

Hope and pray you aren’t on it …

Arrgh. The first thing I notice is that my handy template for tests has gone missing again. There must be something I’m doing wrong with Eclipse’s defaults. Hold on while I type that in again. If you know what I’m doing wrong, please clue me in. I sure don’t see what is making it reset that back to the default from time to time. Anyway, it’s better now. Here’s my rough test:

   @Test
    public void polarDensity() throws Exception {
        p.addHit(10,10);
        p.addHit(10,20);
        p.addHit(10,50);
        // ...
        // something = p.polarDensity(some parameters);
        // assertEquals(3, something[0]);
    }

I’ll read out the coordinates of the red dots (I cleverly plotted the picture on graph “paper” on my tablet), send them all in. Then I’ll make some kind of call to polarDensity, returning some kind of structure representing the answer. Then I’ll interrogate the elements to see if they have the right values. I don’t know what the parameters will have to be, and I’m not sure what the output will look like, but I don’t need to know yet. I can fill in the test values by rote, and let my brain think in the background about the questions of just how to call this method and what it returns. Take a break while I type in all those pairs of numbers.

So that you can share in the tedium, here’s how the test looks now:

   @Test
    public void polarDensity() throws Exception {

        p.addHit(20,5); // Octant 0
        p.addHit(25,5);
        p.addHit(30,10);

        p.addHit(10,10); // 1
        p.addHit(10,20);

        p.addHit(-5,20); // 2

        p.addHit(-10,5); // 3
        p.addHit(-20,10);

        p.addHit(-20,-5); // 4
        p.addHit(-15,-10);
        p.addHit(-20,-10);

        p.addHit(-5,-20); // 5
        p.addHit(-5,-25);

        p.addHit(10,-20); // 6

        p.addHit(30,-10); // 7

        p.addHit(50,10); // 8
        p.addHit(50,20);

        p.addHit(30,40); // 9
        p.addHit(20,40);
        p.addHit(10,50);

        p.addHit(-10,50); // 10
        p.addHit(-10,40);
        p.addHit(-20,50);
        p.addHit(-20,40);

        p.addHit(-40,30); // 11
        p.addHit(-50,20);
        p.addHit(-40,10);

        p.addHit(-50,-10); // 12
        p.addHit(-40,-20);
        p.addHit(-40,-30);

        p.addHit(-30,-40); // 13
        p.addHit(-20,-40);
        p.addHit(-20,-50);
        p.addHit(-10,-50);

        p.addHit(10,-40); // 14
        p.addHit(10,-50);
        p.addHit(20,-40);
        p.addHit(20,-50);
        p.addHit(30,-50);

        p.addHit(50,-10); // 15
        p.addHit(40,-20);
        p.addHit(40,-30);
        // ...
        // something = p.polarDensity(some parameters);
        // assertEquals(3, something[0]);
    }

I decided to count the dots going around by octants, first the inner ones, numbered 0-7, starting from the one just above the X axis, and then the outer ones, numbered 8-15. My subconscious hasn’t reported much back on the testing problem … no, wait, I hear voices. No, sorry, those are the mothers and children klatsching loudly here at Stonehouse Cafe. Anyway, let’s assume that we have two rings, and eight wedges. We can tile the circle by looping over wedges within rings, and the indexes of our output list can go from 0-15 just like our test numbers do. I can build a Wedge object like the Rectangle object, except this time it’ll be an object of my own invention, I expect, and test the points to see if they’re in there.

And that gives me my test:

   @Test
    public void polarDensity() throws Exception {

        p.addHit(20,5); // Octant 0
        p.addHit(25,5);
        p.addHit(30,10);

        p.addHit(10,10); // 1
        p.addHit(10,20);

        p.addHit(-5,20); // 2

        p.addHit(-10,5); // 3
        p.addHit(-20,10);

        p.addHit(-20,-5); // 4
        p.addHit(-15,-10);
        p.addHit(-20,-10);

        p.addHit(-5,-20); // 5
        p.addHit(-5,-25);

        p.addHit(10,-20); // 6

        p.addHit(30,-10); // 7

        p.addHit(50,10); // 8
        p.addHit(50,20);

        p.addHit(30,40); // 9
        p.addHit(20,40);
        p.addHit(10,50);

        p.addHit(-10,50); // 10
        p.addHit(-10,40);
        p.addHit(-20,50);
        p.addHit(-20,40);

        p.addHit(-40,30); // 11
        p.addHit(-50,20);
        p.addHit(-40,10);

        p.addHit(-50,-10); // 12
        p.addHit(-40,-20);
        p.addHit(-40,-30);

        p.addHit(-30,-40); // 13
        p.addHit(-20,-40);
        p.addHit(-20,-50);
        p.addHit(-10,-50);

        p.addHit(10,-40); // 14
        p.addHit(10,-50);
        p.addHit(20,-40);
        p.addHit(20,-50);
        p.addHit(30,-50);

        p.addHit(50,-10); // 15
        p.addHit(40,-20);
        p.addHit(40,-30);

        int[] densities = p.analyzePolar();
        assertEquals(3, densities[0]);
        assertEquals(2, densities[1]);
        assertEquals(1, densities[2]);
        assertEquals(2, densities[3]);
        assertEquals(3, densities[4]);
        assertEquals(2, densities[5]);
        assertEquals(1, densities[6]);
        assertEquals(1, densities[7]); 

        assertEquals(2, densities[8]);
        assertEquals(3, densities[9]);
        assertEquals(4, densities[10]);
        assertEquals(3, densities[11]);
        assertEquals(3, densities[12]);
        assertEquals(4, densities[13]);
        assertEquals(5, densities[14]);
        assertEquals(3, densities[15]);
    }

Note that I’ve finessed the question of setting parameters to the analyzePolar method. I’ll just write it internally to do two rings of eight octants, and then work out the parameters when I have a story for that. The test won’t quite compile, but when it does, it’ll go red. It’s a good time to break for lunch, though I hate to leave here, since the coffee ladies and their children are leaving. Anyway, it’s time for a break. I’m off to Zukey Lake Tavern. Then maybe I’ll go home and write the code to pass this test. Time so far: a couple of hours, counting writing the article.

Much Later ...

I’ve returned home, read some Vince Flynn, treated my wife to a dinner at Zukey Lake Tavern (yes, I ate there twice today – I’m a very simple man), and now I think I’ll code up analyzePolar. I’m going to try doing it by intention. So, let’s see, what might the code look like:

   public int[] analyzePolar() {
        Wedge[] wedges = createWedges();
        for (Wedge wedge: wedges) {
            for ( Hit hit: hits) {
                wedge.tally(hit);
            }
        }
        int tally = 0;
        int[] result = new int[16];
        for (Wedge wedge: wedges) {
            result[tally++] = wedge.count();
        }
        return result;
    }

    private Wedge[] createWedges() {
        Wedge[] wedges = new Wedge[16];
        int wedge = 0;
        int deltaR = 30;
        double deltaTheta = Math.PI/4;
        for (int radius = 0; radius < 60; radius += deltaR) {
            for (double theta = 0; theta < 2*Math.PI; theta += deltaTheta) {
                wedges[wedge++] = new Wedge(radius, radius+deltaR, theta, theta+deltaTheta);
            }
        }
        return wedges;
    }

That seems reasonable. We’ll need a Wedge class … Eclipse will write one for me. And a tally() method … I’ll just fill in the blanks. Here’s Wedge:

package com.hendricksonxp.patterning.model;

public class Wedge {

    private double innerR;
    private double outerR;
    private double lowTheta;
    private double highTheta;
    private int    count;

    public Wedge(int innerR, int outerR, double lowTheta, double highTheta) {
        this.innerR    = innerR;
        this.outerR    = outerR;
        this.lowTheta  = lowTheta;
        this.highTheta = highTheta;
    }

    public void tally(Hit hit) {
        if (contains(hit))
            count++;
    }

    private boolean contains(Hit hit) {
        if (hit.r() < innerR) return false;
        if (hit.r() >= outerR) return false;
        if (hit.theta() < lowTheta) return false;
        if (hit.theta() >= highTheta) return false;
        return true;
    }

    public int count() {
        return count;
    }
}

So the Wedge knows its inner and outer radius and its low and high angle (theta), and it does compares analogous to those in the Rectangle to decide whether it contains a given Hit. The Hit needs to compute r() and theta().

   public double r() {
        r = Math.sqrt(x*x+y*y);
        return r;
    }

    public double theta() {
        theta = Math.atan2((double)y, (double) x);
        if (theta < 0) theta += 2*Math.PI;
        return theta;
    }

The calculation there for theta() is the third version. Here’s why:

I typed in the code with the help of all Eclipse’s little messages and code generators, and it looked really good. But the test didn’t run. One problem was that I used atan(y/x) to get theta. I had forgotten that you have to use atan2(y,x) in order to get values all the way around the clock.

But the tests still didn’t run: they got two ticks in the zero octant, not three as shown in the picture. See that point at 30,10? Well, the radius of that one is 31, which is bigger than 30. Uh … oh. I drew the circle poorly. It goes through 40, not 30, in positive X. That changes a few things. I think I’ll just move that one point and see what happens. Hold on …

That one works, but now it’s failing on wedge[4]. Theta is coming back as -2.something. Darn. We need to normalize theta to be between - and 2 PI. Fix the theta method. (I’ll show you in a moment.) That works. wedge[7] fails. Another 30. This time I’ll move the dot from (30,-10) to (20,-10), because otherwise we wouldn’t have any tallies in that cell. And we’re green!

Here’s a view of the revised picture from which the test was written. The black circle shows how far off my sketch was. So much for drawing on computerized graph paper.

image

I wrote a few auxiliary tests for Wedge along the way, and I set a couple of breakpoints. (I found the (30,10) problem by inspecting r and theta for that point, and observing cleverly that 31 is more than 30.) The DensityTest now looks like this:

package com.hendricksonxp.patterning.test;

import static org.junit.Assert.*;

import org.junit.Before;
import org.junit.Test;

import com.hendricksonxp.patterning.model.Hit;
import com.hendricksonxp.patterning.model.ShotPattern;
import com.hendricksonxp.patterning.model.Wedge;

public class DensityTest {
    ShotPattern p;

    @Before
    public void setUp() throws Exception {
        p = new ShotPattern(6,6);
    }

    @Test
    public void fourQuadrants() {
        p.addHit(1,1);
        p.addHit(3,1);
        p.addHit(4,1);
        p.addHit(0,3);
        p.addHit(1,3);
        p.addHit(3,3);
        p.addHit(4,3);
        p.addHit(0,4);
        p.addHit(1,4);
        p.addHit(3,4);
        int[] densities = p.analyzeDensity(3,3);
        assertEquals(1, densities[0]);
        assertEquals(2, densities[1]);
        assertEquals(4, densities[2]);
        assertEquals(3, densities[3]);
    }

    @Test
    public void wedge0() throws Exception {
        Wedge wedge = new Wedge(0, 30, 0, Math.PI/4);
        assertEquals(0, wedge.count());
        wedge.tally(new Hit(20,5));
        assertEquals(1, wedge.count());
        wedge.tally(new Hit(25,5));
        assertEquals(2, wedge.count());
        wedge.tally(new Hit(30,10));
        assertEquals(2, wedge.count());
    }

    @Test
    public void wedge4() throws Exception {
        Wedge wedge = new Wedge(0, 30, Math.PI, 5*Math.PI/4);
        assertEquals(0, wedge.count());
        wedge.tally(new Hit(-20,-5));
        assertEquals(1, wedge.count());
    }

    @Test
    public void polarDensity() throws Exception {

        p.addHit(20,5); // Octant 0
        p.addHit(25,5);

        p.addHit(10,10); // 1
        p.addHit(10,20);

        p.addHit(-5,20); // 2

        p.addHit(-10,5); // 3
        p.addHit(-20,10);

        p.addHit(-20,-5); // 4
        p.addHit(-15,-10);
        p.addHit(-20,-10);

        p.addHit(-5,-20); // 5
        p.addHit(-5,-25);

        p.addHit(10,-20); // 6

        p.addHit(20,-10); // 7

        p.addHit(50,10); // 8
        p.addHit(50,20);
        p.addHit(30,10);

        p.addHit(30,40); // 9
        p.addHit(20,40);
        p.addHit(10,50);

        p.addHit(-10,50); // 10
        p.addHit(-10,40);
        p.addHit(-20,50);
        p.addHit(-20,40);

        p.addHit(-40,30); // 11
        p.addHit(-50,20);
        p.addHit(-40,10);

        p.addHit(-50,-10); // 12
        p.addHit(-40,-20);
        p.addHit(-40,-30);

        p.addHit(-30,-40); // 13
        p.addHit(-20,-40);
        p.addHit(-20,-50);
        p.addHit(-10,-50);

        p.addHit(10,-40); // 14
        p.addHit(10,-50);
        p.addHit(20,-40);
        p.addHit(20,-50);
        p.addHit(30,-50);

        p.addHit(50,-10); // 15
        p.addHit(40,-20);
        p.addHit(40,-30);

        int[] densities = p.analyzePolar();
        assertEquals(2, densities[0]);
        assertEquals(2, densities[1]);
        assertEquals(1, densities[2]);
        assertEquals(2, densities[3]);
        assertEquals(3, densities[4]);
        assertEquals(2, densities[5]);
        assertEquals(1, densities[6]);
        assertEquals(1, densities[7]); 

        assertEquals(3, densities[8]);
        assertEquals(3, densities[9]);
        assertEquals(4, densities[10]);
        assertEquals(3, densities[11]);
        assertEquals(3, densities[12]);
        assertEquals(4, densities[13]);
        assertEquals(5, densities[14]);
        assertEquals(3, densities[15]);
    }
}

Observations

I’m now sure that I can readily do a radial pattern and classify the hits into sections. (There is an issue on that, to discuss below.) The objects seem to me to be just about right, though I am sure there are many things that should be done. They’ll turn up as we go forward. One is that the Hit calculates r and theta every time they’re asked for. (It saves them so that I could look at them in the debugger. We’ll talk about that as well.)

This code isn’t super clean yet, and on a given day I’d suggest making it more nearly squeaky clean. Today isn’t that day, though, and I’d like to muse on that as well.

Finally, I need to confess that I used the debugger a couple of times, to stop the system during hit classification, and to see why pixels were being classified wrongly. Note that in a few cases, my test answers were wrong, and I don’t feel bad about looking to see why the computer was right.

Using the Debugger

It troubles me, though, to be using the debugger. If I had been a little more careful with the conversion to polar coordinates, actually TDDing it, then those bugs would very likely not have occurred. I took a pretty big bite with the Wedge code, thinking that I knew just what was needed. I was nearly right … there were no big delays getting it to work. Still, neither of the polar conversion errors would have needed a debugger.

Discovering that I had drawn the circle on the wrong side of the (30,10) point, however, was less likely to have been found with TDD. Sure it’s possible to write a test that will show that 30,10 isn’t in the inner zero-angle octant, but why would I? Given the picture as I drew it, it looks like it should be there.

So when I find myself tempted to use the debugger, there’s a very good chance that I’ve taken too big a bite and that finer-grained tests would have avoided the confusion. I really don’t like feeling confused, so it’s a good reminder.

Squeaky Clean

I notice that I’m not polishing this code as I generally do with other examples. This is due, in part, to the fact that we are just spiking here, and that the learning is what’s important. But I’m wondering whether there is more to it, whether the fact that the topic is one I’ve not worked on, or some kind of deadline pressure, is pushing me toward stopping before I’m really “done”.

I’m not consciously feeling any pressure, nor do I feel like I’m reaching beyond my meager capacities. But it’s definitely the case that these classes aren’t polished as far as I’d commonly do. We need to keep an eye on that.

Hit Classification

We have a story ahead of us that will consolidate all the pixels that are adjacent to one another into one “big” Hit. When we do that, we’ll have the possibility that the pixels making up one big Hit will lie on opposite sides of some classification line. (In two different octants, for example.)

Some solutions have occurred to us. One would be to classify the Hit into the section that holds more of the pixels of the hit. Another would be that the first section that sees the Hit gets it, and others do not. A third would be to give the hit a “center of gravity”, and use that to classify it.

Some of these solutions may imply changes to the classification code, while others may imply changes only inside the Hit object itself. We’re not worried about these, nor are we going to make any changes “in preparation” for this upcoming story. I mention it because (a) we are aware there may be upcoming changes, and (b) we’re not going to generalize our code in antici …

… pation. Watch and see what happens: we will be.

Summing Up

There are still only a few hours in this project, surely less than two full working days. We have learned a lot, and stumbled around quite a bit as well. Our web searches for code that would help have been unsuccessful in a few cases (and we’ve had great help from our friends on line to make up for that). We’ve been taken to task a bit, and may address some of those task-takings-to in future comments.

Our code is a bit more sloppy-feeling than I’d like, but I keep reminding myself that it’s very early days and we haven’t really implemented any stories yet: we’re just spiking and building up a base of understanding in a new domain. But it has been two days, and we’ve required whole teams to complete stories in the first two days of their projects, so we’d better get down to it!

All in all, I’m very optimistic that we can do what Chet needs, and feeling just a little loose about the code we have so far. Kind of like driving on a slightly slippery road.

Keep an eye on us, and keep those cards and letters coming! Knowing you’re out there keeps us going.