Рисование эллипса с помощью алгоритма Брезенхэма

Используя член ошибки e = ax^2 + by^2 - r^2, довольно легко показать, что шаг от (x,y) до (x,y+1) изменяет ошибку на 2by + b, шаг до (x+1,y+1) на 2ax + a + 2by + b и шаг до (x+1,y) на 2ax + a.

Начиная с точки (-x0, 0), выберите шаг с наименьшей абсолютной ошибкой из этих трех. Первые два случая - норма для "первого региона", как вы его называете.

В первый раз, когда шаг вправо, от (x,y) до (x+1,y), дает наименьшую ошибку, вы знаете, что находитесь во второй области. На данный момент первый случай больше не нужен. Четверть эллипса можно закончить, используя только вторые два случая.

Обратите внимание, что эта проверка позволяет избежать операций с плавающей запятой, которые вы использовали. Весь смысл алгоритмов Брезенхема заключается в том, чтобы избегать операций с плавающей запятой.

Последнее, на что следует обратить внимание, это то, что вы не хотите вычислять 2ax или 2by на каждой итерации. Умножений можно избежать, сохраняя переменные, скажем, dx=2ax и dy=2by, и обновляя их. Шаг от x до x+1 увеличивает dx на 2a, константу. Точно так же шаг от y до y+1 увеличивает dy на 2b.

Собрав все это вместе, вы получите (грубый) код ниже.

Обратите внимание, что вы можете проверить вычисление инкрементной ошибки, сравнив его с исходным членом ошибки. Если (x0,0) — начальная точка, то вы знаете, что x0^2 = r^2. Таким образом, фактическая ошибка на каждой итерации равна a * x^2 + b * y^2 - x0^2. Это должно быть равно e в приведенном ниже коде, и это так.

import static java.lang.Math.abs;
import java.util.Arrays;
import java.util.function.BiConsumer;

public class EllipseTracer {
  static char [] [] raster = new char[51][101]; 

  static void trace(int x, int y, int a, int b, BiConsumer<Integer, Integer> emitter) {
    emitter.accept(x, y);
    int e = 0;
    int dx = 2 * a * x;
    int dy = 2 * b * y;
    // First region: stepping north and northeast.
    while (x < 0) {
      int dxa = dx + a;
      int dyb = dy + b;
      int eUp = e + dyb;
      int eRt = e + dxa;
      int eDg = e + dxa + dyb;
      if (abs(eUp) < abs(eDg)) {
        emitter.accept(x, ++y);
        e = eUp;
        dy += 2 * b;
      } else {
        if (abs(eRt) < abs(eDg)) {
          // Step east is least error. Found second region.
          emitter.accept(++x, y);
          e = eRt;
          dx += 2 * a;
          break;
        }
        emitter.accept(++x, ++y);
        e = eDg;
        dy += 2 * b;
        dx += 2 * a;
      }
    }
    // Second region: step northeast and east.
    while (x < 0) {
      int dxa = dx + a;
      int dyb = dy + b;
      int eRt = e + dxa;
      int eDg = e + dxa + dyb;
      if (abs(eRt) < abs(eDg)) {
        emitter.accept(++x, y);
        e = eRt;
        dx += 2 * a;
      } else {
        emitter.accept(++x, ++y);
        e = eDg;
        dy += 2 * b;
        dx += 2 * a;
      }
    }
  }

  static void emit(int x, int y) {
    raster[y][x + 100] = '*';
  }

  public static void main(String [] args) {
    for (int i = 0; i < raster.length; ++i) {
      Arrays.fill(raster[i], ' ');
    }
    trace(-100, 0, 1, 4, EllipseTracer::emit);
    for (int i = 0; i < raster.length; ++i) {
      System.out.println(raster[i]);
    }
  }
}

Вы можете добавить больше трюков, чтобы избежать абсолютных значений, но я позволю вам поискать их.