본문 바로가기

로그라이크

보이어 왓슨(Bowyer-Watson) 알고리즘

kukuta 2024. 11. 26. 00:17

들어가며

보이어 왓슨(Bowyer-Watson) 알고리즘은 델로네 삼각분할(Delaunay Triangulation)이라는 공간 분할법을 구현하는 여러가지 방법 중에 하나다.

보이어 왓슨 알고리즘에 앞서 델로네 삼각분할을 간략하게 살펴 보도록 하자.

델로네 삼각분할은 공간을 분할하는 방법 중에 하나로써 평면 위의 임의의 점들을 삼각형 형태로 연결하는 방법이다. 다만 단순 삼각형을 만드는 것이 아니라, "삼각형의 내각의 최소값이 최대가 되도록 한다"라는 규칙을 가진다. 간단히 말하면 최대한 정삼각형에 가까운 삼각형들을 만드는 것이다.

다음 그림을 살펴 보자 :

델로네 삼각분할

위 그림의 A의 네 점들을 연결하여 삼각형을 만든다고 생각해 보자. 두 가지 선택이 가능한데, B의 경우 처럼 세로로 분할 해 긴 삼각형 형태를 만들거나, C와 같이 가로로 분할 하여 정삼각형에 가까운 형태를 만들 수 있다. 둘 중 '최소 내각이 최대'가 되는 C형태의 분할이 델로네 삼각분할의 결과가 된다.

'최소 내각을 최대'가 되도록 만들기 위해선 일명 '델로네 조건'이라 것을 만족해야 한다.

델로네 조건 : 모든 삼각형의 외접원에 다른 점이 들어가지 않아야 한다

※ 삼각형의 외접원 : 필자의 경우 수학을 잘 못하는 관계로 보이어 왓슨 알고리즘에 대해 공부하기전 삼각형의 외접원에 대해 먼저 공부할 필요가 있었다. 이에 대한 포스팅을 [여기]에 정리해 놓았으니 필요하다면 먼저 살펴 보고 오도록 하자.

이렇게 정삼각형에 가까운 형태로 공간을 분할하게 되면 공간들 간의 연결 거리를 최소화 할 수 있기 때문에 주로 도로망 설계 같은 분야에서 많이 활용 되는 방법이다. 이것 외에도 델로네 삼각분할에 대해 이야기하자면 블로그 포스팅 몇 개 분량이 나오긴 하지만 오늘 포스트의 주제는 델로네 삼각분할이 아닌 이것을 구현하기 위한 방법 중의 하나인 '보이어 왓슨' 알고리즘이므로 여기까지만 하도록 하겠다. 더 관심이 있으신 분들은 [여기]를 참고하도록 하자.

※ 델로네 vs 들로네 ??
Delaunay triangulation을 다루는 한글 포스트들에서 '들로네' 또는 '델로네'가 혼용되어 쓰이고 있다. Delaunay triangulation은 프랑스의 수학자인 Boris Delaunay의 이름에서 유래되었다. 프랑스어 발음 규칙에 따르면, '들로네'에 가깝게 발음 되나, 한국에서는 영어식 발음인 '델로네'가 더 자주 사용 되고 있는 만큼 본 포스트에서도 '델로네'를 사용하도록 한다.

보이어 왓슨(Bowyer-Watson) 알고리즘

델로네 삼각분할에 대해 알아 보았으니, 오늘의 주제인 보이어 왓슨 알고리즘에 대해 살펴 볼 차례다. 보이어 왓슨 알고리즘은 2차원 평면에서 델로네 삼각분할을 생성하기 위한 알고리즘 중 하나다.

알고리즘 동작 원리

보이어 왓슨 알고리즘은 증분 방식(incremental algorithm)으로 작동하며 다음과 같은 단계로 이루어 진다.

1. 초기화

입력된 점들을 처리하기 전에, 모든 점을 포함할 수 있는 충분히 큰 초기 삼각형(super triangle)을 생성한다.
이 초기 삼각형은 이후 델로네 삼각분할 과정에서 사용되며, 최종 결과에서 제외 된다..

2. 점 추가

주어진 점 집합에서 한 번에 하나의 점을 추가하면서 삼각분할을 갱신한다.
새 점이 추가 되었을 때, 새 점이 기존 삼각형들의 외접원(circumcircle) 안에 포함 되는지 검사한다.

3. 삼각형 갱신

새 점이 외접원 안에 포함되는 모든 삼각형을 삭제 한다. 이 과정을 통해 기존 삼각형들 사이에 공백('polygonal hole' or 'cavity')이 생기게 된다.
새로 생성된 공백 영역을 새 점과 공백 영역을 둘러 싸는 경계선으로 연결하여 새로운 삼각형들을 생성한다.

4. 반복

위 과정을 모든 점에 대해 반복하여 점진적으로 델로네 삼각분할을 완성한다.

5. 초기 삼각형 제거

모든 점들이 연결 되어 삼각형들의 구성이 완료되면 초기 삼각형에 속한 꼭짓점들과 관련된 모든 삼각형들을 제거한다.

이해를 돕기 위해 위 과정들을 그림으로 다시 한번 살펴 보자.

[그림 1] 모든 점을 포함할 수 있는 '초기 삼각형'을 설정한다(모든 점들은 그리드 영역에만 존재한다고 가정한다).
[그림 1-2] 초기 삼각형 안에 새로운 점을 추가하면, 초기 삼각형의 외접원에 포함 되므로 삼각형의 외접원 안에 다른 점이 있어서는 안된다는 델로네 조건에 위배 된다.
[그림 2] 델로네 조건에 위배 되므로 삼각형 갱신 과정이 발생한다. 초기 삼각형을 삭제하고, 이 공백을 새로 추가 된 점과 공백 영역을 둘러 싸는 경계선(초기 삼각형의 각 변들)으로 연결하여 새로운 삼각형들을 생성한다.

이번에는 추가 되는 점은 빨간색으로 표시된 삼각형의 외접원 내에 위치한다.
빨간 삼각형을 삭제 하고, 공백을 둘러 싸는 경계선과 새로 추가된 점을 연결하여 분할된 삼각형을 새로이 생성한다.

[그림 1] 이번에 추가된 점은 초록색, 빨간색 외접원에 동시 포함 된다.
[그림 2] 초록색, 빨간색 삼각형을 삭제한다. 삭제된 삼각형이 두 개 이상인 경우는 공백 영역이 삼각형 이상의 다각형이 된다. 이런 경우 삭제 되는 변들 중, 겹치는 변(위 가운데 그림에서 파란색 타원으로 표시된 변)을 빼면 공백 영역의 둘러싸는 변들을 구할 수 있다.

다른 삼각형과 공유 되는 '변'은 제외 된다.

[그림 3] 공백 영역을 둘러싸는 경계를 이루고 있는 변들로 부터 새로 추가된 점을 연결하여 분할된 삼각형을 생성한다.

모든 점의 추가가 끝나면 기초 삼각형과 연결된 모든 삼각형들을 삭제한다.
위 그림에서는 빨간색으로 표시된 초기 삼각형의 꼭지점에 연결된 모든 삼각형들을 삭제하고 나면 오른쪽 그림과 같은 결과를 얻을 수 있다.

구현

알고리즘의 동작 방식을 슈도 코드(Pseudo code)로 표현하면 아래와 같다.

function BowyerWatson (pointList)
    // pointList : 삼각형을 구성할 점들의 목록
    triangulation := empty triangle mesh data structure
    add super-triangle to triangulation // pointList의 모든 점들을 포함할 만큼 큰 삼각형이어야 함
    
    for each point in pointList do // 한번에 하나씩 삼각형에 추가함
        badTriangles := empty set  // 추가 되는 외접원에 점이 포함되어 삭제될 삼각형 목록
        
        for each triangle in triangulation do // 새로 추가된 점이 각 삼각형의 외접원에 포함되는 체크
            if point is inside circumcircle of triangle
                add triangle to badTriangles
                
        polygon := empty set
        for each triangle in badTriangles do // 공백 영역의 경계 찾기
            for each edge in triangle do
                if edge is not shared by any other triangles in badTriangles
                    add edge to polygon
                    
        for each triangle in badTriangles do // 외접원에 포함된 삼각형들 삭제
            remove triangle from triangulation
            
        for each edge in polygon do // 공백 영역의 경계와 새 점을 연결하여 새로운 삼각형 생성
            newTri := form a triangle from edge to point
            add newTri to triangulation
            
    for each triangle in triangulation // 초기 삼각형과 연결된 모든 삼각형들 삭제
        if triangle contains a vertex from original super-triangle
            remove triangle from triangulation
            
    return triangulation

하지만 슈도 코드만으로는 만족할 수 없으니 C#으로 다시 구현해 보도록 하겠다. 전체 소스 코드는 다음 링크에서 확인 할 수 있다.

1. 초기화

Triangle CreateSuperTriangle(List<Vector3> points)
{
    foreach (Vector3 point in points)
    {
        minX = Mathf.Min(minX, point.x);
        maxX = Mathf.Max(maxX, point.x);
        minY = Mathf.Min(minY, point.y);
        maxY = Mathf.Max(maxY, point.y);
    }
    
    float dx = maxX - minX;
    float dy = maxY - minY;
    
    // super triangle을 포인트 리스트 보다 크게 잡는 이유는
    // super triangle의 변과 포인트가 겹치게 되면 삼각형이 아닌 직선이 되므로
    // 델로네 삼각분할을 적용할 수 없기 때문이다.
    Vector3 a = new Vector3(minX - dx,      minY - dy);
    Vector3 b = new Vector3(minX - dx,      maxY + dy * 3);
    Vector3 c = new Vector3(maxX + dx * 3,  minY - dy);
    
    return new Triangle(a, b, c);
}

2. 점 추가 및 삼각형 갱신

void AddPoint(Vector3 point)
{
    // 추가 되는 외접원에 점이 포함되어 삭제될 삼각형 목록
    List<Triangle> badTriangles = new List<Triangle>();
    foreach (var triangle in triangles)
    {
        // 삼각형의 외접원에 점이 포함 되는지 체크
        if (true == triangle.circumCircle.Contains(point))
        {
            badTriangles.Add(triangle);
        }
    }
    
    // 삼각형 삭제로 인한 공백 영역의 경계 찾기
    List<Edge> polygon = new List<Edge>(); 
    foreach (var triangle in badTriangles)
    {
        List<Edge> edges = triangle.edges;
        
        foreach (Edge edge in edges)
        {
            // find unique edge
            // 삼각형과 공유 되지 않는 변만이 공백 영역의 경계가 된다.
            bool unique = true;
            foreach (var other in badTriangles)
            {
                if (true == triangle.Equals(other))
                {
                    continue;
                }

                foreach (var otherEdge in other.edges)
                {
                    if (true == edge.Equals(otherEdge))
                    {
                        unique = false;
                        break;
                    }
                }
                
                if (false == unique)
                {
                    break;
                }
            }
            
            if (true == unique)
            {
                polygon.Add(edge);
            }
        }
    }
    
    foreach (var badTriangle in badTriangles)
    {
        triangles.Remove(badTriangle);
    }
    
    // 공백 경계와 새로 추가된 점들을 연결해 새로운 삼각형 생성
    foreach (Edge edge in polygon)
    {
        Triangle triangle = new Triangle(edge.v0, edge.v1, point);
        triangles.Add(triangle);
    }
}

3. 초기 삼각형 제거

void RemoveSuperTriangle()
{
    List<Triangle> remove = new List<Triangle>();
    foreach (var triangle in triangles)
    {
        if (true == (triangle.a == superTriangle.a || triangle.a == superTriangle.b || triangle.a == superTriangle.c ||
                     triangle.b == superTriangle.a || triangle.b == superTriangle.b || triangle.b == superTriangle.c ||
                     triangle.c == superTriangle.a || triangle.c == superTriangle.b || triangle.c == superTriangle.c)
        )
        {
            triangles.Remove(triangle);
        }
    }
}

4. 전체 소스 코드

View Source Code

마치며

이상 보이어 왓슨 알고리즘의 동작 방식과 C#을 이용해 직접 구현하는것 까지 살펴 보았다. 본 포스트에 사용된 유니티 프로젝트는 [여기]에서 찾아 볼 수 있으며 다음과 같이 프로젝트를 실행하여 알고리즘이 어떻게 동작하는지 실시간으로 확인할 수 있다.

Hierarchy 창에서 Delaunay 객체를 선택하면 Inspector 창에서 실시간으로 보이어 왓슨 알고리즘을 이용한 삼각분할 이 어떻게 진행 되는지 테스트 해볼수 있다.

Reset : 추가된 모든 점과 삼각형들을 삭제한다.
Toggle Circle : 삼각형의 외심원을 활성화/비활성화 시킨다.
RemoveSuperTriangle : 기초 삼각형과 그에 연결된 모든것들을 삭제한다.

부록 1. 같이 읽으면 좋은 글

저작자표시 비영리

유익한 글이었다면 공감(❤) 버튼 꾹!! 추가 문의 사항은 댓글로!!

티스토리툴바