Graham scan 알고리즘 (Convex hull 추출)

 (원래 기준점은 최하단 왼쪽 점을 고르게 되지만 PIXI는 DirectX처럼 y최소값이 상단에 위치합니다.)

Graham scan이란?

 Graham scan이란 유한개의 점 중 다른 점을 가둘 수 있는 외곽점을 찾는 알고리즘 중 하나입니다. 이 외곽점을 이으면 볼록 껍질(Convex hull)이 됩니다.

 시간 복잡도는 입니다.

알고리즘

1. y 값이 가장 작은 점을 찾습니다.(만약 여러 개 존재시 x값이 가장 작은 점을 선택합니다.) 이 때, 이 점을 P0이라 부르겠습니다.
2. P0을 기준으로 다른 모든 점의 각도를 구하여 각도가 작은 순서대로 정렬합니다.
3. P0과 정렬된 점을 2개를 Convex hull에 추가합니다.
4. 그 다음 점부터 다음 조건을 반복하여 수행합니다.
1. Convex hull의 마지막 직선에서 현재 점이 왼쪽에 있으면 Convex hull의 마지막 점을 Convex hull에서 제외합니다.(현재 점이 2번 조건을 만족할 때까지 진행합니다.)
2. Convex hull의 마지막 직선에서 현재 점이 오른쪽에 있으면 현재 점을 Convex hull에 추가하고 다음 점을 가져옵니다.
5. Convex hull을 이루고 있는 점을 이어줍니다.

코드 설명

this.genConvexHull = function()
{
     // 점이 3개 미만이면 도형을 이룰 수 없음
    if(dots.length < 3)
        return;
    
    // (1) 기준점 선정
    var fiducialPoint = null;
    dots.forEach(function(item)
    {
        if(fiducialPoint === null)
        {
            fiducialPoint = item;
            return;
        }
 
        if(item.position.y < fiducialPoint.position.y ||
            (item.position.y == fiducialPoint.position.y && item.position.x < fiducialPoint.position.x))
            fiducialPoint = item;
    });
 
    // (2) 각도 순서대로 정렬
    var heap = new Heap(dots.length, function(a, b)
    {
        return a.angle < b.angle;
    });
 
    dots.forEach(function(item)
    {
        if(fiducialPoint == item)
            return;
 
        heap.push(
            {
                value:item,
                angle:Math.atan2(item.y - fiducialPoint.position.y, item.x - fiducialPoint.position.x),
            });
    });
 
    // (3) 기준점과 정렬된 앞의 두 점을 삽입하여 초기 Convex hull 구성
    var vertices = [];
    vertices.push(fiducialPoint);
    vertices.push(heap.pop().value);
    vertices.push(heap.pop().value);
 
    // (4) 순차적으로 조건을 실행
    var iter = heap.pop().value;
    while(true)
    {
        var prev1Point = vertices[vertices.length - 1];
        var prev2Point = vertices[vertices.length - 2];
        var prevVec = new PIXI.Vector(prev1Point.x - prev2Point.x, prev1Point.y - prev2Point.y);
 
        var currentVec = new PIXI.Vector(iter.position.x - prev2Point.position.x,
                                         iter.position.y - prev2Point.position.y);
 
        var dot = prevVec.x * currentVec.y - currentVec.x * prevVec.y;
        
        // (4-1) 점이 Convex hull 마지막 선분 기준으로 오른쪽에 있다면
        if(dot >= 0)
        {
            vertices.push(iter);
            if(heap.count() > 0)
                iter = heap.pop().value;
            else
                break;
        }
        // (4-2) 점이 Convex hull 마지막 선분 기준으로 왼쪽에 있다면
        else
            vertices.pop();
    }
 
    // (5) 점을 이어줌
    if(shape !== null)
        self.removeChild(shape);
 
    shape = new PIXI.Graphics();
    shape.lineStyle(2, 0xea5796, 1);
    shape.moveTo(vertices[0].position.x, vertices[0].position.y);
    for(var i = 1 ; i < vertices.length ; ++i)
        shape.lineTo(vertices[i].position.x, vertices[i].position.y);
    shape.lineTo(vertices[0].position.x, vertices[0].position.y);
 
    self.addChild(shape);
}

(1) 기준점 선정(기준점 : P0)

• y값이 가장 작은 점을 찾습니다.(OpenGL에서는 하단이지만 PIXI에서는 상단입니다. 어차피 모든 점이 같은 기준으로 선별되므로 추후 알고리즘에 영향을 미치지 않습니다.)
• 최소 y값의 점이 여러개라면 최소 x값을 가진 점을 선정합니다.

(2) 각도 순서대로 정렬

• Arctangent 함수를 통해 기준점과 나머지 점들의 각도를 구하여 정렬해줍니다.
• 역으로 해도 똑같습니다. 그렇기 때문에 상단이든 하단이든 중요하지 않고 y 최소값으로 사용하도록 하겠습니다.
• 정렬은 힙을 사용하였고, 이미지와 같이 dot1~dot6로 정렬하여 사용할 수 있게됩니다.

(3) 초기 Convex hull을 구성

• P0, dot1, dot2로 비교를 위한 초기 Convex hull을 구성해줍니다. (dot2는 무조건 선분 p0, dot1의 오른쪽에 있게되므로 넣어줍니다.)

(4) 순차적으로 조건을 실행

1. 점이 Convex hull 마지막 선분을 기준으로 오른쪽에 있다면 Convex hull에 추가하고 다음 점을 가져옴
2. 점이 Convex hull 마지막 선분을 기준으로 왼쪽에 있다면 Convex hull 마지막 점을 제외

• 이미지1, 이미지2 : dot3을 판별합니다.
• 선분 dot1, dot2를 기준으로 dot3은 오른쪽에 있으니 dot2를 convex hull에서 제외하고 다음 루프로 넘어갑니다.
• 이미지3, 이미지4 : 변경된 기준점으로 dot3을 재판별합니다.
• dot4는 선분 p0, dot1 오른쪽에 있기 때문에 convex hull에 추가합니다.

(5) 점을 이어줌

• 4번의 루프가 끝나면 convex hull이 완성되고 인접한 꼭지점끼리 이어줍니다.

두 선분의 좌우관계 구분

 두 선분의 좌우관계 구분은 벡터의 외적으로 판별할 수 있습니다.

(https://ko.wikipedia.org/wiki/%EB%B2%A1%ED%84%B0%EA%B3%B1)

a*b(a가 b의 왼쪽에 있음)를 할 경우 위쪽을 향하는 노멀 벡터를 가져올 수 있고,

b*a(b가 a의 왼쪽에 있음)를 할 경우에는 아래쪽을 향하는 노멀벡터를 가져올 수 있습니다.

이 성질을 이용하여 a, b의 z값이 0이라고 했을 때, a * b의 z값이 음수면 b는 a의 왼쪽에 있는 것이고, 양수면 b는 a의 오른쪽에 있다고 할 수 있습니다.