Форум программистов [Powered by Invision Power Board]

Код


#!/usr/bin/python
# coding: utf8
import Image ; Image.init( )

file = "./x.png";

im = Image.open( file )
startx, starty, endx, endy = im.getbbox( )
endx -= 1 ; endy -= 1

max_x, min_x, max_y, min_y = 0, 0, 0, 0 

def Fill( x, y, new_color ):
    pixels_queue = [ ]
    pixels_queue.append( (x, y) )

    global max_x, max_y, min_x, min_y
    max_x, min_x, max_y, min_y = x, x, y, y

    def Fill_PixelRoutine( pixel, new_color ):
        self_color = im.getpixel( pixel )
        im.putpixel( pixel, new_color )

        x, y = pixel
        
        global max_x, max_y, min_x, min_y
        if x > max_x: max_x = x
        if x < min_x: min_x = x
        if y > max_y: max_y = y
        if y < min_y: min_y = y
        
        check = (x-1, y)
        if x > startx and im.getpixel( check ) == self_color:
            if not check in pixels_queue: pixels_queue.append( check )
        
        check = (x+1, y)
        if x < endx   and im.getpixel( check ) == self_color:
            if not check in pixels_queue: pixels_queue.append( check )
            
        check = (x, y-1)
        if y > starty and im.getpixel( check ) == self_color:
            if not check in pixels_queue: pixels_queue.append( check )
        
        check = (x, y+1)
        if y < endy   and im.getpixel( check ) == self_color:
            if not check in pixels_queue: pixels_queue.append( check )

    counter = 0
    while pixels_queue: # not empty
        pixel = pixels_queue.pop( 0 )
        print counter, pixel
        Fill_PixelRoutine( pixel, new_color )
        if counter % 10000 == 0:
            im.show( )
        counter += 1

    print "(%d, %d) (%d, %d)" % ( min_x, min_y, max_x, max_y )
    im.show( )

Fill( 50, 30, 160 )

Код


///////////////////////////////////////////////////////////////////////////////////////////
// Определим, является ли точка граничной, т.е:
//        - точка удовлетворяет предикату IsOk
//        - имеет хотя бы одного "не Ok" 4-соседа
//        - имеет хотя бы одного "Ok" 8-соседа        (не изолирована)
template <class _PRED>
bool IsOutlinePoint(const POINT& pt,_PRED IsOk)
{
    if (!IsOk(pt)) return false;

    // проверяем 4-соседей
    int cnt[2] = { 0,0 };            // не-Ok-соседи, Ok-соседи
    for (CDir dir = 0; dir < 8; dir+=2)    
        cnt[IsOk(dir.Move(pt))]++;
    if (!cnt[0]) return false;        // нет пустых соседей
    if (cnt[1]) return true;
    
    // проверяем 8-соседей
    for (CDir dir=1; dir < 8; dir+=2)    
        if (IsOk(dir.Move(pt))) return true;

    return false;
}

///////////////////////////////////////////////////////////////////////////////////////////
// Прослеживание контура: предикат IsOk как в предыдущем алгоритме + накопитель точек Store
// с интерфейсом bool operator ()(const POINT&) должен возвращать false для прекращения
// цикла; он же отвечает за проверку замыкания
// Возвращаемое значение: true, если возврат произошел по инициативе Store, false - ошибка:
// начальная точка не является точкой границы (см. код)
// Начальная точка не заносится в Store!!!
template <class _PRED, class _STORE>
_STORE OutlineContour(POINT pt,_PRED IsOk,_STORE Store)
{
    if (!IsOutlinePoint(pt,IsOk)) { ASSERT(0); return Store; }

    // ищем пустую точку, задающую стартовое направление поиска
    POINT tmp;
    for (CDir dir=0; IsOk(tmp=dir.Move(pt)); ++dir);            

    while (true)
    {
        ASSERT(!IsOk(tmp));
        // pt - предыдущая точка границы и центр поиска; ищем внутреннюю точку
        POINT ptPrev = tmp;
        for ( ; !IsOk(tmp=dir.Move(pt)); ++dir, ptPrev=tmp);
        // сохраняем
        if (!Store(pt=tmp)) break;
        // ptPrev - последняя пустая точка; 
        // начальное направление след. итерации задается направлением на нее
        dir = CDir(pt,tmp=ptPrev);
    }
    return Store;
}

Код


///////////////////////////////////////////////////////////////////////////////////////////
// Направления на целочисленной решетке: ось X - вправо, ось Y - вниз
//  
//        3   2   1        
//          \ | /          
//        4 - 8 - 0 -+ X   
//          / | \          
//        5   6   7        
//         |            
//             +
//        Y
class CDir
{
public:
    enum { R=0,RU,U,LU,L,LD,D,RD,Z };

    CDir(int dir): m_dir(dir%8) { }
    CDir(POINT p,POINT q);                // направление из точки <p> в точку <q>

    operator int() const { return m_dir; }

    CDir& operator++();
    CDir  operator++(int);
    CDir& operator+=(int);
    CDir& operator--();
    CDir  operator--(int);
    CDir& operator-=(int);

    int   Dir () const;
    POINT Move(const CPoint& pt) const;
    SIZE    Step() const;

private:
    static int Dir(int dx,int dy);    // направление из точки <0,0> в точку <dx,dy>

private:
    int m_dir;
};

inline CDir::CDir(POINT p,POINT q)
{
    m_dir = Dir(q.x-p.x,q.y-p.y);
}
inline CDir& CDir::operator++()        
{ 
    m_dir++; return *this;    
}
inline CDir CDir::operator++(int)
{ 
    CDir tmp = *this; 
    ++(*this); 
    return tmp;    
}
inline CDir& CDir::operator--()        
{ 
    m_dir--; return *this;    
}
inline CDir CDir::operator--(int)
{ 
    CDir tmp = *this; 
    --(*this); 
    return tmp;    
}
inline CDir& CDir::operator+=(int n)
{ 
    m_dir += n;    return *this;    
}
inline CDir& CDir::operator-=(int n)
{ 
    m_dir -= n;    return *this;    
}
inline int CDir::Dir() const
{
    int dir = m_dir%8;
    if (dir < 0) dir +=8;
    ASSERT(dir >= 0 && dir < 8);
    return dir;
}
inline int CDir::Dir(int dx,int dy)
{        
    static int _dir[9] = { LU,U,RU,L,Z,R,LD,D,RD };
    if (dx < -1 || dx > 1 || dy < -1 || dy > 1) { ASSERT(0); return Z; }
    else return _dir[(dy+1)*3 + (dx+1)];
}
inline POINT CDir::Move(const CPoint& pt) const
{
    return pt + Step();
}
inline SIZE CDir::Step() const
{
    static SIZE    _inc[] = { {1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1} };
    return _inc[Dir()];
}