Simple Polygon

학교 후배가 지원한 회사의 입사 전 문제로 심플 폴리곤 이라는 문제를 주었어요. (절대 심심해서 그런건 아니고) 마침 UML 만들기도 짜증이 울끈 불끈 쏟아 올라서, 잠시 머리 좀 식혀(?!!) 줄 겸사 한번 풀어 보려고 해요.

어차피 OpenGL 관련해서, 이미 구축해 놓은 베이스 엔진도 있겠다, 테스트도 해볼 수 있기에 시도 했어요 :)

문제 자체는 간단해요.

임의의 점들이 주어 지고, 점들을 이어서 선분이 겹쳐지지 않게 하나의 면으로 만들어 주면 끝! 가령, 아래와 같은 모양새겠죠?

일단 이런 문제해결에는 알고리즘을 만들어 줘야 하고, 그에 따른 자료 구조가 필요 하겠죠! 차례대로 나열해 볼게요.

• 재료
  정점들
  
  주어진 문제 그 자체죠.
  
  
• 언어(Language)
  저는 C/C++ 유저이므로 사용 하는 언어는 C/C++로 하겠어요. 다른 언어 유저분은 코딩에 있어서는 참고만 하세요 :)
  
• 자료 구조(Data Structure)
  • 정점(Position)
    점 자체를 표현 할 수 있는 자료구조가 제일 우선시 되네요. 임의로 이차원 상의 점이라고 생각하고 만들었습니다.
    

    class Position
    {
    private:
    	double x, y;
    	
    public:
    	Position(void);
    	Position(const double &_x, const double &_y);
    	~Position(void);
    	
    	// 대입 함수
    	void operator()(const double &_x, const double &_y);
    	
    	// 거리 계산 함수
    	double DistanceFrom(const Position &_other);
    	
    	// 자체 값 출력 함수
    	void PrintMe() const;
    };
    				

    
    
    
    최종적으로 편의를 돕기위한 몇몇 함수가 추가 되었어요.
    
    
  • 정점 테이블(Position Table)
    정점들을 관리할 테이블을 제가 만들었어요. 별도의 데이터베이스 라이브러리는 사용하지 않기 때문에 직접 만들어야겠죠? :) 어려울 건 없어요. 아래와 같은 모양새 랍니다.
    
    
    
    연결은 i번째 정점이 다른 정점과 연결되어 있는 개수를 의미 해요. 아직 하나도 연결 되어 있지 않으면 0개, polygon을 만들려면 한 정점당 2개의 연결이 되어야 최종적인 polygon의 완성을 의미 하겠죠.
    
    연결 컬럼에서의 사각괄호의 의미는 "이상/이하"라는 뜻이에요.
    그냥 괄호 "()"는 "미만/초과"라는 뜻이구요.
    즉, 단위가 양의 정수(size_t) 이므로 0, 1, 2의 세 개의 숫자만 허용 된다는 의미에요. 만약 (0, 2)라면 1만 된다는 뜻이겠죠? 0 초과하고, 2 미만이니까:)
    
    
    이 부분은 그냥 STL을 이용해서 간단히 만들거에요. 포스팅의 간소화를 위해, 필요한 부분만 잘라서 넣은 거에요. 코딩 하시는 분들은 쉽게 알아 보실 듯:)
    

    #include "Position.h"
    #include <vector>
    typedef std::pair<Position, size_t> PosNConnect;
    typedef std::vector<PosNConnect> PosTABLE;
    				

    
    
  • 정점 연결 구조(Position Linked List)
    최종적으로는 어떤 정점이 서로서로 연결 되어 있나를 체크해야 하니까, 링크드리스트로 구현 하려고 해요. 뭐 직접 구현하는 건 아니고, 이거도 STL의 vector로 처리하려고 합니다. 내용은 아래와 같아요.
    
    
    
    
    초기에 정점들을 테이블로 만들었으니까 그 인덱스를 이용할 게요.
    

    #include <vector>
    std::vector<size_t> PolygonList;
    				

    
    
• 알고리즘
  
  자 이제 본격적인 시작 이에요. 제가 생각한 알고리즘은 아래와 같아요.
  
  관련 내용에 대해서는 그 어떠한 웹 검색과 지인을 통한 질문은 하지 않고 제 스스로 생각 한것임을 밝히고 진행 하겠습니다. 따라서 보는 이에 따라서 알고리즘이 비효율 적이고, 지저분 할 수도 있다는 것을 감안 하시기 바라겠습니다.
  
  
  1. 초기에 선택되는 점은 어떤 것이 되던 상관 없지만, 제일 가장자리에 있는 점을 최초의 점으로 선택 합니다.(여기서 제일 가장 자리라 함은 원점으로 부터 거리가 가장 멀리 떨어진 점으로 합니다.)
  2. 위와 같이 선택 되어서 어떤 정점으로 선분을 이어볼까~~ 하고 찾는 점을 "현재 정점" 이라고 하겠습니다.(current position, 구현상으로는 const Position &crntPos = //something;)
  3. 현재 정점으로 부터 connect가 0이면서 가장 가까운 점을 선택 합니다.
  4. 두 개의 점을 잇는 직선의 방정식을 만듭니다.
     
  5. 한쪽 항이 0이 되도록 이동 시킵니다.
     
  6. connect 가 1 이하인 정점들에 대해서 직선의 방정식을 기준으로 한쪽으로 몰려 있는지 확인 합니다. 확인 하는 방법은 아래와 같습니다.
     
  7. 만약 선택된 정점이 위의 판별과정에 반하게 되면, 해당 정점을 제하고 3. 과정으로 되돌아 갑니다. 판별시 connect가 1이하인 정점들이 한쪽 면에 들어가 있다면, 8. 과정으로 넘어 갑니다.
  8. 해당 정점을 현재 정점과 이어 주고(링크드 리스트에 넣어 주고) 각각 connect를 1씩 증가 시킵니다.(이 때 현재 정점은 기존에 1인 상태이므로 connect가 2가 되게 됩니다.) 그리고 선택된 정점을 현재 정점으로 선택 합니다.
  9. connect가 0인 정점이 없게 될 때까지 3~8 과정을 반복하며, connect가 0인 정점이 없다면 가장 마지막의 정점과 이어주고 마무리 합니다.

• 알고리즘 예시
  위의 알고리즘이 이해가 잘 가지 않을 거 같아서 예시로 5개의 정점 만을 이용해서 Step별로 설명해 볼게요.
  
  
  
  
• 실행 결과
  임의의 점들에 대한 결과만을 출력 했어요. 정점 좌표는 무작위 추출로 가져온 거라 의미가 없을 거 같아요 :) 아래의 정보는 simple polygon의 정리가 완료된 것이며, 결과 실행은 현재 제가 작업하고 있는 OpenGL 베이스 엔진으로 테스트 했어요 :)
  • 테스트1
    정점 20개 무작위 입력.
    
    
    
    
  • 테스트2
    정점 30개 무작위 입력
    
    
    
    
  • 테스트3
    
    정점 200개 무작위 입력(정점 자료는 생략...ㄷㄷㄷㄷ)
    
    
    
    
• 개선사항
  
  휴우.. 아쉬움이 많이 남는 실습이네요 :) 급하게 대충 생각하니라… 포스팅도 해야하고, 개인적으로 취업 준비도 해야하고, 귀차니즘도 있고 해서…ㅋㅋㅋ
  
  속도는 생각 하나도 안하고 구현에만 치중했기 때문에, 알고리즘을 그대로 둔다는 가정하에는 아래와 같은 개선사항을 만들면 될 거 같아요.
  1. 가용 메모리가 크다면 정점간 거리 테이블을 구축 후 처리.
  2. 직선의 방정식을 이용하는 부분은 행렬로 구현 후 처리
  3. 2번의 과정을 할 때 GPU를 사용해서 병렬처리를 하면 속도 향상에 크게 기여 할 수 있을것으로 예상.
  
  
  알고리즘 적으로도 몇 개 더 생각 해 봤어요. 간단한 설명이므로 이해가 많이 안되실 수 있음을 양해 바랄 게요 ;_;
  1. 정점들의 분포도를 이용해서, 분포가 거의 절반을 이루는 영역으로 잘라나아가는 방식으로, 그렇게 자른 영역 내에 정점이 2개가 되면 그것들 끼리 이어나가는 방식
  2. 정점들의 가장 중앙값으로 부터 가장 큰 너비가 되는 삼각형을 대략 잡은 후, 다시 중앙 값으로 부터 가장 멀리 떨어져 있는 정점 순 으로 어떤 면과 가장 짧은 가를 계산 해서 새로이 중간을 잇는 점으로 활용. 이후 반복.

• 코드
  
  필요 하신 분은 가져다 사용 하시라고 올려 놓을게요:D
  • Position.h

    #pragma once
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    
    enum POSELEM
    {
    	X,
    	Y
    };
    
    
    class Position
    {
    private:
    	double x, y;
    
    public:
    	Position(void);
    	Position(const double &_x, const double &_y);
    	~Position(void);
    
    	const double &operator[](const POSELEM &_elem) const;
    
    	void operator()(const double &_x, const double &_y);
    	double DistanceFrom(const Position &_other) const;
    	void PrintMe() const;
    
    };
    
    bool operator==(const Position &_A, const Position &_B);
    bool operator<(const Position &_A, const Position &_B);
    					

    
    
  • Position.cpp

    #include "Position.h"
    
    
    Position::Position(void)
    	: x(0.0)
    	, y(0.0)
    {
    }
    
    Position::Position( const double &_x, const double &_y )
    	: x(_x)
    	, y(_y)
    {
    
    }
    
    
    Position::~Position(void)
    {
    }
    
    void Position::operator()( const double &_x, const double &_y )
    {
    	x = _x;
    	y = _y;
    }
    
    double Position::DistanceFrom( const Position &_other ) const
    {
    	return sqrt((_other.x - x)*(_other.x - x) + (_other.y- y)*(_other.y- y));
    }
    
    void Position::PrintMe() const
    {
    	printf("%4.1lf, %4.1lf, 0.0, 1.0\n", x, y);
    }
    
    const double & Position::operator[]( const POSELEM &_elem ) const
    {
    	if(_elem == X)
    		return x;
    	return y;
    }
    
    bool operator==(const Position &_A, const Position &_B)
    {
    	return _A[X] == _B[X] && _A[Y] == _B[Y];
    }
    
    bool operator<(const Position &_A, const Position &_B)
    {
    	return _A[X] < _B[X];
    }
    					

    
    
  • main.cpp
    
    

    #include <vector>
    #include <set>
    
    #include "Position.h"
    
    typedef std::pair<Position, size_t> PosNConnect;
    typedef std::vector<PosNConnect> PosTABLE;
    
    void RandomPositionSet(
    	 const size_t &_nmb		// 점의 횟수
    	, const double &_width	// 점이 위치할 너비
    	, const double &_height	// 점이 위치할 높이
    	, PosTABLE &_posTable	// 출력할 정점 테이블
    	);
    
    // 오름차순 정렬후의 인덱스를 반환
    void Distance_ADSC_SortedList(
    	const Position &_base,	// 기준점
    	const PosTABLE &_table,	// 확인할 정점들의 테이블
    	const size_t &_connect, // connect 개수이하의 연결 정점만 확인
    	std::vector<size_t>	&_sortedList	// 정렬된 인덱스들의 집합
    	);
    
    // 두 점을 잇는 직선의 방정식으로 부터
    // connect가 1이하인 점들이 모두 같은 쪽에 위치하는가?
    bool isAllSameFace(
    	const size_t &_first,	// 첫번째 정점 인덱스
    	const size_t &_second,	// 두번째 정점 인덱스
    	const PosTABLE &_table	// 비교할 테이블
    	);
    
    void PrintTable(const PosTABLE &_table)
    {
    	for(size_t i = 0 ; i < _table.size() ; ++i)
    	{
    		printf("%u : ", i);
    		_table[i].first.PrintMe();
    	}
    }
    
    int main()
    {
    	std::vector<size_t>		polygonList;
    	PosTABLE				posTable;
    	size_t					crntPos(0);		// 현재 정점
    
    	// 랜덤한 정점 자료를 뽑는다.
    	RandomPositionSet(200, 300, 300, posTable);
    
    	// 루틴 시작
    	//PrintTable(posTable);
    
    	// 원점으로 부터 가장 먼 점을 선택
    	Position o(0.0, 0.0);
    	std::vector<size_t> from_zero_distance;
    	Distance_ADSC_SortedList(o, posTable, 0, from_zero_distance);
    	
    	// 오름차순 이므로 가장 마지막 원소가
    	// 가장 멀다
    	crntPos = from_zero_distance[from_zero_distance.size()-1];
    	
    	
    	// 현재 정점이 폴리곤 리스트의 처음이 된다.
    	polygonList.push_back(crntPos);
    	++posTable[crntPos].second;
    
    	while(true)
    	{
    		// 현재 정점으로 부터 거리를 측정
    		// 이때에는 connect가 0인 정점들만 체크
    		std::vector<size_t> from_crnt_distance;
    		Distance_ADSC_SortedList(posTable[crntPos].first, posTable, 0, from_crnt_distance);
    		
    		// connect가 0인 정점의 개수가 0개 라면, 모든 선분은 이미 이어진 상태가 된다.
    		if(from_crnt_distance.size() == 0)
    			break;
    
    		// 무조건 자기자신(0번째)으로 부터의 거리가 가장 짧으므로,
    		// 1번째 원소가 가장 거리가 짧은 원소이다.
    
    		// 거리의 오름차순으로 정렬된 원소들을 순회한다.
    		// 이중 같은 connect가 1이하인 정점들이 같은 면에 있는 것을 만족하면,
    		// 잇고(connect) 해당 정점이 현재 정점으로 바뀌면서,
    		// connect를 1증가.
    		// 아니라면, 나올때 까지 반복.
    		// 그래도 나오지 않는다면 그건 오류!!
    		bool nextStep(false);
    		for(size_t i = 0 ; nextStep == false && i < from_crnt_distance.size() ; ++i)
    		{
    			if(nextStep = isAllSameFace(crntPos, from_crnt_distance[i], posTable))
    			{
    				// crntPos과 i번째 인덱스 정점은 이어져야 한다.
    				
    				// 폴리곤리스트에 i의 인덱스를 넣는다.
    				polygonList.push_back(from_crnt_distance[i]);
    
    				// crntPos과 i번째 인덱스 정점의 connect를 각각 1증가 시킨다.
    				if(polygonList.size() != 2)
    					++posTable[crntPos].second;
    				++posTable[from_crnt_distance[i]].second;
    
    				// i번째 인덱스 정점이 crntPos이 된다.
    				crntPos = from_crnt_distance[i];
    			}
    		}
    
    		if(nextStep)
    			continue;
    
    		printf("데이터를 다시 한번 확인 하시기 바랍니다.\n");
    		return 0;
    	}
    
    	// 정점 내용 출력
    	for(size_t i = 0 ; i < polygonList.size() ; ++i)
    		posTable[polygonList[i]].first.PrintMe();
    
    	return 0;
    }
    
    void RandomPositionSet(
    	const size_t &_nmb		// 점의 횟수
    	, const double &_width	// 점이 위치할 너비
    	, const double &_height	// 점이 위치할 높이
    	, PosTABLE &_posTable	// 출력할 정점 테이블
    	)
    {
    	std::set<Position> positions;
    	
    	while(positions.size() != _nmb)
    	{
    		Position newPos((double)(rand()%(int)(_width+1)), (double)(rand()%(int)(_height+1)));
    		positions.insert(newPos);
    	}
    
    	_posTable.reserve(positions.size());
    	for(std::set<Position>::iterator itr = positions.begin();
    		itr != positions.end(); ++itr)
    	{
    		PosNConnect tableElem;
    		tableElem.first = *itr;
    		tableElem.second = 0;
    
    		_posTable.push_back(tableElem);
    	}
    }
    
    // 오름차순 정렬후의 인덱스를 반환
    void Distance_ADSC_SortedList(
    	const Position &_base,	// 기준점
    	const PosTABLE &_table,	// 확인할 정점들의 테이블
    	const size_t &_connect, // connect 개수이하의 연결 정점만 확인
    	std::vector<size_t>	&_sortedList	// 정렬된 인덱스들의 집합
    	)
    {
    	typedef std::pair<size_t, double> distanceElem;
    	std::vector<distanceElem> distanceTable;
    
    	for(size_t i = 0 ; i < _table.size() ; ++i)
    	{
    		if(_table[i].second > _connect)
    			continue;		
    
    		distanceElem newElem;
    		newElem.first = i;
    		newElem.second = _base.DistanceFrom(_table[i].first);
    
    		bool isInsert(false);
    		for(std::vector<distanceElem>::iterator itr = distanceTable.begin() ;
    			isInsert == false && itr != distanceTable.end() ;
    			++itr)
    		{
    			if(newElem.second <= itr->second)
    			{
    				distanceTable.insert(itr, newElem);
    				isInsert = true;
    				break;
    			}
    		}
    
    		if(isInsert)
    			continue;
    
    		distanceTable.push_back(newElem);		
    	}
    
    	_sortedList.resize(distanceTable.size());
    	for(size_t i = 0 ; i < distanceTable.size() ; ++i)
    		_sortedList[i] = distanceTable[i].first;
    
    }
    
    // 두 점을 잇는 직선의 방정식으로 부터
    // connect가 1이하인 점들이 모두 같은 쪽에 위치하는가?
    bool isAllSameFace(
    	const size_t &_first,	// 첫번째 정점 인덱스
    	const size_t &_second,	// 두번째 정점 인덱스
    	const PosTABLE &_table	// 비교할 테이블
    	)
    {
    	const Position &first = _table[_first].first;
    	const Position &second = _table[_second].first;
    
    	double result;
    	bool positive(false), negative(false);
    
    	// x1 == x2 ; x = x1 ; x - x1 = 0
    	// x1 != x2 ; (x-x1)*(y2-y1)/(x2-x1) - (y - y1) = 0
    	if(first[X] == second[X])
    	{
    		for(size_t i = 0 ; i < _table.size() ; ++i)
    		{
    			if(_table[i].second == 2 || i == _first || i == _second)
    				continue;
    
    			const Position &pos = _table[i].first;
    			result = pos[X] - first[X];
    
    			if(result < 0)
    				negative = true;
    			else if(result > 0)
    				positive = true;
    			
    			if(positive & negative == true)
    				break;
    		}
    	}
    	else
    	{
    		double m = (second[Y]-first[Y])/(second[X]-first[X]);
    		double c = first[Y]-m*first[X];
    		for(size_t i = 0 ; i < _table.size() ; ++i)
    		{
    			if(_table[i].second == 2 || i == _first || i == _second)
    				continue;
    
    			const Position &pos = _table[i].first;
    			result = m*pos[X]-pos[Y]+c;
    
    			if(result < 0)
    				negative = true;
    			else if(result > 0)
    				positive = true;
    
    			if(positive & negative == true)
    				break;
    		}
    	}
    
    	if(positive & negative == true)
    		return false;
    	return true;
    }
    					

이제 다시 UML문서 만들기 포스팅 해야 겠네요 :) 적절한 시기에 문제를 제공 해준 성** 군에게 고맙다는 말 전할게요ㅋㅋㅋ