[카테고리:] Algorithms

군집화 알고리즘(Clustering Algorithm) 중 K-Means 가 있습니다. K-Means 알고리즘에 대한 설명 이전에, 실제로 구현된 K-Means 알고리즘에 대한 실행 결과를 바로 설명하면서 자연스럽게 K-Means 알고리즘이 무엇인지 설명하겠습니다. 아래는 K-Means 알고리즘을 실행하기 위해 입력한 포인트 데이터입니다. SHP 파일을 통해 입력 받았습니다.

위의 이미지처럼 공간상에 무수히, 주관적 해석이긴 하지만 의미 없이 분포되어 있는 포인트들에 대해서 어떤 연관 관계에 대한 특성을 부여함으로써 몇개로 묶을 수 있는데요. 이처럼 묶는다라는 것을 그룹핑, 클러스터링이라고 합니다. K-Means 알고리즘에서 몇개(K개)로 묶을지를 지정하여 원하는 개수 만큼 클러스터링할 수 있습니다. 아래의 화면은 K-Means 알고리즘을 활용하여 12개의 그룹으로 공간상의 포인트를 묶은 결과입니다.

앞서 포인트를 그룹으로 묶을 때 어떤 관계에 대한 특성을 부여한다고 하였는데요. 위의 화면에서는 그 특성을 거리(Distance)로 하였습니다. 즉, 거리 상으로 가까운 포인트들을 그룹으로 묶는 것입니다.

이처럼 이미 확보한 수 많은 공간상의 데이터를 그룹핑하여 놓는다면, 새로운 포인트에 대해서 어느 그룹에 포함되는지에 대한 해석이 매우 빠르게 분류될 수 있습니다. 이미 확보한 데이터가 많으면 많을 수록, 새로운 데이터에 대한 해석이 보다 더 정확할 수 있겠죠.

아래는 K-Means 알고리즘을 구현한 C# 소스코드이며, 듀라맵(DuraMap-Xr)을 이용하여 K-Means 알고리즘에 필요한 포인트 데이터를 SHP 파일로부터 읽어 들이고 그 결과를 시각화 하였습니다.

Convex Hull은 볼록한 껍데기로.. 무수히 많은 포인트를 감싸는 볼록한 영역으로 정의할 수 있습니다. 입력 데이터인 포인트는 SHP 파일로부터 제공받아, 이를 듀라맵에서 그 결과를 표시하도록 하였습니다. 아래는 그 결과 화면입니다.

무수히 많은 작은 포인트를 감싸는 Convex Hull이 반투명한 빨간색 폴리곤으로 표시되어져 있습니다. 이러한 Convex-Hull에 대한 구현에 대해 C# 클래스로 정의했으며 아래와 같습니다.

using System;
using System.Collections.Generic;

namespace tstConvexHull
{
    public class ConvexHull
    {
        public class Point : IComparer
        {
            public double x;
            public double y;

            public Point()
            {
                x = 0.0;
                y = 0.0;
            }

            public Point(double x, double y)
            {
                this.x = x;
                this.y = y;
            }

            public int Compare(Point p1, Point p2)
            {
                if (p1.x == p2.x)
                {
                    return p1.y > p2.y ? 1 : p1.y < p2.y ? -1 : 0;
                }
                else
                {
                    return p1.x > p2.x ? 1 : p1.x < p2.x ? -1 : 0;
                }
            }
        }

        public static double Cross(Point O, Point A, Point B)
        {
            return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
        }

        public static Point[] Get(Point[] P)
        {
            if (P.Length > 1)
            {
                int n = P.Length, k = 0;
                Point[] H = new Point[2 * n];

                Array.Sort(P, new Point());

                for (int i = 0; i < n; ++i)
                {
                    while (k >= 2 && Cross(H[k - 2], H[k - 1], P[i]) <= 0)
                        k--;
                    H[k++] = P[i];
                }

                for (int i = n - 2, t = k + 1; i >= 0; i--)
                {
                    while (k >= t && Cross(H[k - 2], H[k - 1], P[i]) <= 0)
                        k--;
                    H[k++] = P[i];
                }

                if (k > 1)
                {
                    Point[] NewH = new Point[k - 1];
                    Array.Copy(H, NewH, k - 1);
                    H = NewH;
                }
                return H;
            }
            else if (P.Length <= 1)
            {
                return P;
            }
            else
            {
                return null;
            }
        }
    }
}

실제 위의 Convex-Hull 클래스에 대한 사용은 아래 코드와 같은데요. DuraMap-Xr에서 SHP 파일로부터 점 데이터를 읽어 입력 데이터를 구성하여 Convex-Hull을 실행하고 그 결과로 반투명 빨간색 폴리곤을 추가하는 코드 모두를 나타내고 있습니다.

XrMapLib.ShapeMapLayer lyr = axXr.Layers.GetLayerAsShapeMap("lyr");
XrMapLib.ShapeTable tbl = lyr.ShapeTable;
int cntRows = tbl.RowCount;

ConvexHull.Point[] pts = new ConvexHull.Point[cntRows];

for(int i=0; i
코드를 살짝 설명하면, 1~15번 코드는 SHP 파일로부터 포인트 데이터를 읽어와 Convex-Hull 알고리즘에 입력할 데이터를 준비하는 것이고, 17번 코드가 바로 Convex-Hull의 실행이며 19번 코드부터는 Convex-Hull의 결과를 그래픽 객체로 가시화시켜주는 코드들입니다.

	

3차원에서, 광원에 의한 물체 표면의 표현을 위해 표면에 수직인 법선 벡터를 고려하게 됩니다. 쉽게 생각해 보면, 물체를 구성하는 좌표에 대한 모델뷰 행렬(M)을 이용해 법선 벡터를 변환하는 것으로 충분할듯하지만 아래처럼 어파인(Affine) 변환 중 y축에 대한 크기 변환을 수행했을 경우, 법선 벡터를 모델뷰 행렬로 변환하면, 표면 벡터(S)와 법선 벡터(N)이 더 이상 수직이 아님을 쉽게 알 수 있습니다.

그렇다면 물체에 대해서 어떠한 어파인 변환을 수행하더라도 법선 백터의 고유한 특성, 즉 표면 벡터와 수직인 성질을 유지할 수 있을까하는 것에 대해 정리를 해 봅니다.

먼저 법선 벡터와 표면 벡터는 수직이므로 이 두 벡터의 내적은 0입니다. 즉, 아래와 같습니다.

물체는 모델뷰 행렬에 의해 변환됩니다. 즉, 물체의 표면 역시 모델뷰 행렬에 의해 정확히 변환됩니다. 모델뷰 행렬이 M, 표면 벡터를 S, 변환된 표면 벡터를 S’라고 하면 다음과 같습니다.

위와 같은 맥락으로, 법선 벡터 N이 법선 벡터로써의 특성을 유지하면서 새롭게 변환된 법선 벡터를 N’라고 할때, 법선 벡터로써의 특성을 유지하면서 변환해 주는 행렬, 즉 법선 행렬을 K라고 하면 다음과 같습니다.

법선 벡터의 특성, 즉 변환된 후의 표면 벡터인 S’와 법선 벡터인 N’는 수직이여야 하므로 다음과 같습니다.

S’=MS 그리고 N’=KN이라고 했으므로 바로 위의 식에 각각 대입하면 다음과 같습니다.

벡터의 기본 성질 중, 벡터의 내적의 결과는 첫번째 벡터의 전치에 의한 벡터의 단순 곱과 같으므로 위의 식은 아래와 같습니다.

벡터 곱에 대한 전치는 각 벡터의 전치에 대한 역순의 곱과 같으므로 다음의 첫번째 식과 같습니다.

위의 첫째 식은 순차적으로 2번째와 세번째 식으로 변환이 가능합니다. 위의 식중 세번째 식을 “주식”이라고 하겠습니다. S와 N의 내적의 표현은 S의 전치와 N의 곱과 같고, S와 N의 내적의 결과는 0이므로 다음과 같습니다.

위의 식과 앞서 “주식”이라고 했던 식을 함께 살펴보면, 다음의 결과과 같은 식을 얻을 수 있습니다.

위의 식에서 양변에 M의 전치 행렬에 대한 역행렬을 곱해 주면 최종적으로 K 행렬을 다음처럼 얻을 수 있습니다.

위의 식은 행렬의 기본 성질에 의해 다음과 같습니다.

즉, 어떤 변환(M)에 의해 법선 벡터가 그 고유한 특성을 유지할 수 있는 변환을 위한 행렬인 법선행렬은 모델뷰 행렬의 역행렬에 대한 전치 행렬과 같다는 것을 알 수 있습니다.

위의 그림에서 보는 것처럼 x축은 오른쪽으로 증가하고 y축은 아래쪽으로 증가하는 축에 대한 2점이 이루는 각도를 구하는 방법입니다. 각도는 60분법이며 편의상 0도 ~ 359.999999도로 산출됩니다. 딱히 말로써 설명드릴 것은 없을듯하고.. 코드 바로 나갑니다. 코드는 Java 입니다.

public double getAngle(PointF start, PointF end) {
    double dy = end.y-start.y;
    double dx = end.x-start.x;
    double angle = Math.atan(dy/dx) * (180.0/Math.PI);

    if(dx < 0.0) {
        angle += 180.0;
    } else {
        if(dy<0.0) angle += 360.0;
    }

    return angle;
}

퍼포먼스를 고려한다면 9번 코드는 불필요합니다. -45도나 315도나 동일한 각도이니까요.