Я должен признать, что я твердо верю, что в круге больше симметрии, чем в эллипсе.Если круг может быть зеркально отражен на любой оси, проходящей через центр, для эллипса это возможно только с осями x и y в целом.Следовательно, я считаю, что midPointCircleThick() не может быть адаптирован для эллипса.
Итак, я начал свою реализацию с midpointEllipse(), предоставленным ОП.
Это были мои основные мысли:
ИМХО, алгоритм линии Брезенхема является источником алгоритма окружности средней точки , а также алгоритма эллипса средней точки.Это может помочь понять магию ошибок / дельта, которая используется.Для линии это намного проще, но следует той же идее, адаптированной к x² / a² + y² / b² = 1 ( уравнение эллипса ).
С началом координат в центреэллипса midpointEllipse() визуализирует все 4 квадранта одновременно (используя симметрию).Следовательно, только кривая в одном квадранте должна быть эффективно вычислена.Кривая в этой области монотонна.
midpointEllipse() имеет две области:
- Начиная с точек на оси x, ∆y> ∆x доCross-Even.
- Впоследствии, ∆x> ∆y.
Моя концепция состояла в том, чтобы адаптировать midpointEllipse() таким образом, чтобы код был "«дублировано» для управления двумя точками (одна для внутренней границы, одна для внешней) с идентичными координатами y для рисования горизонтальных линий (линий пролета).
Моим первым наблюдением было то, что новый алгоритм должен управлять конечной фазой (для innerRadius.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):
Я использовал цвета для визуализации различных комбинаций областей и фаз.Это предназначено просто для иллюстрации того, какая часть кода была ответственна за отображение какой части эллипса.
Я был немного неуверен в случае else в // 2nd phase.Я протестировал с
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(и появляются голубые области).
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();
}
}
Результат выглядит неплохо:
Устранены пробелы.
Я понял, что есть еще одна проблема, связанная с ошибкой "один на один":
Толщинав верхней и нижней части эллипса кажется, что один пиксель слишком мал.
Хммм ... Это вопрос определения.Всякий раз, когда должен быть указан диапазон, должно быть сказано, являются ли начало и конец (каждый) включающими или исключающими.(Сравните, например, с диапазонами итераторов в стандартных контейнерах - начало → включительно, конец → эксклюзив.)
Документ Qt.посвящает целую дополнительную главу этой теме Система координат .
Что я должен признать: мой текущий алгоритм обрабатывает это по-разному для горизонтального и вертикального направления, которое я бы рассматривал как "безобразие". ИМХО, самое простое решение - сделать его согласованным по горизонтали и вертикали. После док. может быть скорректирована соответственно.
Сотрудник: & ldquo; Босс! Наши недавно изготовленные ведра имеют отверстие и теряют воду. & Rdquo;
Босс: & ldquo; Полезно знать. Мы должны упомянуть об этом в руководстве. & Rdquo;
Таким образом, я установил размер горизонтальной границы, настроив вспомогательную лямбду horiLine:
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().