자료구조 카테고리를 만들까 하다가 알고리즘 카테고리에 작성합니다.


쿼드트리란?

 트리 자료구조중 하나로 부모 노드 아래에 자식 노드를 4개(Quad)씩 가지고 있는 트리입니다. 이미지 용량, 충돌, 컬링 등 다양한 곳에서 최적화 기법으로 사용되고 있습니다.


알고리즘

 오늘은 쿼드트리를 이용해 흑백 이미지를 간단하게 압축해보도록 하겠습니다.

검은색을 0, 흰색을 1로 한다면 왼쪽 이미지는 오른쪽과 같이 나타낼 수 있습니다.


 

00001111

00001111

00000011

00000011

11110001

11111111

11111111

11111110





해당 이미지를 쿼드트리를 이용해 압축을 하면 결과는 이렇게 나옵니다.

(0(1101)1((0011)(0111)1(1110))


 그림으로 보신다면 왼쪽과 같은 형태로 압축하는 것입니다. 알고리즘은 이미지의 구역을 4개로 나눈 후, 같은 숫자로 구성돼 있다면 하나로 묶어버리고 그렇지 않으면 다시 구역을 4개로 나누는 형태로 진행됩니다.








소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<stdio.h>
#include<malloc.h>
#include<memory.h>
 
void quadTree(char** data, int beginX, int beginY, int size)
{
 
    // 병합 가능한지 체크---------------------------------
    char beginData = data[beginY][beginX];
    bool isCombinable = true;
    for (int y = beginY; y < beginY + size; ++y) {
        for (int x = beginX; x < beginX + size; ++x) {
            if (beginData != data[y][x])
            {
                isCombinable = false;
                break;
            }
        }
        if (isCombinable == false)
            break;
    }
    //---------------------------------------------------
 
    // 병합이 가능하면------------------------------------
    if (isCombinable)
    {
        printf("%c", beginData);
        return;
    }
 
    // 그게 아니라면 4개로 분할---------------------------
    int halfSize = (int)(size * 0.5f);
    printf("(");
    quadTree(data, beginX, beginY, halfSize);
    quadTree(data, beginX + halfSize, beginY, halfSize);
    quadTree(data, beginX, beginY + halfSize, halfSize);
    quadTree(data, beginX + halfSize, beginY + halfSize, halfSize);
    printf(")");
}
 
void main()
{
    int dataSize = 0;
    printf("데이터의 크기를 입력해주세요(2의 승수):");
    scanf("%d", &dataSize);
 
    // 메모리 할당
    char** data = (char**)malloc(sizeof(char*)*dataSize);
    for (int i = 0; i < dataSize; ++i)
    {
        data[i] = (char*)malloc(sizeof(char)*(dataSize + 1));
        memset(data[i], 0, sizeof(data[i]));
    }
 
    printf("데이터를 입력해주세요.\n");
    for (int i = 0; i < dataSize; ++i)
    {
        scanf("%s", data[i]);
    }
    
    // 분할
    quadTree(data, 0, 0, dataSize);
 
    for (int i = 0; i < dataSize; ++i)
    {
        free(data[i]);
    }
    free(data);
}
cs


응용

 충돌 알고리즘도 이와 같은 방법으로 최적화를 진행하게 됩니다. 왼쪽 이미지와 같이 오브젝트들의 구역을 나눈 후, 인접한 영역의 오브젝트들끼리만 충돌처리 알고리즘을 진행합니다.


'Notes > Algorithm' 카테고리의 다른 글

도형 충돌, 분할 축 정리 (Separating Axis Theorem)  (0) 2016.06.26
Graham scan 알고리즘 (Convex hull 추출)  (0) 2016.06.10
[자료구조] 이진 힙(binary heap) 그리고 힙 정렬(heap sort)  (0) 2016.06.07
하노이 탑(Tower of Hanoi)  (0) 2016.05.24
병합 정렬 (Merge Sort)  (0) 2016.05.15


참고 : www.dyn4j.org/2010/01/sat/



분할 축 정리(Separating Axis Theorem)란?

 분할축 정리(Separating Axis Theorem, 이하 SAT)란 "두 물체를 투영한 구간이 겹치지 않는 축이 하나라도 존재한다면 두 물체는 교차하지 않은 상태이다."라는 명제에 관한 정리입니다. 그리고 이것을 통해 충돌을 검출해내는 알고리즘을 만들것입니다. 충돌 유무, 충돌 위치, 충돌 량을 검출하며 2D물리 시뮬레이션에서 일반적으로 사용하게 됩니다.


(http://chessire.tistory.com/entry/%EC%84%A0%EB%B6%84%EA%B3%BC-%EC%84%A0%EB%B6%84%EC%9D%98-%EC%B6%A9%EB%8F%8C-%EC%A0%95%EB%A6%AC)

 기본적인 원리는 선분충돌과 같습니다. 두 도형의 모든 선분의 직교선분에 각 도형을 투영하여 교차여부를 검출하는 방식입니다.




아래는 코드입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
Shape = function(count, size, rotation)
{
    var self = this;
 
    PIXI.Container.call(this);
 
    var vertices = [];
    var shape = new PIXI.Graphics();
    
    shape.beginFill(Math.random() * 0xffffff);
    shape.lineStyle(2, 0x101010, 1);
 
    var angle = 2 * Math.PI / count;
    for(var i = 0 ; i < count ; ++i)
    {
        var x = Math.cos(rotation + angle * i) * size;
        var y = Math.sin(rotation + angle * i) * size;
 
        vertices.push(new PIXI.Vector(x, y));
 
        if(i == 0)
            shape.moveTo(x, y);
        else
            shape.lineTo(x, y);
    }
    shape.lineTo(vertices[0].x, vertices[0].y);
    shape.endFill();
 
    this.addChild(shape);
 
    this.getVertexPosition = function(index)
    {
        return vertices[index].clone().add(new PIXI.Vector(this.position.x, this.position.y));
    }
 
    this.getAxes = function()
    {
        var axes = [];
        for(var i = 0 ; i < vertices.length ; ++i)
        {
            var vec = vertices[i+1 >= vertices.length ? 0 : i+1].clone().sub(vertices[i]);
            axes.push(new PIXI.Vector(vec.y, -vec.x).normalize());
        }
        
        return axes;
    }
 
    this.project = function(axis)
    {
        var posit = new PIXI.Vector(self.position.x, self.position.y);
        var min = axis.dot(vertices[0].clone().add(posit));
        var max = min;
        for(var i = 1 ; i < vertices.length ; ++i)
        {
            var p = axis.dot(vertices[i].clone().add(posit));
            if(min > p)
                min = p;
            if(max < p)
                max = p;
        }
 
        return new Projection(min, max);
    }
}
cs





1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
Projection = function(min, max)
{
    this.min = min;
    this.max = max;
}
 
Projection.prototype.constructor = Projection;
Projection.prototype.isOverlap = function(proj)
{
    if (proj.min < this.max && this.min < proj.max)
        return true;
 
    return false;
}
 
Projection.prototype.getOverlap = function(proj)
{
    var left = this.getOverlapLeft(proj);
    var right = this.getOverlapRight(proj);
 
    return right - left;
}
 
Projection.prototype.getOverlapLeft = function(proj)
{
    return this.min < proj.min ? proj.min : this.min;
}
 
Projection.prototype.getOverlapRight = function(proj)
{
    return this.max > proj.max ? proj.max : this.max;
}
 
Projection.prototype.getOverlapCenter = function(proj)
{
    var left = this.getOverlapLeft(proj);
    var right = this.getOverlapRight(proj);
 
    return left + (right - left) * 0.5;
}
 
cs




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
function update()
{
    var axesA = shapeA.getAxes();
    var axesB = shapeB.getAxes();
 
    var overlap = 9999;
    var smallest = null;
 
    var overlapDistance = 9999;
    var isA = false;
 
    var isCollide = true;
 
    for(var k = 0 ; k < axesA.length ; ++k)
    {
        var projA = shapeA.project(axesA[k]);
        var projB = shapeB.project(axesA[k]);
        if(projA.isOverlap(projB) === false)
            isCollide = false;
        else
        {
            var o = projA.getOverlap(projB);
            if(overlap - 0.00001 <= o && o <= overlap + 0.00001)
            {
                var dist = Math.abs(projA.getOverlapCenter(projB) - axesA[k].dot(shapeA.getVertexPosition(k)));
 
                if(overlapDistance > dist)
                {
                    overlap = o;
                    smallest = axesA[k];
                    overlapDistance = dist;
                    isA = true;
                }                        
            }
            else if(overlap > o)
            {
                overlap = o;
                smallest = axesA[k];
                overlapDistance = Math.abs(projA.getOverlapCenter(projB) - axesA[k].dot(shapeA.getVertexPosition(k)));
                isA = true;
            }
        }
    }
 
    for(var k = 0 ; k < axesB.length ; ++k)
    {
        var projA = shapeA.project(axesB[k]);
        var projB = shapeB.project(axesB[k]);
        if(projA.isOverlap(projB) === false)
            isCollide = false;
        else
        {
            var o = projA.getOverlap(projB);
            if(overlap - 0.00001 <= o && o <= overlap + 0.00001)
            {
                var dist = Math.abs(projA.getOverlapCenter(projB) - axesB[k].dot(shapeB.getVertexPosition(k)));
 
                if(overlapDistance > dist)
                {
                    overlap = o;
                    smallest = axesB[k];
                    overlapDistance = dist;
                    isA = false;
                }
            }
            else if(overlap > o)
            {
                overlap = o;
                smallest = axesB[k];
                overlapDistance = Math.abs(projA.getOverlapCenter(projB) - axesB[k].dot(shapeB.getVertexPosition(k)));
                isA = false;
            }
        }
    }
 
    if(isCollide)
    {
        smallest.multiplyScalar(overlap);
        if (shapeA.dragging ^ isA)
            smallest.multiplyScalar(-1);
 
        if(shapeA.dragging)
        {
            shapeB.position.x += smallest.x;
            shapeB.position.y += smallest.y;
        }
        else
        {
            shapeA.position.x += smallest.x;
            shapeA.position.y += smallest.y;
        }
    }
}
cs



'Notes > Algorithm' 카테고리의 다른 글

쿼드트리(Quad tree)  (0) 2017.11.14
Graham scan 알고리즘 (Convex hull 추출)  (0) 2016.06.10
[자료구조] 이진 힙(binary heap) 그리고 힙 정렬(heap sort)  (0) 2016.06.07
하노이 탑(Tower of Hanoi)  (0) 2016.05.24
병합 정렬 (Merge Sort)  (0) 2016.05.15
 (원래 기준점은 최하단 왼쪽 점을 고르게 되지만 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을 이루고 있는 점을 이어줍니다.

코드 설명
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
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);
}
cs


(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의 오른쪽에 있다고 할 수 있습니다.

'Notes > Algorithm' 카테고리의 다른 글

쿼드트리(Quad tree)  (0) 2017.11.14
도형 충돌, 분할 축 정리 (Separating Axis Theorem)  (0) 2016.06.26
[자료구조] 이진 힙(binary heap) 그리고 힙 정렬(heap sort)  (0) 2016.06.07
하노이 탑(Tower of Hanoi)  (0) 2016.05.24
병합 정렬 (Merge Sort)  (0) 2016.05.15

참고

 - https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)


소스코드

heap.zip

사용하실 때, 댓글을 남겨주세요.


정의

 힙은 2진 힙(바이너리 힙)이라고도 부르며 최댓값과 최솟값 찾기 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조로써 다음과 같은 힙 속성(property)을 만족합니다.

 - A가 B의부모노드(parent node)이면 A의 키(key)값과 B의 키 값 사이에는 대소관계가 성립한다.


최대 힙

 - 부모노드의 키값이 자식 노드의 키값보다 항상 큰 힙


최소 힙

 - 부모노드의 키값이 자식 노드의 키값보다 항상 작은 힙


형제 사이에는 대소관계가 정해지지 않습니다.


(Max heap 이미지입니다.)



Push

 힙에 값을 추가하는 함수입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
this.push = function(value)
{
    arr[count] = value;
    var child = count;
 
    while(child > 0)
    {
        var parent = Math.floor((child + 1) * 0.5) - 1;
        if(compare(arr[child], arr[parent]))
        {
            swap(parent, child);
            child = parent;
        }
        else
            break;
    }
 
    ++count;
}
cs


규칙

  1. 마지막에 값을 추가합니다.
  2. 부모와 비교하여 부모보다 크면(최소힙은 부모보다 작으면) 부모와 swap합니다.
  3. 부모보다 작을때까지 혹은 최상단(0번 인덱스)이 될 때까지(최소힙은 부모보다 클때까지 2번을 반복합니다.


Pop

 힙에서 값을 가져오는 함수입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
this.pop = function()
{
    if(count === 0)
        return null;
 
    var ret = arr[0];
    arr[0] = arr[count-1];
 
    --count;
 
    var node = 0;
    while(true)
    {
        var child1 = node * 2 + 1;
        var child2 = child1 + 1;
 
        var swapIdx = node;
        if(child1 < count && compare(arr[child1], arr[swapIdx]))
            swapIdx = child1;
        if(child2 < count && compare(arr[child2], arr[swapIdx]))
            swapIdx = child2;
 
        if(swapIdx !== node)
        {
            swap(node, swapIdx);
            node = swapIdx;
        }
        else
            break;
    }
 
    return ret;
}
cs

규칙

  1. 최상단(0번인덱스)를 빼냅니다.
  2. 최상단에 배열의 마지막 데이터를 집어넣습니다.
  3. 자식과 비교하여 자신보다 크면 교체(최소힙일 경우 작으면)합니다.(둘 다 클 경우, 가장 큰 자식과 교체합니다.)
  4. 자식보다 작아질때(최소힙일 경우 커질때)까지 혹은 자식이 없어질 때까지 3번을 반복합니다.
이렇게 추출할 경우, 정렬된 데이터를 추출해낼 수 있습니다.


추가적으로

 보편적으로 compare함수를 생성자에서 전달받아 사용합니다.

 예를들어 int나 float이 아닌 사용자정의 형일 경우, 크거나 작은것을 비교할 수 없습니다. 그렇기 때문에 사용자정의 compare함수를 전달받아 사용하게 됩니다.



힙 정렬

 위에서 설명드린 힙을 이용해 정렬하는 알고리즘입니다.

제자리 정렬 알고리즘에 의 시간복잡도를 가지고 있습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
{
    // (1) 힙 형태로 정렬
    for (var i = Math.floor(this.nodes.length * 0.5) - 1 ; i >= 0 ; --i)
    {
        var parent = i;
        while(true)
        {
            var child1 = parent * 2 + 1;
            var child2 = child1 + 1;
 
            var changeIndex = parent;
            if (child1 < this.nodes.length &&
                compare(this.nodes[child1], this.nodes[changeIndex]))
                changeIndex = child1;
            if (child2 < this.nodes.length &&
                compare(this.nodes[child2], this.nodes[changeIndex]))
                changeIndex = child2;
 
            if(changeIndex !== parent)
            {
                this.swap(parent, changeIndex);
                parent = changeIndex;
            }
            else
                break;
        }
    }
 
    // (2) 최상위 값을 빼와서 뒤에서부터 순서대로 삽입
    for (var i = 0 ; i < this.nodes.length ; ++i)
    {
        var last = this.nodes.length - 1 - i;
        var front = this.pop(last);
 
        this.nodes[last] = front;
        this.nodes[last].value.position.x = 5 + last * 55;
        this.nodes[last].value.position.y = 600;
    }
}
 
cs


(1) 힙 형태로 정렬

 일단 배열을 힙형태로 정렬을 해야합니다.

이때, 정렬은 자식을 가지고 있는 Math.floor(this.nodes.length * 0.5) - 1번째 인덱스부터 역순으로 정렬해 나갑니다.


(2) 최상위 값을 빼와서 뒤에서부터 순서대로 삽입

 제자리 정렬을 해야하기 때문에 힙용 배열을 따로 만드는 것이 아니라 맨 첫번째 있는 것을 pop하여 끝에 집어넣습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
this.prototype.pop = function(last)
{
    var ret = this.nodes[0];
 
    this.nodes[0] = this.nodes[last];
    this.nodes[0].value.position.x = 5;
    this.nodes[0].value.position.y = 600;
 
    if(last <= 1)
        return ret;
 
    var parent = 0;
    while(true)
    {
        var child1 = parent * 2 + 1;
        var child2 = child1 + 1;
 
        var changeIndex = parent;
        if (child1 < last &&
            compare(this.nodes[child1], this.nodes[changeIndex]))
            changeIndex = child1;
        if (child2 < last &&
            compare(this.nodes[child2], this.nodes[changeIndex]))
            changeIndex = child2;
 
        if(changeIndex !== parent)
        {
            this.swap(parent, changeIndex);
            parent = changeIndex;
        }
        else
            break;
    }
 
    return ret;
}
 
cs


pop함수는 위와 동일한 형태로 다른 부분은 last를 인자로 받아오는 것 외에는 없습니다.

'Notes > Algorithm' 카테고리의 다른 글

도형 충돌, 분할 축 정리 (Separating Axis Theorem)  (0) 2016.06.26
Graham scan 알고리즘 (Convex hull 추출)  (0) 2016.06.10
하노이 탑(Tower of Hanoi)  (0) 2016.05.24
병합 정렬 (Merge Sort)  (0) 2016.05.15
선택 정렬 (Select Sort)  (0) 2016.05.11
Javascript로 구현한 Hanoi tower


하노이 탑은 세개의 기둥과 n개의 크기가 다른 원판이 크기가 큰 순서대로 첫번째 기둥에 꽂혀있습니다. 그리고 다음의 규칙에 맞게 세번째 기둥에 옮기면 되는 퍼즐의 일종이다.
첫번째, 한번에 하나의 원판을 옮길 수 있다.
두번째, 크기가 작은 원판 위에 큰 원판이 올 수 없다.

원판이 n개일 때, 번 이동하게 됩니다.

하노이 탑 설화
인도 베나레스에 있는 한 사원에는 세상의 중심을 나타내는 큰 돔이 있고 그 안에 세 개의 다이아몬드 바늘이 동판 위에 세워져 있습니다. 바늘의 높이는 1큐빗이고 굵기는 벌의 몸통만 합니다. 바늘 가운데 하나에는 신이 64개의 순금 원판을 끼워 놓았습니다. 가장 큰 원판이 바닥에 놓여 있고, 나머지 원판들이 점점 작아지며 꼭대기까지 쌓아 있습니다. 이것은 신성한 브라흐마의 탑입니다. 브라흐마의 지시에 따라 승려들은 모든 원판을 다른 바늘로 옮기기 위해 밤낮 없이 차례로 제단에 올라 규칙에 따라 원판을 하나씩 옮깁니다. 이 일이 끝날 때, 탑은 무너지고 세상은 종말을 맞이하게 됩니다.




알고리즘의 구성
기본적으로 하노이탑 알고리즘은 재귀호출을 이용하여 해결하는 구조입니다.

1
2
3
4
5
6
7
8
9
10
11
HanoiTower.prototype.move = function(count, from, by, to)
{
    if(count==1)
        this.columns[to].addNode(this.columns[from].pop());
    else
    {
        this.move(count-1, from, to, by);
        this.columns[to].addNode(this.columns[from].pop());
        this.move(count-1, by, from, to);
    }
}
cs


1
HanoiTower.prototype.move = function(count, from, by, to)
cs

 이 함수는 count만큼의 원판을 from기둥에서부터 to기둥까지 by기둥을 이용해서 옮기라는 함수입니다.


1
2
if(count==1)
    this.columns[to].addNode(this.columns[from].pop());
cs

 원판이 한개일때는 그냥 해당 장소로 옮기면 됩니다. column은 스택구조로 돼있고, 제일 위에 있는 것은 가장 작은 것이므로 어디로든 옮길 수 있습니다.


1
2
3
4
5
6
else
{
    this.move(count-1, from, to, by);
    this.columns[to].addNode(this.columns[from].pop());
    this.move(count-1, by, from, to);
}
cs

 이제 중요한 것은 위의 코드입니다.


1
this.move(count-1, from, to, by);
cs

일단 to로 이동을 시키려면 가장 큰 것(가장 아래에 있는 것)이 먼저 to기둥으로 들어가야하기 때문에 일단 그 위에 있는 것들을 by기둥으로 옮겨야 합니다. 그림으로 이해해주시면 좋을 것 같습니다.



1
this.columns[to].addNode(this.columns[from].pop());
cs

위에 있는 원판들의 이동이 끝났으면 가장 아래에 있는 원판을 To원판으로 옮겨줍니다.



1
this.move(count-1, by, from, to);
cs

그럼 이제 by로 옮겨놨던 원판들을 to로 옮겨줍니다.


이렇게 되면 아래의 그림처럼 이동이 완료되는 형태입니다.


 이미지에서는 여러개를 묶어서 이동하는 것처럼 표현했지만, 그런것이 아니라 해당 묶음을 재귀호출을 통해 1개 단위로 거슬러 올라가서 이동하는 형태입니다.



'Notes > Algorithm' 카테고리의 다른 글

Graham scan 알고리즘 (Convex hull 추출)  (0) 2016.06.10
[자료구조] 이진 힙(binary heap) 그리고 힙 정렬(heap sort)  (0) 2016.06.07
병합 정렬 (Merge Sort)  (0) 2016.05.15
선택 정렬 (Select Sort)  (0) 2016.05.11
거품 정렬 (Bubble Sort)  (0) 2016.05.08
Javascript로 구현한 Merge sort


오늘은 분할 정복 알고리즘의 기초인 MergeSort에 대해 알아보겠습니다.

MergeSort는 원소의 개수가 1개가 될때까지 나눈 후, 역순으로 2개의 그룹을 병합 정렬해 가는 알고리즘입니다. 시간 복잡도는 로 원소들의 상태에 영향을 받지 않고 안정적으로 정렬하며 정렬 전의 순서와 정렬 후의 순서가 동일함을 보장하는 stable sort입니다. 하지만 원소 개수만큼의 임시 배열을 만들어 줘야하는 단점이 있습니다.


오늘은 동영상으로 어떻게 병합정렬이 진행되는지 봅시다.



재귀로 작성한 코드

1
2
3
4
5
6
7
8
9
10
11
12
MergeSort.prototype.mergeSort = function(first, last)
{
    if(first < last)
    {
        var mid = Math.floor((last + first) * 0.5);
        this.mergeSort(first, mid);
        this.mergeSort(mid + 1, last);
 
        this.merge(first, mid, last);
    }
}
 
cs

5~6번째 줄은 앞부분과 뒷부분으로 나누는 부분입니다.

해당 함수에서는 또 앞부분과 뒷부분으로 나누면서 first<last 될때까지 나누게 될 것입니다.

그렇게 나뉘면 작은 부분부터 차례대로 merge()함수를 실행하며 올라올 것 입니다.

소그룹 정렬 => 중그룹 정렬 => 대그룹 정렬

위에 보이는 동영상처럼요.


두 그룹을 병합하는 부분(first ~ mid, mid+1 ~ last)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
MergeSort.prototype.merge = function(first, mid, last)
{
    var a = first;
    var b = mid + 1;
 
    for(var i = first ; i <= last ; ++i)
    {
        if(a > mid)
        {
            this.tempArr[i] = this.nodes[b];
            b += 1;
            continue;
        }
        else if(b > last)
        {
            this.tempArr[i] = this.nodes[a];
            a += 1;
            continue;
        }
 
 
        if(this.nodes[a].value.size < this.nodes[b].value.size)
        {
            this.tempArr[i] = this.nodes[a];
            a += 1;
        }
        else
        {
            this.tempArr[i] = this.nodes[b];
            b += 1;
        }
    }
 
    for(var i = first ; i <= last ; ++i)
    {
        this.nodes[i] = this.tempArr[i];
        this.nodes[i].value.x = 5 + i * 55;
    }
}
 
cs

두 그룹의 병합은 아주 간단합니다.

각 그룹의 첫번째 인자를 비교하여 정렬 순서대로 미리 준비한 임시 배열에 넣어줍니다.

배열에 넣은 그룹은 인덱스를 1상승시킵니다.

한쪽 그룹에 더 이상 비교할 게 없다면 나머지 한쪽 그룹을 순서대로 넣어줍니다.

모든 그룹을 임시 배열에 넣어줬다면 그것을 현재 배열에 적용합니다.


위 코드에서 임시배열은 tempArr이고, 현재 배열은 nodes입니다.

a는 first ~ mid 그룹 인덱스고, b는 mid+1 ~ last 그룹 인덱스입니다.


조심할 부분이 있다면 해당 코드는 자바스크립트라는 점입니다.

자바스크립트는 노드를 그대로 사용하면 값을 복사하기 때문에 상당히 비효율적입니다. 그래서 해당 노드를 object에 넣어서 사용해줬습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
MergeSort.prototype.createNodes = function()
{
    this.nodes = [];
    for(var i = 0 ; i < this.count ; ++i)
    {
        var node = new SortNode(i, Math.ceil(Math.random() * this.maxSize) + 1);
        node.position.x = 5 + i * 55;
        node.position.y = 600;
        this.addChild(node);
 
        this.nodes.push({value:node});
    }
}
 
cs

11번째 줄을 보시면 nodes라는 array에 {value:node}가 보이실겁니다. 이렇게 사용하시면 call by reference로 사용할 수 있다고 합니다.


For문으로 작성한 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
MergeSort.prototype.sort = function*()
{
    var stack = [];
    stack.push([0, this.count-1]);
 
    for(var i = 0 ; i < stack.length ; ++i)
    {
        var lastData = stack[i];
 
        var first = lastData[0];
        var last = lastData[1];
 
        var mid = Math.floor((last + first) * 0.5);
        if(first < mid)
            stack.push([first, mid]);
        if(mid + 1 < last)
            stack.push([mid + 1, last]);
    }
 
    while(stack.length !== 0)
    {
        var data = stack.pop();
 
        this.setGroupLine(data[0], data[1]);
        yield true;
        var mid = Math.floor((data[0] + data[1]) * 0.5);
        this.merge(data[0], mid, data[1]);
        yield true;
    }
 
    this.groupLine.clear();
    yield false;
}
 
cs

위에 코드는 재귀가 아닌 For문으로 작성한 코드입니다.

작성한 이유는 다름아닌 저 동영상을 generator를 이용해 만들고 있기 때문입니다!

코드를 보시면 재귀하는 부분을 stack을 이용해 해결하였습니다. 차례대로 2등분하여 쌓아줍니다.

그리고 마지막부터 역순으로 병합해주는 형태입니다.

'Notes > Algorithm' 카테고리의 다른 글

[자료구조] 이진 힙(binary heap) 그리고 힙 정렬(heap sort)  (0) 2016.06.07
하노이 탑(Tower of Hanoi)  (0) 2016.05.24
선택 정렬 (Select Sort)  (0) 2016.05.11
거품 정렬 (Bubble Sort)  (0) 2016.05.08
선분 교점 구하기, 선분 충돌(line segment collision)  (1) 2016.04.25
Javascript로 구현한 Select sort


주어진 배열 이외에 다른 저장공간을 필요로 하지 않는 제자리 정렬 알고리즘의 하나로 시간 복잡도는  입니다. 어떤 상황에서든 에 비례하는 시간이 걸립니다.



1 5 6 8 7 4 3 9 2


1 5 6 8 7 4 3 9 2

1 2 6 8 7 4 3 9 5


1 2 6 8 7 4 3 9 5

1 2 3 8 7 4 6 9 5


1 2 3 8 7 4 6 9 5

1 2 3 4 7 8 6 9 5


1 2 3 4 7 8 6 9 5

1 2 3 4 5 8 6 9 7


1 2 3 4 5 8 6 9 7

1 2 3 4 5 6 8 9 7


1 2 3 4 5 6 8 9 7

1 2 3 4 5 6 7 9 8


1 2 3 4 5 6 7 9 8

1 2 3 4 5 6 7 8 9


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
for(var i = 0 ; i < this.nodes.length - 1 ; ++i)
{
    var min = i;
 
    for(var j = i + 1 ; j < this.nodes.length ; ++j)
    {
        if(this.nodes[min].getSize() > this.nodes[j].getSize())
            min = j;
    }
 
    if(min == i)
        continue;
 
    var temp = this.nodes[i];
    this.nodes[i] = this.nodes[min];
    this.nodes[min] = temp;
 
    this.nodes[i].x = 5 + i * 55;
    this.nodes[min].x = 5 + min * 55;
}
 
cs

안쪽 포문에서는 그 자리에 해당하는 최소값을 찾고 바깥쪽 포문에서는 딱 한번 swap 해줍니다. swap이 조금 일어나기때문에 거품정렬에 비해 속도가 빠릅니다. (그래도 ...)


'Notes > Algorithm' 카테고리의 다른 글

[자료구조] 이진 힙(binary heap) 그리고 힙 정렬(heap sort)  (0) 2016.06.07
하노이 탑(Tower of Hanoi)  (0) 2016.05.24
병합 정렬 (Merge Sort)  (0) 2016.05.15
거품 정렬 (Bubble Sort)  (0) 2016.05.08
선분 교점 구하기, 선분 충돌(line segment collision)  (1) 2016.04.25
Javascript로 구현한 Bubble sort



거품 정렬이란?
인접한 두 원소를 비교하여 정렬하는 방법입니다.
거품이 수면위로 떠오르는 것 처럼 보여서 붙혀진 이름이라고 합니다.
시간 복잡도는  입니다.


예시

1 5 6 8 7 4 3 9 2

1 5 6 8 7 4 3 9 2

1 5 6 8 7 4 3 9 2

1 5 6 8 7 4 3 9 2

1 5 6 8 7 4 3 9 2

1 5 6 7 8 4 3 9 2

1 5 6 7 8 4 3 9 2

1 5 6 7 4 8 3 9 2

1 5 6 7 4 8 3 9 2

1 5 6 7 4 3 8 9 2

1 5 6 7 4 3 8 9 2

1 5 6 7 4 3 8 9 2

1 5 6 7 4 3 8 2 9   첫번째 이터레이션 종료


1 5 6 7 4 3 8 2 9

1 5 6 7 4 3 8 2 9

1 5 6 7 4 3 8 2 9

1 5 6 7 4 3 8 2 9

1 5 6 4 7 3 8 2 9

1 5 6 4 7 3 8 2 9

1 5 6 4 3 7 8 2 9

1 5 6 4 3 7 8 2 9

1 5 6 4 3 7 8 2 9

1 5 6 4 3 7 2 8 9 두번째 이터레이션 종료


1 5 6 4 3 7 2 8 9

1 5 6 4 3 7 2 8 9

1 5 6 4 3 7 2 8 9

1 5 4 6 3 7 2 8 9

1 5 4 6 3 7 2 8 9

1 5 4 3 6 7 2 8 9

1 5 4 3 6 7 2 8 9

1 5 4 3 6 7 2 8 9

1 5 4 3 6 2 7 8 9 세번째 이터레이션 종료


1 5 4 3 6 2 7 8 9

1 5 4 3 6 2 7 8 9

1 4 5 3 6 2 7 8 9

1 4 5 3 6 2 7 8 9

1 4 3 5 6 2 7 8 9

1 4 3 5 6 2 7 8 9

1 4 3 5 6 2 7 8 9

1 4 3 5 2 6 7 8 9 네번째 이터레이션 종료


1 4 3 5 2 6 7 8 9

1 4 3 5 2 6 7 8 9

1 3 4 5 2 6 7 8 9

1 3 4 5 2 6 7 8 9

1 3 4 5 2 6 7 8 9

1 3 4 2 5 6 7 8 9 다섯번째 이터레이션 종료


1 3 4 2 5 6 7 8 9

1 3 4 2 5 6 7 8 9

1 3 4 2 5 6 7 8 9

1 3 2 4 5 6 7 8 9 여섯번째 이터레이션 종료


1 3 2 4 5 6 7 8 9

1 3 2 4 5 6 7 8 9

1 2 3 4 5 6 7 8 9 일곱번째 이터레이션 종료


1 2 3 4 5 6 7 8 9 여덟번째 이터레이션 종료


이터레이션 단위에서는 작은 수들은 앞으로 한칸씩 밀려오고 비교 단위에서는 큰 수들이 뒤로 한칸씩 밀려나는 형태입니다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(var i = 0 ; i < this.nodes.length - 1 ; ++i)
{
    for(var j = 0 ; j < this.nodes.length - 1 - i ; ++j)
    {
        if(this.nodes[j].getSize() > this.nodes[j+1].getSize())
        {
            var temp = this.nodes[j];
            this.nodes[j] = this.nodes[j+1];
            this.nodes[j+1] = temp;
 
            this.nodes[j].x = 5 + j * 55;
            this.nodes[j+1].x = 5 + (j+1) * 55;
        }
    }
}
 
cs


 가장 큰 값을 뒤로 밀어낸다고 보시면 됩니다. 뒤에서 부터 정렬된 값이 쌓이기 때문에 3번째 줄의 for문은 length - 1 - i만큼만 돌게 됩니다. length - 1은 j와 j+1을 비교하기 때문에 넣어줍니다.



'Notes > Algorithm' 카테고리의 다른 글

[자료구조] 이진 힙(binary heap) 그리고 힙 정렬(heap sort)  (0) 2016.06.07
하노이 탑(Tower of Hanoi)  (0) 2016.05.24
병합 정렬 (Merge Sort)  (0) 2016.05.15
선택 정렬 (Select Sort)  (0) 2016.05.11
선분 교점 구하기, 선분 충돌(line segment collision)  (1) 2016.04.25
Javascript로 구현한 선분충돌



투영을 통한 선분충돌

1번

2번

하지만 2번 이미지에서 초록 선분도 투영 결과는 같지만 충돌하지는 않은 상태입니다.
그렇기 때문에 파랑 선분의 직교 벡터에도 똑같이 투영을 하여 같은 결과가 나오는지 확인해주어야 합니다.


3번

3번 이미지는 파랑 선분의 직교 벡터인 파랑 직교 벡터에 투영을 한 결과입니다.
보라 선분은 아까와 같은 결과이지만 초록 선분은 그렇지 않습니다.


예외 : 두 선분의 벡터가 같은 방향을 가지고 있을 때,

4번


4번 이미지는 두 선분의 벡터가 같은 방향을 가지고 있을 때를 보여주는 이미지입니다.
해당 경우에는 직교 벡터에서 한 점에 투영이 됩니다.
이 경우에는 선분의 벡터에 투영하여 빨강 선분의 각 점 중 하나라도 파랑 선분의 사이에 있다면 충돌 된 것입니다.

보라 선분의 직교 벡터인 보라 직교벡터에 세 점을 투영하면 위와 같은 결과가 나옵니다.


이제 코드를 보겠습니다.

1
2
3
4
5
6
7
var myP1 = new PIXI.Vector(this.points[0].position.x, this.points[0].position.y);
var myP2 = new PIXI.Vector(this.points[1].position.x, this.points[1].position.y);
var otherP1 = new PIXI.Vector(other.points[0].position.x, other.points[0].position.y);
var otherP2 = new PIXI.Vector(other.points[1].position.x, other.points[1].position.y);
 
var myN = new PIXI.Vector(myP2.y - myP1.y, myP1.x - myP2.x);    
var otherN = new PIXI.Vector(otherP2.y - otherP1.y, otherP1.x - otherP2.x);
cs

각 네점은 myP1, myP2, otherP1, otherP2 입니다.

myN과 otherN이 각 선분의 직교벡터입니다. 2차원 벡터의 직교벡터를 구하는 방법은 복소평면에서의 회전을 참고해주시면 좋을 것 같습니다.


1
2
3
4
5
6
7
var myDot = myN.dot(myP1);
var myDotA = myN.dot(otherP1) - myDot;
var myDotB = myN.dot(otherP2) - myDot;
 
if(myDotA * myDotB > 0)
    return false;
 
cs

myN 벡터에 각 점을 투영하여 my가 other의 각 점 사이에 있는지 체크해줍니다.

투영은 벡터의 내적을 통해 얻을 수 있습니다.


1
2
3
4
5
6
7
var otherDot = otherN.dot(otherP1);
var otherDotA = otherN.dot(myP1) - otherDot;
var otherDotB = otherN.dot(myP2) - otherDot;
 
if(otherDotA * otherDotB > 0)
    return false;
 
cs

똑같이 otherN벡터에 각 점을 투영하여 other가 my의 각 점 사이에 있는지 체크해줍니다.


두 선분의 벡터가 같은 방향을 가지고 있을 때 입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// when vector same,
if(myDotA == 0 && myDotB == 0)
{
    var dir = myP2.clone().sub(myP1);
 
    var myP1Dot = dir.dot(myP1);
    var myP2Dot = dir.dot(myP2);
    var otherP1Dot = dir.dot(otherP1);
    var otherP2Dot = dir.dot(otherP2);
 
    if((myP1Dot - otherP1Dot) * (myP1Dot - otherP2Dot) < 0)
    {
        joint.x = myP1.x;
        joint.y = myP1.y;
        return true;
    }
    else if((myP2Dot - otherP1Dot) * (myP2Dot - otherP2Dot) < 0)
    {
        joint.x = myP2.x;
        joint.y = myP2.y;
        return true;
    }
}
 
cs

my의 방향 벡터에 네 점을 투영하여 충돌을 검출합니다.


마지막으로 충돌 지점을 계산합니다.

1
2
3
4
5
6
7
8
var ratio = Math.abs(myDotA) / Math.abs(myDotB - myDotA);
 
var bPoint1 = otherP1.clone();
var bDelta = otherP2.clone().sub(otherP1).multiplyScalar(ratio);
var result = bPoint1.add(bDelta);
joint.x = result.x;
joint.y = result.y;
 
cs

투영한 점의 비율을 계산하여 충돌 지점을 계산할 수 있습니다.


아래는 전체 코드입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
SegmentLine.prototype.getJoint = function (other, joint)
{
    var myP1 = new PIXI.Vector(this.points[0].position.x, this.points[0].position.y);
    var myP2 = new PIXI.Vector(this.points[1].position.x, this.points[1].position.y);
    var otherP1 = new PIXI.Vector(other.points[0].position.x, other.points[0].position.y);
    var otherP2 = new PIXI.Vector(other.points[1].position.x, other.points[1].position.y);
 
    var myN = new PIXI.Vector(myP2.y - myP1.y, myP1.x - myP2.x);    
    var otherN = new PIXI.Vector(otherP2.y - otherP1.y, otherP1.x - otherP2.x);

    var myDot = myN.dot(myP1);
    var myDotA = myN.dot(otherP1) - myDot;
    var myDotB = myN.dot(otherP2) - myDot;
 
    // when vector same,
    if(myDotA == 0 && myDotB == 0)
    {
        var dir = myP2.clone().sub(myP1);
        var myP1Dot = dir.dot(myP1);
        var myP2Dot = dir.dot(myP2);
        var otherP1Dot = dir.dot(otherP1);
        var otherP2Dot = dir.dot(otherP2);
        if((myP1Dot - otherP1Dot) * (myP1Dot - otherP2Dot) < 0)
        {
            joint.x = myP1.x;
            joint.y = myP1.y;
            return true;
        }
        else if((myP2Dot - otherP1Dot) * (myP2Dot - otherP2Dot) < 0)    
        {
            joint.x = myP2.x;
            joint.y = myP2.y;
            return true;
        }
    }
 
    if(myDotA * myDotB > 0)
        return false;
 
    var otherDot = otherN.dot(otherP1);
    var otherDotA = otherN.dot(myP1) - otherDot;    
    var otherDotB = otherN.dot(myP2) - otherDot;    
 
    if(otherDotA * otherDotB > 0)
        return false;
 
     // calculate intersection
    var ratio = Math.abs(myDotA) / Math.abs(myDotB - myDotA);
    var bPoint1 = otherP1.clone();
    var bDelta = otherP2.clone().sub(otherP1).multiplyScalar(ratio);
    var result = bPoint1.add(bDelta);
    joint.x = result.x;
    joint.y = result.y;
    return true;
}
cs




'Notes > Algorithm' 카테고리의 다른 글

[자료구조] 이진 힙(binary heap) 그리고 힙 정렬(heap sort)  (0) 2016.06.07
하노이 탑(Tower of Hanoi)  (0) 2016.05.24
병합 정렬 (Merge Sort)  (0) 2016.05.15
선택 정렬 (Select Sort)  (0) 2016.05.11
거품 정렬 (Bubble Sort)  (0) 2016.05.08

+ Recent posts

티스토리툴바