많은 스플라인의 종류 중에 하나인 큐빅 스플라인을 1차원의 보간에 적용하는 것에 대해 살펴보겠습니다. Catmull-Rom 스플라인을 구성하는 구분된 부드러운 곡선들을 나타내는 키 프레임 집합을 가지며 모든 키는 곡선 상에 위치합니다. 이 루틴을 사용하기 위해서 4개의 키 프레임 값이 필요합니다. 이 4개의 키 값을 v0, v1, v2, v3라고 하고, 여기에 보간을 위하여 v1에서 v2 사이의 지정된 0~1까지의 범위를 가지는 실수값 x가 존재합니다. 아래의 f(x)의 반환값은 x값에 의해 결정이 됩니다.

• d ∙ v > 0 이면 투영되므로 거리를 구할 수 있다는 것이고
• d ∙ v <= 0 이면 편선 뒤에 구가 있어 투영되지 않아 거리를 구할 수 없다는 것이다.

• a = |c - i1| = 구의 반지름값
• b = |pc - c|
• c = |pc - i1|

위에서 오직 길이 c만이 미지수이며, 길이 c는 다음처럼 계산할 수 있다.

1. 벡터 v와 u를 구하며, 벡터 v = p1 - p0, u = p2 - p0이다.
2. 벡터 n = v x u (v와 u의 외적)
3. 벡터 n을 정규화(크기가 1인 단위벡터화)
4. 벡터 n=(xn, yn, zn)이라고 한다면 계수 A=xn, B=yn, C=zn 임
5. 계수 D를 구하기 위해 앞에서 제시한 평면의 공식을 D에 대해 전개. 즉, -D = Ax + By + Cz
6. 평면 상의 점(예를 들어 p0)에 대해 위의 공식의 x, y, z에 값을 대입하여 D를 구함(이 값은 내적을 이용해 쉽게 구할 수 있음. 즉, D = -n ∙ p0)

어떤 점에서 평면까지의 거리와 그 의미

이 블로그의 포스팅된 글에 중에 이와 관련된 글이 있지만, 평면에 대한 공식을 알아보니.. 복습 차원에서 다시 한번 정리해 보겠습니다.

앞에서 평면 방정식의 계수를 구하는 방법을 이용해 얻은 평면의 공식 Ax + By + Cz + D = 0 이 있다고 할때, 이 평면과 어떤 점 r 사이의 거리는... 만약 r이 (xr, yr, zr)이라면 이 좌표를 위의 평면의 방정식에 대입하여 D에 대해 전개하여 구한 값에 대해 절대값을 취하면 됩니다. 즉, D = |Axr + Byr + Czr|이며 이는 내적의 공식을 이용해서 다음처럼 표현할 수 있습니다.

폴리곤이 오목한지 볼록한지에 대한 각각의 경에 대해서, 좌표가 시계방향으로 되어 있는지, 반시계 방향으로 되어 있는지를 검사하기 위한 방법입니다. GIS에서 폴리곤 도형에 대해 시계방향인지 반시계방향인지에 따라 폴리곤에 대한 구멍(Hole)인지의 여부를 결정짓는 경우가 있습니다. 이외에 폴리곤의 앞면인지 뒷면인지의 여부도 시계방향인지의 여부에 따라 결정됩니다.

먼저 폴리곤의 구성하는 좌표의 개수가 N개라고 하고, 구성 좌표를 아래처럼 표기합니다.

볼록한 폴리곤에 대해서 좌표의 방향에 대한 간단한 검사는 인접한 좌표들이 이루는 선분(벡터)에 대한 외적(Cross Product)을 통해 가능합니다. 만약에 외적이 양수이면 수직벡터가 폴리곤이 이루는 평면(z축이 평면의 위쪽으로 향한다고 가정) 윗 방향이고, 음수이면 평면의 안쪽 즉 평면에 대해 아래 방향으로 향합니다.

이제 u값을 구했으니.. 이 u값을 선에 대한 공식에 대입하여 교차점 P를 구할 수 있습니다. 다음은 주의할 점입니다.

• 만약 u에 대한 식에서 분모가 0이면, 주어진 선과 평면의 법선은 수직이라는 의미입니다. 즉, 이말은 평면과 선은 서로 만나지 않는다는 의미입니다.
• 교점 P가 P1과 P2 사이에 있는지 검사해야한다면, u값이 0~1사이의 값인지 확인해 보면 됩니다.

방법 2.

이제 평면에 대한 공식으로, 고등학교때 배운 또 다른 형태는 다음과 같습니다.

const size_t cntData = 20;
int data[cntData];

void selectionSort(int data[], size_t cntData) {
    for(size_t beginIdx=0; beginIdx<cntData-1; beginIdx++) {
        int minData = data[beginIdx];
        size_t minDataIdx = beginIdx;
        for(size_t i=beginIdx+1; i<cntData; i++) {
            if(minData>data[i]) {
                minData = data[i];
                minDataIdx = i;
            }
        }
		
        data[minDataIdx] = data[beginIdx];
        data[beginIdx] = minData;
    }
}

void insertionSort(int data[], size_t cntData) {
    int t;
    size_t j;

    for(size_t i=1; i<cntData; i++) {
        t = data[i];
        j = i;
		
        while(data[j-1]>t && j>0) {
            data[j] = data[j-1];
            j--;
        }

        data[j] = t;
    }
}

void bubbleSort(int data[], size_t cntData) {
    for(size_t i=cntData-1; i>0; i--) {
        for(size_t j=0; j<i; j++) {
            if(data[j]>data[j+1]) {
                int tmpData = data[j];
                data[j] = data[j+1];
                data[j+1] = tmpData;
            }
        }
    }
}

void ShellSort(int data[], size_t cntData) {
    size_t h;
    for(h=1; h<cntData; h=3*h+1);

    for(h/=3; h>0; h/=3) {
        for(size_t i=0; i<h; i++) {
            for(size_t j=i+h; j<cntData; j+=h) {
                int v = data[j];
                size_t k = j;
                while(data[k-h]>v && k>(h-1)) {
                    data[k] = data[k-h];
                    k -= h;
                }
                data[k] = v;
            }
        }
    }
}

void distributionCounting(int data[], size_t cntData, 
                          int startValue, int endValue) {
    const size_t cntType = endValue-startValue+1;
    int *count = new int[cntType];
    
    for(size_t i=0; i<cntType; i++) {
        count[i] = 0;
    }

    for(size_t i=0; i<cntData; i++) {
        count[data[i]]++;
    }

    for(size_t i=1; i<cntType; i++) {
        count[i] += count[i-1];
    }

    int *tmp = new int[cntData];
	
    for(int i=cntData-1; i>=0; i--) {
        tmp[--count[data[i]]] = data[i];
    }

    for(size_t i=0; i<cntData; i++) {
        data[i] = tmp[i];
    }

    delete [] tmp;
    delete [] count;
}

void quickSort(int data[], size_t cntData) {
    int pivot, tmp;
    int i, j;

    if(cntData > 1) {
        pivot = data[cntData-1];
        i = -1;
        j = cntData - 1;

        while(true) {
            while(data[++i] < pivot);
            while(data[--j] > pivot);

            if(i >= j) break;
            tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }

        data[cntData-1] = data[i];
        data[i] = pivot;

        quickSort(data, i);
        quickSort(data+i+1, cntData-i-1);
    }
}

unsigned long bit(unsigned data, int b) {
    return data & (1 << b);
}

void radixExchangeSort(int data[], size_t cntData, int b) {
    int t, i, j;
    if(cntData>1 && b>=0) {
        i = 0;
        j = cntData - 1;

        while(true) {
            while(bit(data[i], b)==0 && i<j) i++;
            while(bit(data[j], b)!=0 && i<j) j--;

            if(i>=j) break;
			
            t = data[i];
            data[i] = data[j];
            data[j] = t;
        }

        if(bit(data[cntData-1], b) == 0) j++;

        radixExchangeSort(data, j, b-1);
        radixExchangeSort(data+j, cntData-j, b-1);
    }
}

unsigned bits(unsigned data, int startBitIndex, int count) {
    return (data >> count) & ~(~0 << startBitIndex);
}

void straightRadixSort(int data[], size_t cntData) {
    int i, j;
    int *tempData, *count;

    const size_t sizeBitData = sizeof(data[0]) * 8;
    const size_t bitCount = 4;
    const size_t cntCountArray = (1<<bitCount);

    tempData = (int *)malloc(sizeof(int)*cntData);
    count = (int *)malloc(sizeof(int)*cntCountArray);

    for(i=0; i<sizeBitData/bitCount; i++) {		
        for(j=0; j<cntCountArray; j++)
            count[j] = 0;

            for(j=0; j<cntData; j++)
                count[bits(data[j], i*bitCount, bitCount)]++;

            for(j=1; j<cntCountArray; j++)
                count[j] += count[j-1];

            for(j=cntData-1; j>=0; j--)
                tempData[--count[bits(data[j], i*bitCount, bitCount)]] = 
                    data[j];

            for(j=0; j<cntData; j++)
                data[j] = tempData[j];
    }

    free(count);
    free(tempData);
}

double gaussDistributeRand(double begin, double end, size_t detail=5) {
    double r = 0;
    for(size_t i=0; i<detail; i++)
        r += (double)rand()/(double)RAND_MAX;
        r /= (double)detail;

    return r*(end-begin)+begin;
}