У меня была такая же потребность. Вот мое решение с кодом. Ошибка составляет не более половины пикселя.
Я основал свое решение на алгоритме эллипса Макилроя , алгоритме только для целых чисел, который математически доказал, что Макилрой имеет точность до половины пикселя, без пропусков или лишних точек, и правильно рисует вырожденные случаи, например линии и круги. л. Патрик дополнительно проанализировал алгоритм Макилроя, включая способы его оптимизации и то, как заполненный эллипс можно разбить на прямоугольники.
Алгоритм Макилроя отслеживает путь через один квадрант эллипса; остальные квадранты отображаются через симметрию. Каждый шаг на пути требует трех сравнений. Многие из других алгоритмов эллипса используют вместо этого октанты, которые требуют только двух сравнений на шаг. Однако методы, основанные на октантах, имеют общеизвестно неточные границы на октантах. Небольшая экономия одного сравнения не стоит неточности в методах октантов.
Как и практически любой другой алгоритм целочисленных эллипсов, Макилрой хочет, чтобы центр имел целочисленные координаты, а длины осей a и b также были целыми числами. Однако мы хотим иметь возможность рисовать эллипс с ограничительной рамкой, используя любые целочисленные координаты. Ограничительная рамка с четной шириной или четной высотой будет иметь центр на целой с половиной координате, а a или b будет на целое с половиной.
Мое решение состояло в том, чтобы выполнить вычисления, используя целые числа, которые удваивают того, что необходимо. Любая переменная, начинающаяся с q, рассчитывается из значений в два пикселя. Чётная q переменная находится в целочисленной координате, а нечетная q переменная - в целочисленной координате. Затем я переработал математику Макирой, чтобы получить правильные математические выражения с этими новыми удвоенными значениями. Это включает в себя изменение начальных значений, когда ограничивающая рамка имеет четную ширину или высоту.
Вот подпрограмма / метод drawEllipse, приведенный ниже. Вы предоставляете ему целочисленные координаты (x0, y0) и (x1, y1) ограничительной рамки. Неважно, если x0 <<code>x1 против x0> x1; это поменяет их по мере необходимости. Если вы укажете x0 == x1, вы получите вертикальную линию. Аналогично для y0 и y1 координат. Вы также предоставляете логический параметр fill, который рисует только контур эллипса, если false, и рисует заполненный эллипс, если true. Вы также должны предоставить подпрограммы drawPoint(x, y), которые рисуют одну точку, и drawRow(xleft, xright, y), которая рисует горизонтальную линию от xleft до xright включительно.
Макилрой и Патрик оптимизируют свой код для свертывания констант, повторного использования общих подвыражений и т. Д. Для ясности я этого не делал. Сегодня большинство компиляторов делают это автоматически сегодня.
void drawEllipse(int x0, int y0, int x1, int y1, boolean fill)
{
int xb, yb, xc, yc;
// Calculate height
yb = yc = (y0 + y1) / 2;
int qb = (y0 < y1) ? (y1 - y0) : (y0 - y1);
int qy = qb;
int dy = qb / 2;
if (qb % 2 != 0)
// Bounding box has even pixel height
yc++;
// Calculate width
xb = xc = (x0 + x1) / 2;
int qa = (x0 < x1) ? (x1 - x0) : (x0 - x1);
int qx = qa % 2;
int dx = 0;
long qt = (long)qa*qa + (long)qb*qb -2L*qa*qa*qb;
if (qx != 0) {
// Bounding box has even pixel width
xc++;
qt += 3L*qb*qb;
}
// Start at (dx, dy) = (0, b) and iterate until (a, 0) is reached
while (qy >= 0 && qx <= qa) {
// Draw the new points
if (!fill) {
drawPoint(xb-dx, yb-dy);
if (dx != 0 || xb != xc) {
drawPoint(xc+dx, yb-dy);
if (dy != 0 || yb != yc)
drawPoint(xc+dx, yc+dy);
}
if (dy != 0 || yb != yc)
drawPoint(xb-dx, yc+dy);
}
// If a (+1, 0) step stays inside the ellipse, do it
if (qt + 2L*qb*qb*qx + 3L*qb*qb <= 0L ||
qt + 2L*qa*qa*qy - (long)qa*qa <= 0L) {
qt += 8L*qb*qb + 4L*qb*qb*qx;
dx++;
qx += 2;
// If a (0, -1) step stays outside the ellipse, do it
} else if (qt - 2L*qa*qa*qy + 3L*qa*qa > 0L) {
if (fill) {
drawRow(xb-dx, xc+dx, yc+dy);
if (dy != 0 || yb != yc)
drawRow(xb-dx, xc+dx, yb-dy);
}
qt += 8L*qa*qa - 4L*qa*qa*qy;
dy--;
qy -= 2;
// Else step (+1, -1)
} else {
if (fill) {
drawRow(xb-dx, xc+dx, yc+dy);
if (dy != 0 || yb != yc)
drawRow(xb-dx, xc+dx, yb-dy);
}
qt += 8L*qb*qb + 4L*qb*qb*qx + 8L*qa*qa - 4L*qa*qa*qy;
dx++;
qx += 2;
dy--;
qy -= 2;
}
} // End of while loop
return;
}
На изображении выше показаны выходные данные для всех ограничивающих рамок размером до 10х10. Я также запустил алгоритм для всех эллипсов размером до 100х100. Это дало 384614 очков в первом квадранте. Была рассчитана ошибка между тем, где каждая из этих точек была нанесена, и местом, где происходит фактический эллипс. Максимальная ошибка составляла 0,500000 (половина пикселя), а средняя ошибка среди всех точек составляла 0,216597.