// Optimal many-translucent-circles painter

// [ O(w*h) + O(n*r) ]

//

// with

//   w = image width

//   h = image height

//   n = # circles

//   r = average height of a circle

//

// Comparison:

// - Naive painting is O(w*h) + O(n*r*r)

// - Naive raytracing is O(w*h*n)

//

// Loose proof of optimality:

// - A term of O(w*h) is always required just to paint each pixel.

// - And n*r is the minimum number of steps you have to do to actually

//   figure out each circle's shape (either by walking around it

//   or by calculating its width on each line).

sclass ManyCirclePainter is MakesBufferedImage {

  settable int w;

  settable int h;

  settable new L<Circle> circles;

  int[] pixels;

  L<Circle>[] startCircle, stopCircle;

  bool ran;

  srecord Circle(Pt center, int radius) {}

  public int getWidth() { ret w; }

  public int getHeight() { ret h; }

  selfType addCircle(int x, int y, int radius) {

    circles.add(new Circle(pt(x, y), radius));

    this;

  }

  run {

    if (ran) ret;

    set ran;

    pixels = new int[w*h];

    if (pixels.length == 0) ret;

    int nCircles = l(circles);

    startCircle = new L[h];

    stopCircle = new L[h];

    for (circle : circles) {

      int y1 = max(0, circle.center.y-circle.radius);

      int y2 = circle.center.y+circle.radius+1;

      if (y1 >= y2) continue;

      startCircle[y1] = addOrCreate(startCircle[y1], circle);

      if (y2 < h)

        stopCircle[y2] = addOrCreate(stopCircle[y2], circle);

    }

    int[] startStop = new[w];

    new Set<Circle> liveCircles;

    int iPixel = 0;

    for y to h: {

      fillArray(startStop, 0);

      addAll(liveCircles, startCircle[y]);

      removeAll(liveCircles, stopCircle[y]);

      for (c : liveCircles) {

        // width of circle at this line

        int width = iround(sqrt(sqr(c.radius)-sqr(y-c.center.y)));

        int x1 = c.center.x-width, x2 = c.center.x+width+1;

        if (x1 > w || x2 <= 0) continue; // not visible at all at this row

        startStop[max(x1, 0)]++;

        if (x2 < w)

          startStop[x2]--;

      }

      int count = 0;

      for x to w: {

        count += startStop[x];

        pixels[iPixel++] = countToColor(count, nCircles);

      }

    }

  }

  int countToColor(int count, int nCircles) {

    ret rgbIntFromBrightness(doubleRatio(count, min(nCircles, 8)));

  }

  public BufferedImage getBufferedImage aka get() {

    run();

    ret bufferedImageWithoutAlpha(w, h, pixels);

  }

}