[C/C++] Simple Polygon의 Triangulation – OpenGL

1. Visual Studio 2015와  OpenGL 사용

아래 글 참조 http://fatc.club/2017/03/25/1814

 

2. 코드

https://github.com/ChangdaeJeong/triangluation-openGL

위의 깃허브 참조  

 

3. 데모 영상

콘솔창 + OpenGL 영상 https://www.youtube.com/watch?v=pxCs9ynF_OA&feature=youtu.be

OpenGL 영상 https://www.youtube.com/watch?v=fBwQU2o17aQ  

 

4. 기타

Triangulation 할때, Upper & Lower Chain을 이미 알고 있다는 가정하에, 구현하였음.

초기 시작시 X-coordinate 순으로 점이 추가됨. 그 다음 Upper Chain은 초록색, Lower Chain은 파랑색으로 나타남. 

여기서 Leftmost, Rightmost 점이 파란색인건 그냥 무시하기 바람. 

어차피 알고리즘 자체에서 양 끝 점이 어느 체인에 포함되는지 여부는 딱히 필요없음.

Triangulation Pseudo Code는 아래와 같음.

 known Upper & Lower chain
merge Upper & Lower chain ordered by X coordinate, Y coordinate asc
init stack, list
push 1st, 2nd points into stack
loop from 2 to n-1
	if the top point of the stack and ith point are in same chain
		stack.pop
		loop stack is not empty
			pts <- stack.top
			stack.pop
			if pts and ith point make a diagonal
				insert the diagonal into L
		push the last point which was saved in stack
		push ith point into stack
			
	otherwise
		while stack.size >= 1
			pts <- stack.top
			stack.pop
			temporalStack <- pts
			if pts and ith point make a diagonal
				insert the diagonal into L
		stack.pop
		recover stack from temporalStack
		push ith point into stack

 그리고 OpenGL은 글자 출력이 딱히 편리한게 아니라서, 스택의 상태나 리스트의 상태는 콘솔에 출력하였음. 참고.