여러 포인트를 찍어 폴리곤 채우기 구현 시도기, 마지막 날.

 몇가지 잘못 구현된 부분을 수정 하고, 간략화 하여 어느정도 복잡도를 가지는 영역 내를 채우는 것을 성공리에 완성 하였습니다. 아직 테스트를 해 보면 매우 복잡한 영역은 여전히 node 에서 잘못 처리되는 경우가 발견 되긴 합니다만, 이 부분은 다음 구현으로 넘기고 이번엔 완료된 것을 통해서 약간의 알고리즘 설명을 남겨 보도록 하겠습니다.

 먼저 참고한 알고리즘은 Darel Rex Finley 라는 사람의 페이지를 통해서 입니다.

http://alienryderflex.com/polygon_fill/

Polygon fill algorithm

 알고리즘은 알고나면 꽤 간단 합니다. 먼저, 삼각형을 하나 그린다 치면, 아래 처럼 좌표계가 만들어 지고, 이 좌표계는 vector < x, y > 에 차곡 차곡 쌓이게 됩니다.

 여기서 vector < x, y > 는 0번째와 마지막 이 같은 위치를 가지는 ring vector 로 구성이 되어야 하며, 시작점이 어디던 간에 re-order 를 통해 가장 y 좌표가 높은 것을 0 번째 위치로 시작하도록 하는 것이 빠릅니다.

 여기서 삼각형 안을 채우는 것은 y 좌표계로 부터 x(0) 부터 x'(영역 넓이) 까지의 길이를 모두 검사하는 scanline 단위의 영역 접점 검사가 이루어 지게 됩니다.

  스캔라인을 검사 하여, 좌표계가 가지는 접점은 바로 Line draw 알고리즘에  기반을 한, 것으로 한 점과 점 사이에 선이 만나는 영역을 각 node 로 추가 하게 됩니다.

 위 경우 삼각형이 시작되는 위치로 부터 생기는 node 는 2개씩이 되며, 이 2개가 하나의 짝으로 그 둘 사이를 채우가 되면 ..

위 이미지 처럼 그 안을 채울 수 있게 된다는 의미 입니다. 각 node 는 하나의 스캔라인 내에 여러개가 존재 할 수 있으며 그로 인해 아래처럼 어느정도 복잡도를 가지는 다각형을 채울 수 있게 됩니다.

Code explaination

 소스내 코드는 main.cpp 안에 다음 class 가 존재 합니다.

class TestDrawBox : public Fl_Box
{
    public:
        TestDrawBox(int x,int y,int w,int h);
        virtual ~TestDrawBox();

    protected:
        int handle( int event );
        void draw();

    public:
        typedef struct
        { int x; int y; } vecponint;

    protected:
        vector< vecponint > points;

    protected:
        void createme();
        void reorderpoints();
        void updatevectorregion();
        bool checkconflict( vecponint* refvp );
        bool checkduplicated( vecponint* refvp, int* idx = NULL );
        void drawxmark( int x, int y, int brdr = 1, int dst = 2 );
        void drawcursor( int x, int y );
        bool checknearpoints( int* x, int* y );

    protected:
        Fl_RGB_Image*   imgme;
        uchar*          imgmebuffer;
        int             last_mx;
        int             last_my;
        bool            inassemble;
        bool            oncompleted;
        bool            drawmouse;
        bool            holddraw;

};

 이 코드는 FLTK 라이브러리를 상속 받아 구동 되는 형태 이며, 다음 위치에서 해당 소스를 다운로드 받아 빌드 할 수 있습니다.

• FLTK : https://github.com/rageworx/fltk-1.3.4-1-ts

 또한 빌드는 MSYS shell 과 MinGW-W64 컴파일러가 필요 합니다.

• MSYS : https://sourceforge.net/projects/mingw/files/
• MinGW-W64 : https://sourceforge.net/projects/mingw-w64/

 코드 빌드는 Code::Blocks 라는 IDE 를 통해서 합니다. 다운로드는

• Code::Blocks : http://www.codeblocks.org/downloads/binaries

 코드에서 알고리즘 관련으로 눈여겨 보면 되는 부분은 다음 method 입니다.

• void TestDrawBox::reorderpoints();
• void TestDrawBox::updatevectorregion();
  

 여기서 reorderpoints() 는 일일히 클릭된 영역을 기반으로 만들어진 vector 를 최상위 Y 위치를 기준으로 재구성 하며, 이는 updatevectorregion() 함수 내에서 호출 됩니다. 그리고 실제 node 를 만들어 polygon 내를 채우는 부분은 바로 updatevectorregion() 으로서 다음 과 같은 차례를 거칩니다.

const int max_y = imgme->h();
const int max_x = imgme->w();

vector< double > node_x;

unsigned fillcount = 0;

for( int cur_y=0; cur_y<max_y; cur_y++ )
{
	int         ptsz        = points.size();
	int         rcnt        = ptsz - 1;
	unsigned    node_count  = 0;

	for( int cnt=0; cnt<ptsz; cnt++ ) 
	{
		if ( ( (double)points[cnt].y   < (double)cur_y ) &&
			 ( (double)points[rcnt].y >= (double)cur_y ) ||
			 ( (double)points[rcnt].y  < (double)cur_y ) &&
			 ( (double)points[cnt].y  >= (double)cur_y ) )
		{
			double newv = (double)points[cnt].x +
						  ( (double)cur_y - (double)points[cnt].y ) ⁄
						  ( (double)points[rcnt].y - (double)points[cnt].y ) *
						  ( (double)points[rcnt].x - (double)points[cnt].x );

			node_x.push_back( newv );
		}

		rcnt = cnt;
	}

	int node_x_sz = node_x.size();

	⁄⁄ sort nodes ..
	if ( node_x_sz > 1 )
	{
		sort( node_x.begin(),
			  node_x.begin() + node_x_sz - 1,
			  sortcondition );

		printf("nodes[%04d] : ", cur_y );
		for( int ncnt=0; ncnt<node_x_sz; ncnt++ )
		{
			printf("%.2f, ", node_x[ncnt] );
		}
		printf("\n");

	}

	for( int dcnt=0; dcnt<node_x_sz; dcnt+=2 )
	{
		if ( node_x[dcnt] >= max_x )
			break;

		if ( node_x[dcnt+1] > 0 )
		{
			if ( node_x[dcnt] < 0 )
			{
				node_x[dcnt] = 0;
			}

			if ( node_x[dcnt+1] > max_x )
			{
				node_x[dcnt+1] = max_x;
			}

			for( int cur_x=node_x[dcnt]; cur_x<=node_x[dcnt+1]; cur_x++ )
			{
				int buffpos = ( max_x * cur_y + cur_x ) * 3;
				imgmebuffer[ buffpos + 0 ] = 0x33;
				imgmebuffer[ buffpos + 1 ] = 0x33;
				imgmebuffer[ buffpos + 2 ] = 0xFF;
				fillcount++;
			}
		}
		else ⁄⁄⁄ for test ...
		{
			for( int cur_x=node_x[dcnt]; cur_x<max_x; cur_x++ )
			{
				int buffpos = ( max_x * cur_y + cur_x ) * 3;
				imgmebuffer[ buffpos + 0 ] = 0x33;
				imgmebuffer[ buffpos + 1 ] = 0xFF;
				imgmebuffer[ buffpos + 2 ] = 0xFF;
			}
		}
	}

	node_x.clear();

} ⁄⁄⁄ of for( y .. )

 전체적으로 y 축을 기준으로 (스캔라인) x  축 node 들을 만든 다음, 이를 가지고 node pair 사이를 색으로 채우게 되는 간단한 구조 입니다. 필요에 따라 색을 채우는 대신, 다른 알고리즘에 응용해도 됩니다.

소스 및, CBP 와 디버깅 바이너리 포함 다운로드

fltk_polyfill_test_day03-bugfixed.zip

_ps_

2016-12-22 , node sorting 에 버그가 있는걸 수정 해서 다시 올렸습니다.