[Alogrithm] 기하알고리즘 - 벡터의 외적

해당 문제는 3차원 공간에 4개의 점이 주어지며,  이 4개의 점이 아래의 조건에 무엇을 만족하는지 판별하는 문제이다.

1) 4개의 점이 같은 한점에 존재한다.

2) 4개의 점이 한 직선에 존재한다.

3) 4개의 점이 한 평면 안에 존재한다.

4) 4개의 점이 1,2,3 번의 조건에 모두 해당되지 않는다.

다음과 같은 문제를 풀기 위해서는 평면의 방적식을 구해햐하며, 

평면의 방정식을 구하기 위해서는 평면의 법선벡터가 필요한데, 이때 벡터의 외적(Outer Product of Vector)을 이용한다.

3차원 벡터공간 R3의 두 벡터 a=(a1, a2, a3)과 b=(b1, b2, b3)에 대하여 이 두 벡터의 외적은a×b=(a2b3−a3b2, a3b1−a1b3, a1b2−a2b1)로 정의한다. 외적은 교차곱(cross product)이나 벡터곱(vector product)이라고도 한다. 외적은 3차원 벡터공간에서만 정의한다. [네이버 지식백과] 외적 [outer product] (수학백과, 2015.5, 대한수학회)

A,B,C,D 이렇게 4개의 점이 존재한다면, 우리는 3개의 점이 한 평면을 이룬다고 가정할 수 있다. 

여기서 우리는 AB, AC, AD 이렇게 3개의 벡터를 구할 수 있는데,

AB와 AC, AB와 AD 그리고 AC와 AD 벡터의 외적을 통해 우리는 법선벡터를 구할 수 있게 된다.

(사실 여기서 AB와 AC 하나만 구하면 되지만, 벡터의 외적 성질상 외적의 값이 0이 나오게 되면, 이는 한 직선상에 존재한다고 할 수 있다. 따라서 위의 3개의 외적이 모두 0 이라면 2번의 조건을 만족하게 된다.)

이렇게 해서 외적이 구해지면, 법선벡터 P의 값이 나오게 되는데, 우리는 이 값을 통해 평면의 방정식을 구할 수 있게 되고, 다른 하나의 점이 이 평면에 존재하는지만 판별하면 끝나게 된다.

코드는 아래와 같다.

#include <cstdio>
#include <algorithm>
using namespace std;
typedef struct {
    int x, y, z;
}SpaceDot;
int T;
SpaceDot SD[3];
SpaceDot CrossVector(SpaceDot v1, SpaceDot v2) {
    SpaceDot temp;
    temp.x = v1.y*v2.z - v1.z*v2.y;
    temp.y = v1.z*v2.x - v1.x*v2.z;
    temp.z = v1.x*v2.y - v1.y*v2.x;
    return temp;
}
int PlaneVector(SpaceDot Cross, SpaceDot v) {
    int temp = Cross.x*v.x + Cross.y*v.y + Cross.z*v.z;
    if (temp == 0) { return 1; }
    else { return 0; }
}
int main() {
    scanf("%d", &T);
    for (int i = 1; i <= T; i++) {
        int count = 0;
        for (int j = 0; j < 3; j++) {
            scanf("%d%d%d", &SD[j].x, &SD[j].y, &SD[j].z);
            if (SD[j].x == 0 && SD[j].y == 0 && SD[j].z == 0) count++;
        }
        if (count == 3) {
            printf("#%d 0\n", i);
            continue;
        }
        SpaceDot temp = CrossVector(SD[0], SD[1]);
        if (temp.x == 0 && temp.y == 0 && temp.z == 0) {
            temp = CrossVector(SD[0], SD[2]);
            if(temp.x == 0 && temp.y == 0 && temp.z == 0) {
                temp = CrossVector(SD[1], SD[2]);
                if (temp.x == 0 && temp.y == 0 && temp.z == 0) {    
                    printf("#%d 1\n", i);
                    continue;
                }
            }
        }
        int Result = PlaneVector(temp, SD[2]);
        if (Result == 1) printf("#%d 2\n", i);
        else {
            printf("#%d 3\n", i);
        }
    }
}