사용자 도구

사이트 도구


kb:bresenhamalgorithm

Bresenham Algorithm

attachment:bresenham.gif

원래는 2D 그래픽에서 사용하는 알고리즘이지만, PathFinding 등 여러 가지 목적으로 사용할 수 있다.

2D 라인 알고리즘

struct POINT2
{
    int x, z;
    POINT2(int _x = 0, int _z = 0) : x(_x), z(_z) {}
};
 
void GetPointsInLine(int x0, int y0, int x1, int y1, std::vector<POINT2>& line)
{
    // 시작점.
    int x = x0, y = y0; 
 
    // 라인의 기울기.
    int dx = x1-x0, dy = y1-y0; 
 
    // 라인의 기울기에 따라 옵셋 결정.
    int sx = (dx > 0 ? 1 : (dx < 0 ? -1 : 0)); 
    int sy = (dy > 0 ? 1 : (dy < 0 ? -1 : 0)); 
 
    // 복셀 선택을 위한 파라미터 계산.
    dx = abs(dx); 
    dy = abs(dy); 
    int ax = 2 * dx, ay = 2 * dy; 
    int decx, decy; 
 
    // 가장 긴 축을 판단한다..
    int maximum = dx, var = 0; 
    if (dy > maximum) { maximum = dy; var = 1; } 
 
    // 브레센햄.
    if (var == 0)
    {
        for (decy=ay-dx; ; x += sx, decy += ay) 
        { 
            line.push_back(POINT2(x, y));
 
            if (x == x1) break; 
            if (decy >= 0) { decy -= ax; y += sy; } 
        } 
    }
    else
    {
        for (decx=ax-dy; ; y += sy, decx += ax) 
        { 
            line.push_back(POINT2(x, y));
 
            if (y == y1) break; 
            if (decx >= 0) { decx -= ay; x += sx; } 
        } 
    }
}

3D 라인 알고리즘

3D 라인 같은 경우에는 렌더링용이라기보다는 뭔가 다른 처리를 위한 것이다. “Voxel Traversal”로 검색해 보기 바란다.

struct POINT3
{
    int x, y, z;
    POINT3(int _x = 0, int _y = 0, int _z = 0) : x(_x), y(_y), z(_z) {}
};
 
void GetPointsInLine(
    int x0, int y0, int z0, int x1, int y1, int z1, std::vector<POINT3>& line)
{
    // 시작점.
    int x = x0, y = y0, z = z0; 
 
    // 라인의 기울기.
    int dx = x1 - x0, dy = y1 - y0, dz = z1 - z0; 
 
    // 라인의 기울기에 따라 옵셋 결정.
    int sx = dx > 0 ? 1 : (dx < 0 ? -1 : 0); 
    int sy = dy > 0 ? 1 : (dy < 0 ? -1 : 0); 
    int sz = dz > 0 ? 1 : (dz < 0 ? -1 : 0); 
 
    // 복셀 선택을 위한 파라미터 계산.
    dx = abs(dx); 
    dy = abs(dy); 
    dz = abs(dz); 
    int ax = 2 * dx, ay = 2 * dy, az = 2 * dz; 
    int decx, decy, decz; 
 
    // 가장 긴 축을 판단한다.
    int maximum = dx, var = 0; 
    if (dy > maximum) { maximum = dy; var = 1; } 
    if (dz > maximum) { maximum = dz; var = 2; } 
 
    // 브레센햄.
    if (var == 0) 
    { 
        for (decy=ay-dx, decz=az-dx; ; x += sx, decy += ay, decz += az) 
        { 
            line.push_back(POINT3(x, y, z));
 
            if (x == x1) break; 
            if (decy >= 0) { decy -= ax; y += sy; } 
            if (decz >= 0) { decz -= ax; z += sz; } 
        } 
    }
    else if (var == 1)
    {
        for (decx=ax-dy, decz=az-dy; ; y += sy, decx += ax, decz += az) 
        { 
            line.push_back(POINT3(x, y, z));
 
            if (y == y1) break; 
            if (decx >= 0) { decx -= ay; x += sx; } 
            if (decz >= 0) { decz -= ay; z += sz; } 
        } 
    }
    else
    {
        for (decx=ax-dz, decy=ay-dz; ; z += sz, decx += ax, decy += ay) 
        { 
            line.push_back(POINT3(x, y, z));
 
            if (z == z1) break; 
            if (decx >= 0) { decx -= az; x += sx; } 
            if (decy >= 0) { decy -= az; y += sy; } 
        } 
    }
}

원 알고리즘

struct POINT2
{
    int x, z;
    POINT2(int _x = 0, int _z = 0) : x(_x), z(_z) {}
};
 
void GetPointsInCircle(int cx, int cy, int radius, std::vector<POINT2>& circle)
{
    if (radius <= 0) return;
 
    int tx = 0;
    int ty = radius;
    int tp = 3 - 2 * radius;
 
    do
    {
        circle.push_back(POINT2(cx + tx, cy + ty));
        circle.push_back(POINT2(cx + ty, cy + tx));
        circle.push_back(POINT2(cx + ty, cy - tx));
        circle.push_back(POINT2(cx + tx, cy - ty));
        circle.push_back(POINT2(cx - tx, cy - ty));
        circle.push_back(POINT2(cx - ty, cy - tx));
        circle.push_back(POINT2(cx - ty, cy + tx));
        circle.push_back(POINT2(cx - tx, cy + ty));
 
        tx++;
 
        if (tp < 0)
        {
            tp += 4 * tx + 6;
        }
        else
        {
            ty--;
            tp += 4 * (tx - ty) + 10;
        }
    }
    while (tx <= ty);
}

= 링크 =

kb/bresenhamalgorithm.txt · 마지막으로 수정됨: 2014/11/06 19:04 (바깥 편집)