中点粗椭圆绘制算法 [英] Midpoint thick ellipse drawing algorithm

查看：90
本文介绍了中点粗椭圆绘制算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我真的很接近让粗椭圆算法起作用，但是我有点麻烦.我从此处采用了中点粗圆算法，并从

这是图片代码(只是一个占位符):

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++;
  }
}

这是中点粗圆算法:

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;
      }
    }
  }
}

这是中点椭圆算法:

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;
    }
  }
}

我试图将两种算法结合在一起，这就是我到目前为止所掌握的.我留下了一些不确定代码的?.我很清楚这里的混乱和重复.我只想让它正常工作，然后再担心代码是什么样子.

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;
      }
    // }
  }
}

这是一个带有innerRadius = 22; outerRadius = 24的粗圆圈:

这是radius = {32, 24}的椭圆:

(假设是)带有innerRadius = {30, 22}; outerRadius = {32, 24}的粗椭圆:

我很近，但还没到那儿.谁能比我更了解这些东西?

解决方案

我必须承认，我坚信圆形比椭圆形对称得多.如果圆可以在通过中心的任何轴上镜像，对于椭圆形，通常只有在x和y轴上才有可能.因此，我相信midPointCircleThick()不能适应椭圆.

因此，我从OP提供的midpointEllipse()开始实施.

这些是我的基本想法:

  • 恕我直言， Bresenham Line算法是中点圆算法以及中点椭圆算法.这可能有助于理解所使用的错误/增量魔术.对于一行来说，它要简单得多，但遵循适用于x²/a²+y²/b²= 1(椭圆方程).

  • 以椭圆的原点为起点，midpointEllipse()同时渲染所有四个象限(利用对称性).因此，仅必须有效地计算一个象限中的曲线.曲线在该区域是单调的.

  • midpointEllipse()具有两个区域:

    1. 从x轴上的点开始，∆ y> ∆ x直到收支平衡.
    2. 此后，∆ x> ∆ y.

我的想法是采用这种方式适应midpointEllipse()，即代码被复制"以管理具有相同y坐标的两个点(一个用于内部边界，一个用于外部)以绘制水平线(跨度线). /p>

我的第一个观察结果是，新算法必须管理最后一个阶段(对于innerRadius.y< y≤ outerRadius.y)，其中只需要考虑外边界上的点.

请记住，原始算法有两个区域，现在有两个区域用于外边界，两个区域用于内边界，以及上面提到的两个阶段.这允许多种组合. (要对此进行管理是我实施过程中的主要工作.)

示例实现(基于Qt具有简单的可视化效果):

#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();
}

编译了VS2017(Qt 5.11.2)中的测试:

我用颜色来形象化区域和相位的不同组合.这只是为了简单说明代码的哪一部分负责呈现椭圆的哪一部分.

对于// 2nd phase中的else情况，我有点不确定.我测试过

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

得到了:

现在，由于deltaOuter.y < deltaOuter.x失败，// 1st phase停止了(并且出现青色区域).

OP抱怨对诸如innerRadius = outerRadius;.我使用以下测试集进行了检查:

  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);
  }

将Qt::yellow更改为Qt::darkgray(以获得更好的对比)，并得到以下信息:

当∆ x y→ y + 1 > x 外部-x 内部.

要解决此问题，在生成跨度线时也必须考虑∆ x y→ y + 1 .为此，我修改了∆ x≥的迭代. ∆ 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;
  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();
  }
}

结果看起来还不错:

间隙被消除.

我意识到，还有一个抱怨过的错误:

椭圆的顶部和底部的厚度似乎太小了一个像素.

Hmmm…这是一个定义问题.每当必须给出一个范围时，就必须说出开始和结束是(每个)包容性还是排他性. (例如，与标准容器中的迭代器范围进行比较-开始→包含(包括)，结束→排除).

Qt文档.为此主题坐标系 专门介绍了整整一章.

我必须承认的是:我目前的算法在水平和垂直方向上都处理不同的问题，我认为这是丑陋"的.恕我直言，最简单的解决方法是使其在水平和垂直方向上保持一致.之后的文件.可能会分别进行调整.

员工:老板！我们最近生产的水桶有一个洞，而且会失水.
老板:很高兴知道.我们应该在手册中提到这一点.

因此，我通过调整horiLine辅助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);
    };

现在，我认为结果至少是一致的(如果不令人满意):

innerRadius现在显示为排他性.如果这不是故意的，则分别.可以在midpointEllipseThick()开始时对参数进行预调整.

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:

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

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

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

解决方案

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

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.

这篇关于中点粗椭圆绘制算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
C/C++开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆