5.8 선그리기

문제 

흑백 모니터 화면은 하나의 바이트 배열에 저장되는데, 인접한 픽셀 여덟 개를 한 바이트에 묶어서 저장한다. 화면의 폭은 w이며 , w는 8로 나누어 떨어진다. (따라서 어떤 바이트도 두 행에 걸치지 않는다) 물론, 화면 높이는 배열 길이와 화면 폭을 통해 유도해 낼 수 있다. 이때 (x1,y)에서 (x2,y)까지 수평선을 그려주는 함수를 작성하라. 메서드 용법은 다음과 같다. 

drawLine( byte[] screen, int width, int x1, int x2, int y)

 

접근법

정말 간단히 생각하면 x1에서 x2까지 for문을 돌면서 일일히 비트를 바꾸어 주어도 되지만, 전혀 효율적이지 못하다.

따라서 x1과 x2가 멀리 떨어져 있을 경우 그 사이 모든비트가 1인 바이트들이 있다는 것을 안다면 

그 바이트들을 0xFF로 처리해 줄 수 있을 것이다. 

그리고 시작 지점과 끝지점에 남은 비트들만 따로 처리해주면 문제를 해결할 수 있다.

 

이 문제는 특별히 처리해주어야 할 것들이 많으니 조심해서 풀어야한다. 특히, x1과 x2가 같은 바이트 내에 있는 경우와 같은 상황 말이다.

def drawLine(screen, width, x1, x2, y):
    start_offset = x1 % 8
    first_full_byte = x1 / 8 if start_offset ==0 else (x1/8) +1

    end_offset = x2 %8
    last_full_byte = x2/ 8 if end_offset == 7 else (x2/8) -1

    f = first_full_byte
    while f <= last_full_byte :
        screen[ (width/8) * y + first_full_byte] = 0xFF
        f +=1

    start_mask = 0xFF >> start_offset
    end_mask = ~(0xFF >> end_offset)
    if (x1/8) == (x2/8):
        screen[(width/8) * y + (x1/8)] |= start_mask & end_mask
    else :
        if start_offset != 0 :
            screen[(width/8) * y + (first_full_byte-1)] |= start_mask
        if end_offset != 7 :
            screen[(width/8) * y + (last_full_byte +1)] |= end_mask