Вот здесь

Автор: Demiurg
Дата: 29.11.02

просили этот код.
Выкладываю:

#ifndef _FIGURES_H_
#define _FIGURES_H_

// FIGURES:

// это многомерная точка. Раньше я юзал обычный std::vector<>, но потом меня задолбало помнить, что p[0] - это иксовая
// координата, p[1] - игрековая и т.д.  :)
template<class T>
struct point
{
    std::vector<T> p;

    point(){}
    point(size_t n): p(n) {}
    point(T x, T y): p(2) {p[0]=x; p[1]=y;}
    point(std::vector<T> P): p(P) {}
    point(const point& pt): p(pt.p) {}
    ~point(){}

    point& operator= (const point& pt){p=pt.p; return *this;}
    T& x() {return p[0];}
    const T& x() const {return p[0];}
    T& y() 
    {
        assert(p.size()>1);
        return p[1];
    }
    const T& y() const
    {
        assert(p.size()>1);
        return p[1];
    }
    T& z() 
    {
        assert(p.size()>2);
        return p[2];
    }
    const T& z() const
    {
        assert(p.size()>2);
        return p[2];
    }
};

// ну это - так, для удобства
typedef point<size_t> PixelPoint;
typedef point<double> DoublePoint;
typedef point<float> FloatPoint;

// в общем, фигура будет массивом этих структур. Каждая линия (отрезок) задается точкой в которой она начинается,
// длиной линии. Все линии горизонтальные (меняется только координата x, начало отрезка - слева)
struct figure_line
{
    PixelPoint start;
    size_t length;
    figure_line(){}
    figure_line(size_t ndims):start(ndims, 0), length(1){}
    figure_line(const figure_line& f): start(f.start), length(f.length){}
    ~figure_line(){}
};

typedef std::vector<figure_line> figure;


// Вот оно! По полигону (массиву вершин с координатами возможно вещественного типа) строит массив линий.
// работает оно так: для каждой горизонтальной прямой, которая сечет полигон, считает пересечения со сторонами полигона.
template<class T>
figure polygon(const std::vector<point<T> >& poly)
{
    size_t n=poly.size();
#ifndef NDEBUG
    {
        for(size_t i=0;i<n;i++)
            assert(poly[i].p.size()==2);
    }
#endif
    double ymin=poly[0].y(), ymax=poly[0].y();
    size_t i;
    for(i=1;i<n;i++)
        if(ymin>poly[i].y())
            ymin=poly[i].y();
        else if(ymax<poly[i].y())
            ymax=poly[i].y();

    std::vector<DoublePoint> P(poly.size());
    for(i=0;i<n;i++)
    {
        P[i]=DoublePoint(poly[i].x(), poly[i].y());
    }
    if(P[0].x()!=P[n-1].x() || P[0].y()!=P[n-1].y())
        P.push_back(P[0]);

    if(ymin<1) 
        ymin=0;
    else
        ymin-=1;

    if(ymax<0)
        return figure();
    else
        ymax+=1;

    std::vector<double> k(n), h(n);
    for(i=0;i<n;i++)
    {
        k[i]=(P[i+1].x()-P[i].x())/(P[i+1].y()-P[i].y());
        h[i]=P[i].x()-P[i].y()*k[i];
    }
    figure res;
    figure_line l(2);
    res.reserve(n*int(ymax-ymin+2));
    for(size_t y=(size_t)floor(ymin), yend=(size_t)ceil(ymax);y<yend;y++)
    {
        std::vector<int> cross;
        cross.reserve(n);
        for(i=0;i<n;i++)
            if(P[i].y()>y && P[i+1].y()<y || P[i].y()<y && P[i+1].y()>y)
                cross.push_back((int)floor(h[i]+y*k[i]+0.5));
            else if(P[i].y()==y)
                cross.push_back((int)floor(P[i].x()+0.5));

        std::sort(cross.begin(), cross.end());

        size_t m=cross.size();

        l.start.y()=y;
        for(i=0;i<m-m%2;i+=2)
            if(cross[i+1]>=0)
            {
                l.start.x()=cross[i]<0 ? 0 : cross[i];
                l.length=cross[i+1]+1-l.start.x();
                res.push_back(l);
            }
        if(m>0)
            if(m%2!=0 && cross[m-1]>=0)
            {
                l.start.x()=cross[m-1];
                l.length=1;
                res.push_back(l);
            }
    }
    return res;
}

// делает то же самое, но для эллипса
figure ellipse(double x, double y, double a, double b)
{
    assert(a>0 && b>0);
    size_t n=size_t(b*2+1.5);
    figure res;
    res.reserve(n);
    size_t y0=0;
    if(y-b+0.5>=0)
        y0=size_t(y-b+0.5);
    else
        n-=size_t(b-y+0.5);

    double b2_1=1/(b*b);
    figure_line l(2);
    for(size_t i=0;i<n;i++)
    {
        l.start.y()=y0+i;
        double h=float(y0)+i-y;
        double w=sqrt(1.-h*h*b2_1)*a;
        if(finite(w))
            if(x+w+1.5>=0)
            {
                l.start.x()=( x-w+0.5 >=0 ? size_t(x-w+0.5) : 0);
                l.length=size_t(x+w+1.5)-l.start.x();
                if(l.length>0)
                    res.push_back(l);
            }
    }
    return res;
}


// чтобы побыстрее работать с figure, ее нужно вытянуть в линейный массив.
// ну т.е. N-мерные координаты пересчитываются в 1-мерные

typedef std::pair<size_t, size_t> split_line;

template<class Image>
std::vector<split_line> lining(const figure& fig, const Image& img)
// второй параметр - N-мерный массив
{
    assert(fig.size()>0);
#ifndef NDEBUG
    {
        PixelPoint min, max;
        circumscribe(fig, min, max);
        img.index(max.p);
    }
#endif // DEBUG
    std::vector<split_line> res(fig.size());
    PixelPoint pt(img.dims().size());
    for(size_t i=0;i<fig.size();i++)
    {
        assert(img.dims().size()>=fig[i].start.p.size());
        const PixelPoint& pt0=fig[i].start;
        std::fill(pt.p.begin(), pt.p.end(), 0);
        std::copy(pt0.p.begin(), pt0.p.end(), pt.p.begin());
        res[i].first=img.index(pt.p);
        res[i].second=fig[i].length;
#ifndef NDEBUG
        pt.x()+=fig[i].length-1;
        img.index(pt.p);
#endif
    }
    return res;
}


// эта штука описывает вокруг фигуры паралелепипед.
// Ну, т.е. считает наибольшие и наименьшие значения координат :))
void circumscribe(const figure& fig, PixelPoint& minbounds, PixelPoint& maxbounds)
{
    assert(fig.size()>0);
    size_t n=fig[0].start.p.size();
#ifndef NDEBUG
    {
        for(size_t i=1;i<fig.size();i++)
            assert(fig[i].start.p.size()==n);
    }
#endif // DEBUG
    minbounds.p.resize(n);
    maxbounds.p.resize(n);
    std::copy(fig[0].start.p.begin(), fig[0].start.p.end(), minbounds.p.begin());
    std::copy(fig[0].start.p.begin(), fig[0].start.p.end(), maxbounds.p.begin());
    maxbounds.p[0]+=fig[0].length-1;
    for(size_t i=1;i<fig.size();i++)
    {
        const figure_line& fl=fig[i];
        for(size_t j=0;j<n;j++)
        {
            size_t h=fl.start.p[j];
            if(minbounds.p[j]>h)
                minbounds.p[j]=h;
            if(j==0) h+=fl.length-1;
            if(maxbounds.p[j]<h)
                maxbounds.p[j]=h;
        }
    }
}

#endif

В качестве типа Image функции lining() надо использовать типы образованные от шаблона array<>, который я уже
выкладывал здесь

Автор: Atilla
Дата: 29.11.02

, либо чего-нибудь в этом роде.

Ну и как все это юзать:

IntegerArray d(2); d[0]=1000, d[1]=1000;
array<float> img(d, 0); // делаем картинку 1000х1000, заполняем нулями

figure fig=ellipse(10, 10, 10, 10); // "рисуем" круг радиусом 10, центром (10,10)
std::vector<split_line> l=lining(fig, img);

PixelPoint pt(10, 10);
for(;pt.y()<1000;pt.y()+=30)
   for(pt.x()=10;pt.x()<1000;pt.x()+=30)
   {
      size_t offset=img.index(pt.p); // считаем 1-мерный индекс точки pt
      for(size_t i=0;i<l.size();i++) // пробегаем по всем линиям
         for(size_t j=offset+l[i].first, jend=j+l[i].second;j<jend;j++) // по всем точкам линии
           img[j]=1; // в каждой точке круга - единица
   }

// и того, на выходе в картинке img единицами нарисованы круги радиусом 10 и с центрами в точках (10,10), (10,40) и т.д.

d[0]=500; d[1]=500;
array<float> img2(d, 0); // делаем другую картинку, поменьше

std::vector<DoublePoint> poly(3);
poly[0].x()=100, poly[0].y()=10;
poly[1].x()=300, poly[1].y()=400;
poly[2].x()=50, poly[2].y()=450;
fig=polygon(poly); // рисуем такой вот треугольник

l=lining(fig, img);
std::vector<split_line> l2=lining(fig, img2);

// у меня еще был специально обученный класс типа slice_array, только с итераторами, но он ща с этим
// кодом не совместим :( 

for(size_t i=0;i<l.size();i++) // пробегаем по всем линиям треугольника
   for(size_t j1=l[i].first, j1end=j1+l[i].second,
              j2=l2[i].first;j1<j1end;j1++, j2++) // по всем точкам линии
      img2[j2]=img[j1]; // копируем ту часть 1-й картинки, которая покрыта треугольником во 2-ю картинку

код примера скорее всего с ошибками, но сами функции проверены электроникой