Растеризация эллипса

Question

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

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

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

Чтобы clearify, что я имею в виду, я недавно был один подобный вопрос этот решен здесь: Special polygonial for loop in two dimensional array

/Ник

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 просто применяет матрицу вращения 2х2 для й и у и помещает результат в newX, Newy.

Answer 2

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

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