본문 바로가기
반응형

알고리즘

 (2)
다익스트라(Dijkstra) 알고리즘 안 가본 노드 중에 가장 빨리 갈 수 있는 노드에 가서 거리 기록하는 일을 반복 #include #include #include #include constexpr int VERTEX_COUNT = 5; constexpr int distances[5][5] = { { 0,-1, 6, 6,-1}, { 3, 0,-1,-1,-1}, {-1,-1, 0, 2,-1}, {-1, 1, 1, 0,-1}, {-1, 4,-1, 2, 0}, }; /* constexpr int VERTEX_COUNT = 6; constexpr int distances[VERTEX_COUNT][VERTEX_COUNT] = { { 0, 2, 5, 1,-1,-1}, { 2, 0, 3, 2,-1,-1}, { 5, 3, 0, 3, 1, 5}, { 1,..
브레즌햄(Bresenham) 알고리즘 브레즌햄 알고리즘은 컴퓨터 그래픽스에서 복잡하고 계산을 느리게 만드는 실수 계산을 배제하고 정수 계산만으로 직선을 그리기 위해 만들어진 알고리즘 입니다. 직선의 공식을 이용해 계산된 좌표값은 결국 스크린에 표현하기 위해서는 소수점 이하를 버림한다던지 반올림 해서 정수로 만들게 됩니다. 이렇게 버려지는 소수점 이하의 복잡한 계산을 브레즌햄 공식을 이용하여 간단한 정수 연산으로 바꾸는 과정을 알아보도록 하겠습니다. 먼저 두 점을 지나는 직선의 방정식을 보면 아래와 같습니다 : y - y1 = (x2 - x1) / (y2 - y1) * (x - x1) y = (x2 - x1)/(y2 - y1) * (x - x1) + y1 예를 들어 (2, 1) 과 (6, 4)를 지나는 직선의 점들 중 x가 3일때 y의 값은 ..
반응형

티스토리툴바