Растрирование эллипса

Question

Существует ли эффективный алгоритм для нахождения признаков пикселей в общем эллипсе?

По сути, я хочу найти индикаторы в двумерном массиве, который соответствует параметризованному эллипсу, который охватывает «двумерную поверхность» возможных индикаторов массива. Эту проблему, как и в моем первом вопросе выше, можно сравнить с растеризацией эллипса.

Я нашел несколько алгоритмов Scan Line, которые делают то, что я хочу для выровненных по оси эллипсов, но теперь мне интересно, есть ли какие-нибудь похожие алгоритмы для эллипсов, которые перекошены и повернуты. Должно быть, так как векторной графике SW удается заполнить эллипсы, которые перекошены и / или повернуты.

Чтобы прояснить, что я имею в виду, недавно у меня был один подобный вопрос, решенный здесь: Специальный многоугольник для цикла в двумерном массиве

/ Ник

Answer 1

Вы можете использовать алгоритмы, которые вы нашли для растеризации эллипса, и просто применить вращение или наклонное преобразование к координатам, прежде чем проверять, находятся ли они внутри или вне эллипса. Например, если вы хотите проверить эллипс, повернутый на 45 градусов, вы можете сделать что-то вроде этого:

for (x = 0; x < maxX; x++)
{
    for (y = 0; y < maxY; y++)
    {
        double newX, newY;
        Transform (x, y, rotationMatrix, &newX, &newY);
        if (PointInEllipse (newX, newY, ellipse))
        {
            ...do whatever here....
        }
    }
}

Где Transform просто применяет матрицу вращения 2x2 к x и y и помещает результат в newX, newY.

Answer 2

Я бы порекомендовал триангулировать ваш эллипс и использовать стандартные подпрограммы заполнения треугольника, шансы хороши, как это делают большинство графических API, поскольку OpenGL и DirectX, как правило, способны рисовать треугольники только в конце дня.

Простая триангуляция эллипса выглядит как пицца, за исключением масштаба. Если вам нужно более высокое качество, просто увеличьте количество ломтиков в пицце.