Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Midpoint thick ellipse drawing algorithm

I'm really close to getting a thick ellipse algorithm working but I'm having a bit of trouble. I've taken the midpoint thick circle algorithm from here, and the midpoint ellipse algorithm from here, and I'm trying to combine them together to get the midpoint thick ellipse algorithm. I'm doing this because Googling "midpoint thick ellipse algorithm" didn't show what I'm looking for. The output from my attempt resembles a thick circle (images are at the bottom of the post).

This is the image code (just a placeholder):

struct Point {
  int x, y;
};

struct Image {};
using Color = int;

void setPixel(Image &, Color, Point) {
  // ...
}

void horiLine(Image &image, Color color, Point first, int last) {
  while (first.x <= last) {
    setPixel(image, color, first);
    first.x++;
  }
}

void vertLine(Image &image, Color color, Point first, int last) {
  while (first.y <= last) {
    setPixel(image, color, first);
    first.y++;
  }
}

Here's the midpoint thick circle algorithm:

void midpointCircleThick(
  Image &image,
  Color color,
  Point center,
  int innerRadius,
  int outerRadius
) {
  int innerX = innerRadius;
  int outerX = outerRadius;
  int posY = 0;
  int innerErr = 1 - innerRadius;
  int outerErr = 1 - outerRadius;

  while (outerX >= posY) {
    horiLine(image, color, {center.x + innerX, center.y + posY},   center.x + outerX);
    vertLine(image, color, {center.x + posY,   center.y + innerX}, center.y + outerX);
    horiLine(image, color, {center.x - outerX, center.y + posY},   center.x - innerX);
    vertLine(image, color, {center.x - posY,   center.y + innerX}, center.y + outerX);

    horiLine(image, color, {center.x - outerX, center.y - posY},   center.x - innerX);
    vertLine(image, color, {center.x - posY,   center.y - outerX}, center.y - innerX);
    horiLine(image, color, {center.x + innerX, center.y - posY},   center.x + outerX);
    vertLine(image, color, {center.x + posY,   center.y - outerX}, center.y - innerX);

    posY++;

    if (outerErr < 0) {
      outerErr += 2 * posY + 1;
    } else {
      outerX--;
      outerErr += 2 * (posY - outerX) + 1;
    }

    if (posY > innerRadius) {
      innerX = posY;
    } else {
      if (innerErr < 0) {
        innerErr += 2 * posY + 1;
      } else {
        innerX--;
        innerErr += 2 * (posY - innerX) + 1;
      }
    }
  }
}

Here's the midpoint ellipse algorithm:

void midpointEllipse(
  Image &image,
  Color color,
  Point center,
  Point radius
) {
  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(image, color, {center.x + pos.x, center.y + pos.y});
    setPixel(image, color, {center.x + pos.x, center.y - pos.y});
    setPixel(image, color, {center.x - pos.x, center.y + pos.y});
    setPixel(image, color, {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(image, color, {center.x + pos.x, center.y + pos.y});
    setPixel(image, color, {center.x + pos.x, center.y - pos.y});
    setPixel(image, color, {center.x - pos.x, center.y + pos.y});
    setPixel(image, color, {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;
    }
  }
}

I attempted to combine the two algorithms and this is what I have so far. I left some ? where I'm not sure about the code. I am well aware of the messiness and duplication here. I just want to get it working before I worry about what the code looks like.

void midpointEllipseThick(
  Image &image,
  Color color,
  Point center,
  Point innerRadius,
  Point outerRadius
) {
  int innerX = innerRadius.x;
  int outerX = outerRadius.x;
  int posY = 0;
  Point innerDelta = {
    2 * innerRadius.y * innerRadius.y * innerX,
    2 * innerRadius.x * innerRadius.x * posY
  };
  Point outerDelta = {
    2 * outerRadius.y * outerRadius.y * outerX,
    2 * outerRadius.x * outerRadius.x * posY
  };
  int innerErr = innerRadius.x * innerRadius.x
               - innerRadius.y * innerRadius.y * innerRadius.x
               + (innerRadius.y * innerRadius.y) / 4;
  int outerErr = outerRadius.x * outerRadius.x
               - outerRadius.y * outerRadius.y * outerRadius.x
               + (outerRadius.y * outerRadius.y) / 4;

  while (outerDelta.y < outerDelta.x) { // ?
    horiLine(image, color, {center.x + innerX, center.y + posY},   center.x + outerX);
    vertLine(image, color, {center.x + posY,   center.y + innerX}, center.y + outerX);
    horiLine(image, color, {center.x - outerX, center.y + posY},   center.x - innerX);
    vertLine(image, color, {center.x - posY,   center.y + innerX}, center.y + outerX);

    horiLine(image, color, {center.x - outerX, center.y - posY},   center.x - innerX);
    vertLine(image, color, {center.x - posY,   center.y - outerX}, center.y - innerX);
    horiLine(image, color, {center.x + innerX, center.y - posY},   center.x + outerX);
    vertLine(image, color, {center.x + posY,   center.y - outerX}, center.y - innerX);

    posY++;

    if (outerErr < 0) {
      outerDelta.y += 2 * outerRadius.x * outerRadius.x;
      outerErr += outerDelta.y + outerRadius.x * outerRadius.x;
    } else {
      outerX--;
      outerDelta.y += 2 * outerRadius.x * outerRadius.x;
      outerDelta.x -= 2 * outerRadius.y * outerRadius.y;
      outerErr += outerDelta.y - outerDelta.x + outerRadius.x * outerRadius.x;
    }

    // ?
    // if (posY > innerRadius.y) {
    //   innerX = posY;
    // } else {
      if (innerErr < 0) {
        innerDelta.y += 2 * innerRadius.x * innerRadius.x;
        innerErr += innerDelta.y + innerRadius.x * innerRadius.x;
      } else {
        innerX--;
        innerDelta.y += 2 * innerRadius.x * innerRadius.x;
        innerDelta.x -= 2 * innerRadius.y * innerRadius.y;
        innerErr += innerDelta.y - innerDelta.x + innerRadius.x * innerRadius.x;
      }
    // }
  }

  innerErr = innerRadius.x * innerRadius.x * (posY * posY + posY)
           + innerRadius.y * innerRadius.y * (innerX - 1) * (innerX - 1)
           - innerRadius.y * innerRadius.y * innerRadius.x * innerRadius.x;
  outerErr = outerRadius.x * outerRadius.x * (posY * posY + posY)
           + outerRadius.y * outerRadius.y * (outerX - 1) * (outerX - 1)
           - outerRadius.y * outerRadius.y * outerRadius.x * outerRadius.x;

  while (outerX >= 0) { // ?
    horiLine(image, color, {center.x + innerX, center.y + posY},   center.x + outerX);
    vertLine(image, color, {center.x + posY,   center.y + innerX}, center.y + outerX);
    horiLine(image, color, {center.x - outerX, center.y + posY},   center.x - innerX);
    vertLine(image, color, {center.x - posY,   center.y + innerX}, center.y + outerX);

    horiLine(image, color, {center.x - outerX, center.y - posY},   center.x - innerX);
    vertLine(image, color, {center.x - posY,   center.y - outerX}, center.y - innerX);
    horiLine(image, color, {center.x + innerX, center.y - posY},   center.x + outerX);
    vertLine(image, color, {center.x + posY,   center.y - outerX}, center.y - innerX);

    outerX--; // ?
    innerX--;

    if (outerErr > 0) {
      outerDelta.x -= 2 * outerRadius.y * outerRadius.y;
      outerErr += outerRadius.y * outerRadius.y - outerDelta.x;
    } else {
      posY++;
      outerDelta.y += 2 * outerRadius.x * outerRadius.x;
      outerDelta.x -= 2 * outerRadius.y * outerRadius.y;
      outerErr += outerDelta.y - outerDelta.x + outerRadius.y * outerRadius.y;
    }

    // ?
    // if (innerX < -innerRadius.x) {

    // } else {
      if (outerErr > 0) {
        innerDelta.x -= 2 * innerRadius.y * innerRadius.y;
        innerErr += innerRadius.y * innerRadius.y - innerDelta.x;
      } else {
        posY++;
        innerDelta.y += 2 * innerRadius.x * innerRadius.x;
        innerDelta.x -= 2 * innerRadius.y * innerRadius.y;
        outerErr += innerDelta.y - innerDelta.x + innerRadius.y * innerRadius.y;
      }
    // }
  }
}

Here's a thick circle with innerRadius = 22; outerRadius = 24:

Thick circle

Here's an ellipse with radius = {32, 24}:

Ellipse

Here's (what's supposed to be) a thick ellipse with innerRadius = {30, 22}; outerRadius = {32, 24}:

Thick ellipse

I'm close but not quite there. Could someone who knows more about this stuff than I do get me over the finish line?

like image 693
Indiana Kernick Avatar asked May 04 '19 07:05

Indiana Kernick


People also ask

What is midpoint ellipse drawing algorithm?

Midpoint ellipse algorithm plots(finds) points of an ellipse on the first quadrant by dividing the quadrant into two regions. Each point(x, y) is then projected into other three quadrants (-x, y), (x, -y), (-x, -y) i.e. it uses 4-way symmetry. Function of ellipse: fellipse(x, y)=ry2x2+rx2y2-rx2ry2.

How does the midpoint circle algorithm work?

The mid-point circle drawing algorithm is an algorithm used to determine the points needed for rasterizing a circle. We use the mid-point algorithm to calculate all the perimeter points of the circle in the first octant and then print them along with their mirror points in the other octants.

What are the advantages of midpoint circle drawing algorithm?

Advantages of Mid Point Circle Drawing Algorithm-It is a powerful and efficient algorithm. The entire algorithm is based on the simple equation of circle X2 + Y2 = R2. It is easy to implement from the programmer's perspective. This algorithm is used to generate curves on raster displays.


1 Answers

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:

    1. Starting at points on x axis, ∆y > ∆x until cross-even.
    2. 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):

Snapshot of testQThickEllipse Snapshot of testQThickEllipse (with different width/height) Snapshot of testQThickEllipse (with yet another width/height)

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:

Snapshot of testQThickEllipse (with different arguments)

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:

Snapshot of testQThickEllipse (edge tests)

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:

Snapshot of testQThickEllipse (fixed for edge tests)

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):

Snapshot of testQThickEllipse (fixed for border width)

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.

like image 179
Scheff's Cat Avatar answered Sep 28 '22 06:09

Scheff's Cat