中点厚椭圆绘制算法

Question

我正在尝试让一个厚的椭圆算法正常运作，但我遇到了一些问题。我从这里获取了中点厚圆算法，以及从这里获取了中点椭圆算法，我试图将它们结合起来得到中点厚椭圆算法。我这样做是因为谷歌搜索“中点厚椭圆算法”没有给出我要找的结果。我的尝试输出类似于一个厚圆形（图片在帖子底部）。

这是图片代码（只是一个占位符）：

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

这里有一个内径为22、外径为24的粗圆：

这里有一个半径为{32, 24}的椭圆：

这里是一个（应该是）内径为{30, 22}、外径为{32, 24}的粗椭圆：

我已经接近成功，但还差一点。有没有比我更了解这方面的人能帮我完成最后的工作呢？

- Indiana Kernick

---

@Scheff 我也在使用Qt进行测试！你只需要为“Image”和“Color”创建类型别名，然后实现“setPixel”调用“QImage::setPixel”即可。 - Indiana Kernick

画一个椭圆，然后再画一些类似但稍微小一点的椭圆来创建厚度，这个怎么样？ - גלעד ברקן

@גלעדברקן 这样做可能会留下空洞。而且它不如绘制水平和垂直线条高效。 - Indiana Kernick

Answer 1

我必须承认，我坚信圆形比椭圆更具对称性。一个圆可以在通过中心的任何轴上镜像，但对于一个椭圆来说，只有x和y轴是普遍可行的。因此，我认为midPointCircleThick()不能用于椭圆。

因此，我从OP提供的midpointEllipse()开始实现。

以下是我的基本想法：

• 我认为Bresenham线算法是Midpoint Circle算法以及Midpoint Ellipse算法的起源。这可能有助于理解使用的错误/增量魔术。对于一条线来说，这要简单得多，但遵循了适应于x²/a² + y²/b² = 1（椭圆方程）的相同思路。

• 以椭圆中心为原点，midpointEllipse()同时渲染所有4个象限（利用对称性）。因此，只需要有效地计算一个象限内的曲线。曲线在这个区域是单调的。

• midpointEllipse()有两个区域：

  1. 从x轴上的点开始，∆y > ∆x，直到交叉-even。
  2. 之后，∆x > ∆y。

我的概念是将midpointEllipse()改编为以相同y坐标管理两个点（一个内部边界，一个外部边界）来绘制水平线（跨度线）。

我的第一个观察结果是新算法必须处理一个最终阶段（对于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();
}

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

然后看到了这个：

现在，// 1st phase由于失败的deltaOuter.y < deltaOuter.x而停止（并出现了青色区域）。

---

问题提出者抱怨处理边缘情况（例如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_Outer - x_Inner 时，出现了间隙。

要解决这个问题，需要考虑到生成跨越线所需的 ∆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();
  }
}

结果看起来还不错：

空隙已经去除。

我发现还有另一个问题，即偏差为一的问题：

椭圆顶部和底部的厚度似乎少了一个像素。

嗯...这是个定义问题。每当需要给出范围时，必须说明开始和结束是否包含在内。 （例如与标准容器中的迭代器范围进行比较 - 开始->包括，结束->排除。）

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()开始时可以应用相应的参数预调整。

- Scheff's Cat

---

这看起来很有前途，但是我的时区已经很晚了，所以我得明天再试一下。 - Indiana Kernick

@Kerndog73 哦，澳大利亚。我明白了...;-) - Scheff's Cat

这看起来非常不错，但我认为可能有一个偏移错误。椭圆形顶部和底部的厚度似乎小了一个像素。尝试绘制 outerRadius == innerRadius 的图形，你就会明白我的意思。蓝色和绿色部分的厚度似乎没问题，但品红色和黄色部分有点薄。实话实说，我不知道这段代码是如何工作的，所以无法自行修复它！ - Indiana Kernick

此外，我对那些被注释掉的错误计算(//errOuter = errOuterXY();)感到担忧。你能再次确认它们是否不需要并将其删除吗？顺便说一下，我真的很喜欢这个程序只绘制水平线条。这使得它在绘制非常粗的椭圆时速度相当快。除了这两点之外，我对你所做的一切都非常满意！如果你解决了这些问题，我甚至可能会开一个赏金，并奖励你一些额外的网络积分！ - Indiana Kernick

让我们在聊天中继续这个讨论。 - Scheff's Cat

Answer 2

你面临的问题是，厚度恒定的椭圆轮廓不是椭圆，而是高阶曲线！在两个椭圆之间填充只能给出近似值。

在图片上，红色曲线对应恒定厚度。

一个正确的解决方案是使用粗笔画图，即通过让其中心遵循椭圆曲线，用标准算法扫描所需半径的圆盘。

然而，这是一种低效的过程，因为连续的圆盘会重叠，像素会被重复绘制。一种解决方案是考虑到由于八个方向的位移而覆盖圆盘的新像素。这些像素集必须提前计算并制表，给定半径。

要建立表格，请用一个圆盘绘制它，再用按八个主方向之一偏移一个像素的圆盘来擦除它；对所有方向重复此操作。

- user1196549

---

那可能是一个可行的解决方案。在直线上绘制1像素描边圆只比QPainter绘制粗线略慢一点。但是移动对角线时，1像素圆确实会留下间隙。位图表听起来是个有趣的想法。我对性能持怀疑态度，因为你必须迭代位图中的每个像素，并且大多数像素都未设置。虽然我没有尝试过。我仍将奖励授予Scheff，因为他付出了大量的努力。不过我可能会考虑更改接受的答案。 - Indiana Kernick

我可以进行一些位操作来使位图循环体无分支。但我仍然持怀疑态度，因为你仍然需要查看许多不需要更改的像素。 - Indiana Kernick

当然，你要存储一个要设置的像素列表！ - user1196549

@Kerndog73：还要注意的是，该方法适用于任何连续曲线和任何画笔形状。 - user1196549

@Kerndog73：这是为了避免绘制磁盘，仅轮廓就足够了。 - user1196549