Below is a long-winded algorithm to do a rather simple task. What I imagined from the start was something to dump an array of points starting at the center and spiraling outward, so that I could quickly write applets which used these points for mapping something linear to a radial display.

Originally I had a rather bland loop for drawing a very tight spiral that grew very slowly in order to hit every pixel on the screen. Most loop cycles were wasted because it hit the same pixel again and again, but I couldn't speed it up otherwise I'd get holes in the spiral.

So I wondered how hard it would be to write a loop in which each iteration yielded a new point on my spiral, without dealing anything but the simplest of trigonometry - the distance formula (does this even count as trig?). My original plan was as follows:

1. Start in the very center of the applet.
2. Evaluate the surrounding 8 pixels and eliminate those that have already been used.
3. Determine each of the unused pixels' distances to the center.
4. If one is obviously the closest, use that one and start the loop over again.
5. If two or more are tied for closeness, randomly pick one and start the loop over again.

So I wrote all these rules up and put them into overly complicated code and ran it. Rather than building a circular spiral, it seems to build kind of an octagon and switches directions frequently. It's very odd behavior, and I can't figure out what exactly is causing it other than the use of randomness to solve conflicts. Perhaps it's because it tries to find the closest pixel to the exact center of the applet, which isn't a pixel itself.

(And yeah, I realize that this will fail the instant it hits the edge of the applet...)

Code:

int x, y;

void setup() {
  size(500, 500);
  background(255);
  
  x = (int)Math.round(width / 2);
  y = (int)Math.round(height / 2);
}

void draw() {
  int[][] choices = { { x - 1, y - 1 }, { x, y - 1 }, { x + 1, y - 1 },
                      { x - 1, y     }, /* CENTER */  { x + 1, y     },
                      { x - 1, y + 1 }, { x, y + 1 }, { x + 1, y + 1 } };
  float[] distances = new float[8];
                        
  // Eliminate choices out of bounds and find the distance from the center
  for(int i = 0; i < 8; i ++) {
    if(choices[i][0] < 0 || choices[i][0] >= width || choices[i][1] < 0 || choices[i][1] >= height) {
      choices[i][0] = 0xDEADBEEF;
      choices[i][1] = 0xFEEDFACE;
    } else {
      distances[i] = dist(choices[i][0], choices[i][1], width / 2, height / 2);
    }
  };
  
  // Are any of them already taken?
  for(int i = 0; i < 8; i ++) {
    if(get(choices[i][0], choices[i][1]) != 0xFFFFFFFF) {
      choices[i][0] = 0xDEADBEEF;
      choices[i][1] = 0xFEEDFACE;
    }
  }
  
  // Try to find the shortest distance
  float shortestDist = 0xADDEDBAD;
  int   shortestIndx = 0xC0DEDBAD;
  for(int i = 0; i < 8; i ++) {
    if(choices[i][0] != 0xDEADBEEF && choices[i][1] != 0xFEEDFACE) {
      if(distances[i] < shortestDist || (shortestDist == 0xADDEDBAD && shortestIndx == 0xC0DEDBAD)) {
        shortestDist = distances[i];
        shortestIndx = i;
      } else if(distances[i] == shortestDist) {
        shortestIndx = 0xC0DEDBAD;
      }
    }
  }
  
  // Pick our good one
  int choiceIndx = 0xC0DEBABE;
  
  // If there was a shortest, go with it
  if(shortestDist != 0xADDEDBAD && shortestIndx != 0xC0DEDBAD) {
    choiceIndx = shortestIndx;

  // Otherwise, we'll pick one randomly
  } else if(shortestDist != 0xADDEDBAD) {
  
    // Some are tied for shortest distance
    int randIndx = (int)random(0, 8);
    while(distances[randIndx] != shortestDist || (choices[randIndx][0] == 0xDEADBEEF && choices[randIndx][1] == 0xFEEDFACE))
      randIndx = (int)random(0, 8);
    choiceIndx = randIndx;
   
  } else {
    // I don't think we should ever reach this point
    println("Something went horribly wrong...");
    noLoop();
    return;
  }
  
  // We're done with this pixel
  if(choiceIndx != 0xC0DEBABE) {
    x = choices[choiceIndx][0];
    y = choices[choiceIndx][1];
    set(x, y, color(0));
  } else {
     println("We seem to have reached an unexpected point.");
     noLoop();
     return;
  }
  
  if(!testCorners()) {
    println("Finished.");
    noLoop();
  }
}

boolean testCorners() {
  if(get(0, 0) == 0xFFFFFFFF) return true;
  if(get(width - 1, 0) == 0xFFFFFFFF) return true;
  if(get(0, height - 1) == 0xFFFFFFFF) return true;
  if(get(width - 1, height - 1) == 0xFFFFFFFF) return true;
  return false;
} 

It's really obvious the diagonal pixels from the center are further away, because basically you're measuring 1 pixel on the top, bottom, left and right pixels (1 square away) and 1.41 on the topright, topleft, bottomright, bottomleft pixels, because its a diagonal square away (sqrt(2)). You should incorporate these distances in your algo.

Koenie

Hey rgovostes,

I made this applet:
http://mkv25.net/applets/blackHole/
Which draws an almost perfect circle by spiraling around adding a pixel to each side as it goes.

I figured you needed the correct spiral code to get what you originally wanted.. and I found Archimedes Spiral.

Nice simple maths:
radius = constant * theta;

And then plotting a polar coordinate:
x1 = int(r * cos(theta)) + width/2;
y1 = int(r * sin(theta)) + height/2;

It forms pretty much a perfect circle as it spirals out. It relies on redundancy to make sure it doesn't miss any pixels.

To reduce redundancy I use this thinking:
- Calculate coordinate of new pixel
- (If new pixel is already black (set) Then chances are next pixel will be too)
- Multiply the amount we increment by to increase the chance of of a blank slot
- Loop from top until blank slot found
- Set pixel as black
- Reset increment
- Loop from top

The value I used to multiply the increment by is 1.04; in this example. Multiplying by 1.05 missed a few pixels out at larger scales.
The other factor involved with missing pixels was the size of the initial increment, which I set to 0.00005, so that even at large radii pixels weren't skipped.

For smaller radii 'circles' e.g. 35 pixels diameter you can afford to increase the increment to 0.005 and the increment multiplier to 1.2;

My applet includes a speed up feature, keys 1-7... and a check to stop processing if x and y are out of bounds.

The redundancy problems were the reason I went on this crazy route in the first place, but it seems you've done a great job of reducing it. Kudos! This surely will come in handy

I adapted your code to print out an approximation of how much theta had to increment before the next pixel was hit. Then I stuck these values in my graphing calculator and tried to find a correlation between them, but they seemed to be pretty random.

Code:

1.3400307, 1.4200325, 1.4700336, 0.10000229, 1.3900318, 1.5100346, 1.5200348, 0.8600197, 1.3500309, 0.85001945, 0.5900135, 0.0700016, 0.88002014, 0.5200119, 0.20000458, 0.82001877, 0.47001076, 1.0800247, 0.43000984, 1.5200348, 1.5200348, 0.5900135, 0.5900135, 0.34999084, 0.49991608, 0.089984894, ... 

While playing with it, I had the idea of reversing the equation so that given an (x, y) coordinate, it would return the theta value used to compute it. Then you could sort the list of pixels by the corresponding theta value and have an array.

The code below does this (kind of) almost instantly. I messed up my math somewhere (or I made a false assumption) so rather than drawing a spiral makes a pinwheel. The sorting method is probably less than ideal.

Code:

float[][] table;

void setup() {
  size(200, 200);
  background(255);

  populateTable();
}

void populateTable() {
  println("Populating table for " + width + " x " + height);

  table = new float[width * height][2];
  float cx = width / 2;
  float cy = height / 2;
  
  for(int x = 0; x < width; x ++)
  for(int y = 0; y < height; y ++) {
    float r = dist(x, y, cx, cy);
    float theta = atan((y - cy) / (x - cx));
    theta += 0.1 * r;
    
    table[y * width + x][0] = theta; // Value
    table[y * width + x][1] = y * width + x; // Pixel index
  }
  
  println("Table populated!");
}
 
void draw() { 
  float minimum = -1;
  int minindx = -1;
  for(int j = 0; j < table.length; j ++) {
    if((table[j][0] < minimum || minindx == -1) && table[j][0] > -1) {
      minimum = table[j][0];
      minindx = j;
    }
  }
    
  if(minimum == -1 || minindx == -1) {
    println("Finished!");
    noLoop();
    return;
  }
  
  // No longer a valid point
  table[minindx][0] = -1;
     
  loadPixels();
  pixels[(int)table[minindx][1]] = color(0);
  updatePixels();
} 

This paper is fairly technical, but it looks like it shows you EXACTLY how to generate spirals, and does not need to look at every-single pixel in the window, so it should be much faster.

http://wscg.zcu.cz/wscg2002/Papers_2002/F11.pdf

Take a crack at it, and then I can help you get your sketch working.

I'm very new to processing sketch writing, so I can't write anything much myself, but I'll help you understand the algorithm stuff if you need it.