I must admit that I strongly believe there is more symmetry in a circle than in an ellipse. Where a circle might be mirrored on any axis through center, for an ellipse, this is possible only with x and y axis in general. Hence, I believe that the midPointCircleThick() cannot be adapted for an ellipse.
So, I started my implementation with the midpointEllipse() provided by the OP.
These were my basic thoughts:
IMHO, the Bresenham Line algorithm is the origin of the Midpoint Circle algorithm as well as the Midpoint Ellipse algorithm. This might be helpful to understand the error/delta magic which is used. It's much simpler for a line but follows the same idea adapted to x²/a² + y²/b² = 1 (the ellipse equation).
With origin in center of ellipse, the midpointEllipse() renders all 4 quadrants simultaneously (exploiting the symmetry). Hence, only the curve in one quadrant has to be computed effectively. The curve is in this area monotonic.
The midpointEllipse() has two regions:
- Starting at points on x axis, ∆y > ∆x until cross-even.
- Afterwards, ∆x > ∆y.
My concept was to adapt the midpointEllipse() that way, that the code is "duplicated" to manage two points (one for inner border, one for outer) with identical y coordinates to draw horizontal lines (span lines).
My first observation was that the new algorithm has to manage a final phase (for innerRadius.y < y ≤ outerRadius.y where only the points on outer border have to be considered.
Remembering that the original algorithm has two regions, there are now two regions for the outer border, two regions for the inner border, and the two phases mentioned above. This allows a variety of combinations. (To get this managed was the main effort in my implementation.)
The sample implementation (based on Qt to have a simple visualization):
#include <functional>
#include <QtWidgets>
class View: public QLabel {
public:
View(QWidget *pQParent = nullptr):
QLabel(pQParent)
{ }
virtual ~View() = default;
View(const View&) = delete;
View& operator=(const View&) = delete;
protected:
virtual void paintEvent(QPaintEvent *pQEvent) override;
};
struct Point { int x, y; };
using Color = QColor;
void midpointEllipse(
Point center,
Point radius,
std::function<void(const Color&, const Point&)> setPixel)
{
Point pos = { radius.x, 0 };
Point delta = {
2 * radius.y * radius.y * pos.x,
2 * radius.x * radius.x * pos.y
};
int err = radius.x * radius.x
- radius.y * radius.y * radius.x
+ (radius.y * radius.y) / 4;
while (delta.y < delta.x) {
setPixel(Qt::blue, { center.x + pos.x, center.y + pos.y });
setPixel(Qt::blue, { center.x + pos.x, center.y - pos.y });
setPixel(Qt::blue, { center.x - pos.x, center.y + pos.y });
setPixel(Qt::blue, { center.x - pos.x, center.y - pos.y });
pos.y++;
if (err < 0) {
delta.y += 2 * radius.x * radius.x;
err += delta.y + radius.x * radius.x;
} else {
pos.x--;
delta.y += 2 * radius.x * radius.x;
delta.x -= 2 * radius.y * radius.y;
err += delta.y - delta.x + radius.x * radius.x;
}
}
err = radius.x * radius.x * (pos.y * pos.y + pos.y)
+ radius.y * radius.y * (pos.x - 1) * (pos.x - 1)
- radius.y * radius.y * radius.x * radius.x;
while (pos.x >= 0) {
setPixel(Qt::yellow, { center.x + pos.x, center.y + pos.y });
setPixel(Qt::yellow, { center.x + pos.x, center.y - pos.y });
setPixel(Qt::yellow, { center.x - pos.x, center.y + pos.y });
setPixel(Qt::yellow, { center.x - pos.x, center.y - pos.y });
pos.x--;
if (err > 0) {
delta.x -= 2 * radius.y * radius.y;
err += radius.y * radius.y - delta.x;
} else {
pos.y++;
delta.y += 2 * radius.x * radius.x;
delta.x -= 2 * radius.y * radius.y;
err += delta.y - delta.x + radius.y * radius.y;
}
}
}
void midpointEllipseThick(
Point center,
Point innerRadius,
Point outerRadius,
std::function<void(const Color&, const Point&, int)> horiLine)
{
/// @todo validate/correct innerRadius and outerRadius
Point pos = { outerRadius.x, 0 };
Point deltaOuter = {
2 * outerRadius.y * outerRadius.y * pos.x,
2 * outerRadius.x * outerRadius.x * pos.y
};
auto errOuterYX
= [&]() {
return outerRadius.x * outerRadius.x
- outerRadius.y * outerRadius.y * outerRadius.x
+ (outerRadius.y * outerRadius.y) / 4;
};
auto errOuterXY
= [&]() {
return outerRadius.x * outerRadius.x * (pos.y * pos.y + pos.y)
+ outerRadius.y * outerRadius.y * (pos.x - 1) * (pos.x - 1)
- outerRadius.y * outerRadius.y * outerRadius.x * outerRadius.x;
};
int errOuter = errOuterYX();
int xInner = innerRadius.x;
Point deltaInner = {
2 * innerRadius.y * innerRadius.y * xInner,
2 * innerRadius.x * innerRadius.x * pos.y
};
auto errInnerYX
= [&]() {
return innerRadius.x * innerRadius.x
- innerRadius.y * innerRadius.y * innerRadius.x
+ (innerRadius.y * innerRadius.y) / 4;
};
auto errInnerXY
= [&]() {
return innerRadius.x * innerRadius.x * (pos.y * pos.y + pos.y)
+ innerRadius.y * innerRadius.y * (xInner - 1) * (xInner - 1)
- innerRadius.y * innerRadius.y * innerRadius.x * innerRadius.x;
};
int errInner = errInnerYX();
// helpers (to reduce code duplication)
auto stepOuterYX
= [&]() {
++pos.y;
if (errOuter < 0) {
deltaOuter.y += 2 * outerRadius.x * outerRadius.x;
errOuter += deltaOuter.y + outerRadius.x * outerRadius.x;
} else {
--pos.x;
deltaOuter.y += 2 * outerRadius.x * outerRadius.x;
deltaOuter.x -= 2 * outerRadius.y * outerRadius.y;
errOuter += deltaOuter.y - deltaOuter.x + outerRadius.x * outerRadius.x;
}
};
auto stepOuterXY
= [&]() {
while (--pos.x > 0) {
if (errOuter > 0) {
deltaOuter.x -= 2 * outerRadius.y * outerRadius.y;
errOuter += outerRadius.y * outerRadius.y - deltaOuter.x;
} else {
++pos.y;
deltaOuter.y += 2 * outerRadius.x * outerRadius.x;
deltaOuter.x -= 2 * outerRadius.y * outerRadius.y;
errOuter += deltaOuter.y - deltaOuter.x + outerRadius.y * outerRadius.y;
break;
}
}
};
auto stepInnerYX
= [&]() {
if (errInner < 0) {
deltaInner.y += 2 * innerRadius.x * innerRadius.x;
errInner += deltaInner.y + innerRadius.x * innerRadius.x;
} else {
--xInner;
deltaInner.y += 2 * innerRadius.x * innerRadius.x;
deltaInner.x -= 2 * innerRadius.y * innerRadius.y;
errInner += deltaInner.y - deltaInner.x + innerRadius.x * innerRadius.x;
}
};
auto stepInnerXY
= [&]() {
while (--xInner >= 0) {
if (errInner > 0) {
deltaInner.x -= 2 * innerRadius.y * innerRadius.y;
errInner += innerRadius.y * innerRadius.y - deltaInner.x;
} else {
deltaInner.y += 2 * innerRadius.x * innerRadius.x;
deltaInner.x -= 2 * innerRadius.y * innerRadius.y;
errInner += deltaInner.y - deltaInner.x + innerRadius.y * innerRadius.y;
break;
}
}
};
// 1st phase
while (deltaOuter.y < deltaOuter.x && deltaInner.y < deltaInner.x) {
horiLine(Qt::blue, { center.x - pos.x, center.y + pos.y }, center.x - xInner);
horiLine(Qt::blue, { center.x + pos.x, center.y + pos.y }, center.x + xInner);
horiLine(Qt::blue, { center.x - pos.x, center.y - pos.y }, center.x - xInner);
horiLine(Qt::blue, { center.x + pos.x, center.y - pos.y }, center.x + xInner);
stepOuterYX();
stepInnerYX();
}
// 2nd phase
if (deltaOuter.y < deltaOuter.x) { // inner flipped
//errOuter = errOuterYX();
errInner = errInnerXY();
while (deltaOuter.y < deltaOuter.x && xInner >= 0) {
horiLine(Qt::green, { center.x - pos.x, center.y + pos.y }, center.x - xInner);
horiLine(Qt::green, { center.x + pos.x, center.y + pos.y }, center.x + xInner);
horiLine(Qt::green, { center.x - pos.x, center.y - pos.y }, center.x - xInner);
horiLine(Qt::green, { center.x + pos.x, center.y - pos.y }, center.x + xInner);
stepOuterYX();
stepInnerXY();
}
//errOuter = errOuterYX();
while (deltaOuter.y < deltaOuter.x) {
horiLine(Qt::red, { center.x - pos.x, center.y + pos.y }, center.x + pos.x);
horiLine(Qt::red, { center.x - pos.x, center.y - pos.y }, center.x + pos.x);
stepOuterYX();
}
} else { // outer flipped
errOuter = errOuterXY();
//errInner = errInnerYX();
while (deltaInner.y < deltaInner.x) {
horiLine(Qt::cyan, { center.x - pos.x, center.y + pos.y }, center.x - xInner);
horiLine(Qt::cyan, { center.x + pos.x, center.y + pos.y }, center.x + xInner);
horiLine(Qt::cyan, { center.x - pos.x, center.y - pos.y }, center.x - xInner);
horiLine(Qt::cyan, { center.x + pos.x, center.y - pos.y }, center.x + xInner);
stepOuterXY();
stepInnerYX();
}
//errOuter = errOuterXY();
}
// 3rd phase
errOuter = errOuterXY();
errInner = errInnerXY();
while (xInner >= 0) {
horiLine(Qt::yellow, { center.x - pos.x, center.y + pos.y }, center.x - xInner);
horiLine(Qt::yellow, { center.x + pos.x, center.y + pos.y }, center.x + xInner);
horiLine(Qt::yellow, { center.x - pos.x, center.y - pos.y }, center.x - xInner);
horiLine(Qt::yellow, { center.x + pos.x, center.y - pos.y }, center.x + xInner);
stepOuterXY();
stepInnerXY();
}
// 4th phase
//errOuter = errOuterXY();
while (pos.x >= 0) {
horiLine(Qt::magenta, { center.x - pos.x, center.y + pos.y }, center.x + pos.x);
horiLine(Qt::magenta, { center.x - pos.x, center.y - pos.y }, center.x + pos.x);
stepOuterXY();
}
}
void View::paintEvent(QPaintEvent*)
{
QPainter qPainter(this);
#if 0 // warm up
auto setPixel
= [&](const Color &color, const Point &point)
{
qPainter.setPen(color);
qPainter.drawPoint(point.x, point.y);
};
Point center = { 0.5 * width(), 0.5 * height() };
midpointEllipse(center, center, setPixel);
#else // my attempt to adapt it to thick ellipses
auto horiLine
= [&](const Color &color, const Point &pos0, int x1)
{
qPainter.setPen(color);
qPainter.drawLine(pos0.x, pos0.y, x1, pos0.y);
};
Point center = { 0.5 * width(), 0.5 * height() };
Point innerRadius = { 0.5 * center.x, 0.5 * center.y };
Point outerRadius = { 0.9 * center.x, 0.9 * center.y };
midpointEllipseThick(center, innerRadius, outerRadius, horiLine);
#endif // 0
}
int main(int argc, char **argv)
{
qDebug() << "Qt Version:" << QT_VERSION_STR;
QApplication app(argc, argv);
// setup UI
View qWin;
qWin.setWindowTitle(QString::fromUtf8("Draw Thick Ellipse"));
qWin.resize(320, 240);
qWin.show();
// runtime loop
return app.exec();
}
Compiled an tested in VS2017 (Qt 5.11.2):
I used colors to visualize the different combinations of regions and phases. This is intended to simply illustrate which part of code was responsible to render which part of ellipse.
I was a bit uncertain about the else case in // 2nd phase. I tested with
Point center = { 0.5 * width(), 0.5 * height() };
Point innerRadius = { 0.3 * center.x, 0.8 * center.y };
Point outerRadius = { 0.9 * center.x, 0.9 * center.y };
midpointEllipseThick(center, innerRadius, outerRadius, horiLine);
and got this:
Now, the // 1st phase stops due to failing deltaOuter.y < deltaOuter.x (and cyan areas appear).
OP complained about poor handling of edge cases like e.g. innerRadius = outerRadius;. I checked it with the following test set:
Point center = { 0.5 * width(), 0.5 * height() };
// test edge cases
{ Point outerRadius = { 0.9 * center.x, 0.9 * center.y };
Point innerRadius = { outerRadius.x, outerRadius.y };
Old::midpointEllipseThick(center, innerRadius, outerRadius, horiLine);
}
{ Point outerRadius = { 0.8 * center.x, 0.8 * center.y };
Point innerRadius = { outerRadius.x - 1, outerRadius.y };
Old::midpointEllipseThick(center, innerRadius, outerRadius, horiLine);
}
{ Point outerRadius = { 0.7 * center.x, 0.7 * center.y };
Point innerRadius = { outerRadius.x, outerRadius.y - 1 };
Old::midpointEllipseThick(center, innerRadius, outerRadius, horiLine);
}
{ Point outerRadius = { 0.6 * center.x, 0.6 * center.y };
Point innerRadius = { outerRadius.x - 1, outerRadius.y - 1 };
Old::midpointEllipseThick(center, innerRadius, outerRadius, horiLine);
}
{ Point outerRadius = { 0.5 * center.x, 0.5 * center.y };
Point innerRadius = { outerRadius.x - 2, outerRadius.y - 2 };
Old::midpointEllipseThick(center, innerRadius, outerRadius, horiLine);
}
changed Qt::yellow to Qt::darkgray (for a better contrast) and got this:
It becomes obvious that gaps appear when ∆xy →y+1 > xOuter - xInner.
To fix this issue, the ∆xy →y+1 has to be considered as well for the generation of span lines. To achieve this, I modified the iterations for ∆x ≥ ∆y (in the bottom part of function):
void midpointEllipseThick(
Point center,
Point innerRadius,
Point outerRadius,
std::function<void(const Color&, const Point&, int)> horiLine)
{
/// @todo validate/correct innerRadius and outerRadius
Point pos = { outerRadius.x, 0 };
Point deltaOuter = {
2 * outerRadius.y * outerRadius.y * pos.x,
2 * outerRadius.x * outerRadius.x * pos.y
};
auto errOuterYX
= [&]() {
return outerRadius.x * outerRadius.x
- outerRadius.y * outerRadius.y * outerRadius.x
+ (outerRadius.y * outerRadius.y) / 4;
};
auto errOuterXY
= [&]() {
return outerRadius.x * outerRadius.x * (pos.y * pos.y + pos.y)
+ outerRadius.y * outerRadius.y * (pos.x - 1) * (pos.x - 1)
- outerRadius.y * outerRadius.y * outerRadius.x * outerRadius.x;
};
int errOuter;
int xInner = innerRadius.x;
Point deltaInner = {
2 * innerRadius.y * innerRadius.y * xInner,
2 * innerRadius.x * innerRadius.x * pos.y
};
auto errInnerYX
= [&]() {
return innerRadius.x * innerRadius.x
- innerRadius.y * innerRadius.y * innerRadius.x
+ (innerRadius.y * innerRadius.y) / 4;
};
auto errInnerXY
= [&]() {
return innerRadius.x * innerRadius.x * (pos.y * pos.y + pos.y)
+ innerRadius.y * innerRadius.y * (xInner - 1) * (xInner - 1)
- innerRadius.y * innerRadius.y * innerRadius.x * innerRadius.x;
};
int errInner;
// helpers (to reduce code duplication)
auto stepOuterYX
= [&]() {
++pos.y;
if (errOuter < 0) {
deltaOuter.y += 2 * outerRadius.x * outerRadius.x;
errOuter += deltaOuter.y + outerRadius.x * outerRadius.x;
} else {
--pos.x;
deltaOuter.y += 2 * outerRadius.x * outerRadius.x;
deltaOuter.x -= 2 * outerRadius.y * outerRadius.y;
errOuter += deltaOuter.y - deltaOuter.x + outerRadius.x * outerRadius.x;
}
};
auto stepInnerYX
= [&]() {
if (errInner < 0) {
deltaInner.y += 2 * innerRadius.x * innerRadius.x;
errInner += deltaInner.y + innerRadius.x * innerRadius.x;
} else {
--xInner;
deltaInner.y += 2 * innerRadius.x * innerRadius.x;
deltaInner.x -= 2 * innerRadius.y * innerRadius.y;
errInner += deltaInner.y - deltaInner.x + innerRadius.x * innerRadius.x;
}
};
auto stepOuterXY
= [&]() {
while (--pos.x >= 0) {
if (errOuter > 0) {
deltaOuter.x -= 2 * outerRadius.y * outerRadius.y;
errOuter += outerRadius.y * outerRadius.y - deltaOuter.x;
} else {
++pos.y;
deltaOuter.y += 2 * outerRadius.x * outerRadius.x;
deltaOuter.x -= 2 * outerRadius.y * outerRadius.y;
errOuter += deltaOuter.y - deltaOuter.x + outerRadius.y * outerRadius.y;
break;
}
}
};
auto stepInnerXY
= [&]() {
while (--xInner >= 0) {
if (errInner > 0) {
deltaInner.x -= 2 * innerRadius.y * innerRadius.y;
errInner += innerRadius.y * innerRadius.y - deltaInner.x;
} else {
deltaInner.y += 2 * innerRadius.x * innerRadius.x;
deltaInner.x -= 2 * innerRadius.y * innerRadius.y;
errInner += deltaInner.y - deltaInner.x + innerRadius.y * innerRadius.y;
break;
}
}
};
auto min
= [](int x1, int x2, int x3) {
return std::min(std::min(x1, x2), x3);
};
// 1st phase
errOuter = errOuterYX(); // init error for delta y < delta x
errInner = errInnerYX(); // init error for delta y < delta x
while (deltaOuter.y < deltaOuter.x && deltaInner.y < deltaInner.x) {
horiLine(Qt::blue, { center.x - pos.x, center.y + pos.y }, center.x - xInner);
horiLine(Qt::blue, { center.x + pos.x, center.y + pos.y }, center.x + xInner);
horiLine(Qt::blue, { center.x - pos.x, center.y - pos.y }, center.x - xInner);
horiLine(Qt::blue, { center.x + pos.x, center.y - pos.y }, center.x + xInner);
stepOuterYX();
stepInnerYX();
}
// 2nd phase
if (deltaOuter.y < deltaOuter.x) { // inner flipped
//errOuter = errOuterYX(); // still delta y < delta x
errInner = errInnerXY(); // init error for delta x < delta y
while (deltaOuter.y < deltaOuter.x && xInner >= 0) {
horiLine(Qt::green, { center.x - pos.x, center.y + pos.y }, center.x - xInner);
horiLine(Qt::green, { center.x + pos.x, center.y + pos.y }, center.x + xInner);
horiLine(Qt::green, { center.x - pos.x, center.y - pos.y }, center.x - xInner);
horiLine(Qt::green, { center.x + pos.x, center.y - pos.y }, center.x + xInner);
stepOuterYX();
stepInnerXY();
}
//errOuter = errOuterYX(); // still delta y < delta x
while (deltaOuter.y < deltaOuter.x) {
horiLine(Qt::red, { center.x - pos.x, center.y + pos.y }, center.x + pos.x);
horiLine(Qt::red, { center.x - pos.x, center.y - pos.y }, center.x + pos.x);
stepOuterYX();
}
} else { // outer flipped
errOuter = errOuterXY(); // init error for delta x < delta y
//errInner = errInnerYX(); // still delta y < delta x
while (deltaInner.y < deltaInner.x) {
Point pos_ = pos;
stepOuterXY();
stepInnerYX();
int xInner_ = std::min(pos.x, xInner);
horiLine(Qt::cyan, { center.x - pos_.x, center.y + pos_.y }, center.x - xInner_);
horiLine(Qt::cyan, { center.x + pos_.x, center.y + pos_.y }, center.x + xInner_);
horiLine(Qt::cyan, { center.x - pos_.x, center.y - pos_.y }, center.x - xInner_);
horiLine(Qt::cyan, { center.x + pos_.x, center.y - pos_.y }, center.x + xInner_);
}
}
// 3rd phase
errOuter = errOuterXY(); // init error for delta x < delta y
errInner = errInnerXY(); // init error for delta x < delta y
while (xInner >= 0) {
Point pos_ = pos;
stepOuterXY();
int xInner_ = std::min(pos.x, xInner);
horiLine(Qt::darkGray, { center.x - pos_.x, center.y + pos_.y }, center.x - xInner_);
horiLine(Qt::darkGray, { center.x + pos_.x, center.y + pos_.y }, center.x + xInner_);
horiLine(Qt::darkGray, { center.x - pos_.x, center.y - pos_.y }, center.x - xInner_);
horiLine(Qt::darkGray, { center.x + pos_.x, center.y - pos_.y }, center.x + xInner_);
stepInnerXY();
}
// 4th phase
//errOuter = errOuterXY(); // still delta x < delta y
while (pos.x >= 0) {
horiLine(Qt::magenta, { center.x - pos.x, center.y + pos.y }, center.x + pos.x + 1);
horiLine(Qt::magenta, { center.x - pos.x, center.y - pos.y }, center.x + pos.x + 1);
stepOuterXY();
}
}
The result looks not that bad:
The gaps are removed.
I realized that there is still the other complained issue about off-by-one error:
The thickness at the top and bottom part of the ellipse seems to be one pixel too small.
Hmmm… That's a question of definition. Whenever a range has to be given, there has to be said whether start and end are (each) inclusive or exclusive. (Compare e.g. with iterator ranges in standard containers – start → inclusive, end → exclusive.)
The Qt doc. dedicates a whole extra chapter to this topic Coordinate System.
What I have to admit: My current algorithm handles this different for horizontal and vertical direction which I would consider as “ugliness”. IMHO, the easiest fix is to make it consistent horizontally and vertically. Afterwards the doc. might be adjusted respectively.
Employee: “Boss! Our recently produced buckets have a hole and lose water.”
Boss: “Good to know. We should mention that in the manual.”
Thus, I fixed the horizontal border size by tweaking the horiLine helper lambda:
auto horiLine
= [&](const Color &color, const Point &pos0, int x1)
{
qPainter.setPen(color);
if (x1 != pos0.x) x1 += x1 < pos0.x ? +1 : -1;
qPainter.drawLine(pos0.x, pos0.y, x1, pos0.y);
};
Now, I consider the result, at least, as consistent (if not satisfying):
The innerRadius appears now as exclusive. If this is not intended, a resp. pre-adjustment of the parameters at the begin of the midpointEllipseThick() could be applied.
