Squared Length를 이용한 3D 좌표의 빠른 거리 비교 방법

객체들 간의 거리를 비교하는 방법에 대해서 생각해 보도록 하겠습니다. 특히 여러 객체들 사이의 거리를 비교해 가장 가까운 점을 찾아야 할 경우라면 어떤 방법이 좋을까요?

3D 프로그래머라면 Length() 함수에 대해 잘 알고 있을 것입니다. 이 함수는 공간 상에서 두 점 간의 거리를 계산하는 함수로 게임 개발, 컴퓨터 그래픽 등 다양한 분야에서 사용됩니다. 하지만 더욱 빠르고 효율적인 거리 비교를 위해서 사용할 수 있는 LengthSquared() 함수도 있습니다.

LengthSquared() 함수는 Length() 함수와 비슷하게 두 점 간의 거리를 계산하지만, 각 좌표 차이의 제곱의 합을 구하고 제곱근을 계산하지 않고 그대로 반환합니다. 이 차이는 작아 보일 수 있지만, 많은 양의 점들을 다룰 때 성능에 큰 영향을 미칩니다.

아래는 LengthSquared()와 Length() 함수의 간단한 의사코드입니다.

double Point::LengthSquared() { return x*x + y*y + z*z; } 

double Point::Length() { return Sqrt(x*x + y*y + z*z); }

LengthSquared vs. Length

LengthSquared() 함수에 대해 자세히 이해하기 전에, 먼저 거리 비교를 위해 일반적으로 사용되는 방법에 대해 알아보겠습니다. 두 객체 간의 거리를 비교하려면 x, y, z 좌표 간의 거리를 계산하는 피타고라스 정리를 사용합니다. 이를 Length() 함수라고도 합니다. 이 방법은 각 좌표의 차이의 제곱의 합의 제곱근을 구하는 방법으로 정확하지만, 많은 양의 객체를 다룰 때 계산 비용이 많이 들게 됩니다.

이때 LengthSquared() 함수를 사용할 수 있습니다. LengthSquared() 함수는 게임 개발이나 컴퓨터 그래픽 분야에서 거리 비교를 빠르고 효율적으로 처리하기 위해 많이 사용하는 함수입니다. 각 좌표 차이의 제곱의 합을 구하는 방법으로, 제곱근을 구하는 방법보다 계산 비용이 적습니다. 이 차이는 작아 보일 수 있지만, 많은 양의 객체를 다룰 때는 성능에 큰 영향을 미칩니다.

Length 함수의 성능

3D 프로그래밍에서 거리를 계산할 때, sqrt() 함수는 계산 비용이 많이 들기 때문에 사용에 주의해야 합니다. sqrt() 함수는 제곱근을 구하는 복잡한 수학 연산을 수행하기 때문에, loop에서 반복적으로 사용하거나 대용량 데이터셋을 다룰 때 코드를 느리게 만들고 성능에 영향을 미치게 됩니다.

거리 비교를 할 때 기존의 Length() 함수 대신에 LengthSquared() 함수를 사용하면 sqrt() 함수를 사용하지 않고도 문제를 해결할 수 있습니다. LengthSquared() 함수도 좌표 간의 차이를 제곱한 값을 더하여 두 점 간의 거리를 계산하지만, sqrt() 함수를 사용하지 않기 때문에 계산 비용이 적습니다.

따라서 LengthSquared() 함수를 사용하면 대용량 데이터셋을 다룰 때 성능을 크게 향상시킬 수 있습니다. sqrt() 함수를 사용하지 않기 때문에, 계산 비용이 큰 제곱근 연산을 완전히 피할 수 있기 때문입니다.

하지만 LengthSquared() 함수는 두 개체 간의 실제 거리를 계산해주지는 않는다는 것을 유의해야 합니다. 만약 두 객체 간의 실제 거리를 알아내야 한다면, 여전히 좌표 간의 차이를 제곱하여 합한 후에 이에 대한 제곱근을 구해야 합니다.

LengthSquared() 함수를 사용하면 좋은 경우

LengthSquared() 함수는 3D 프로그래밍에서 점들 간의 거리를 비교하는 데 유용한 함수입니다. 다음은 LengthSquared() 함수를 활용할 수 있는 몇 가지 예시 문제입니다.

• 충돌 감지: 게임 개발에서 충돌 감지는 게임 플레이에 중요한 요소입니다. 객체 간 충돌을 확인할 때, 일정 거리 내에 있는 객체를 먼저 확인해서 계산 대상을 걸러내야 합니다. LengthSquared() 함수를 사용해서 객체 간의 거리를 계산하면, 계산 비용이 많이 드는 제곱근 계산 없이도 충돌 가능성을 빠르고 효율적으로 확인할 수 있습니다.
• 경로 탐색: 경로 탐색 알고리즘에서는 두 점 간의 거리를 계산하여 최단 경로를 찾아야 합니다. LengthSquared() 함수를 사용하면 Length() 함수보다 훨씬 빠르고 효율적인 계산을 할 수 있습니다.
• 3D 렌더링: 컴퓨터 그래픽에서 3D 렌더링은 복잡한 3D 객체를 2D 화면에 표시하는 과정입니다. 객체를 렌더링할 때는 자주 가장 가까운 객체나 다른 객체에 가려진 객체를 찾는 것이 필요합니다. LengthSquared() 함수를 사용하여 객체 간의 거리를 계산하면, 가장 가까운 객체와 가려진 객체를 빠르고 효율적으로 찾아낼 수 있습니다.
• 물리 시뮬레이션: 물리 시뮬레이션에서는 객체 간의 거리를 계산하여 작용하는 힘을 계산해야 할 때가 있습니다. LengthSquared() 함수를 사용하면 계산 비용이 큰 제곱근 연산을 피할 수 있어서 더 빠르고 효율적인 시뮬레이션을 수행할 수 있습니다.

위와 같은 예시들에서 LengthSquared() 함수는 공간 상에서 점들 간의 거리를 비교하는 데에 유용한 도구입니다. Length() 함수보다 계산 비용이 적기 때문에, 대용량 데이터셋을 다룰 때 성능과 효율성이 크게 향상됩니다. 이러한 이점들 덕분에 LengthSquared() 함수는 빠르고 반응성이 뛰어난 어플리케이션을 만들 수 있게 해줍니다.

사례 1 - 가장 가까운 점 찾기 (Finding Closest Point)

주어진 점에서 가장 가까운 점을 찾는 문제는 3D 프로그래밍에서 흔한 문제 중 하나입니다. 이 문제는 LengthSquared() 함수를 사용하여 코드의 효율성을 향상시키는 좋은 예시입니다.

이 문제를 해결하기 위해서는 먼저 모든 점과 주어진 점 간의 거리를 계산해야 합니다. 이를 위해 LengthSquared() 함수를 사용하면 각 점 사이의 거리를 빠르고 효율적으로 계산할 수 있습니다. 그리고 나서, 이러한 거리를 기반으로 가장 가까운 점을 찾아낼 수 있습니다.

다음은 주어진 점에서 가장 가까운 점을 찾는 C++ 코드의 예시입니다.

#include <iostream>
#include <cmath>
using namespace std;
struct Point {
    double x, y, z;
};
double DistanceSquared(Point p1, Point p2) {
    double dx = p2.x - p1.x;
    double dy = p2.y - p1.y;
    double dz = p2.z - p1.z;
    return dx * dx + dy * dy + dz * dz;
}
Point FindClosestPoint(Point p, Point points[], int numPoints) {
    Point closestPoint = points[0];
    double closestDistSquared = DistanceSquared(p, closestPoint);
    for (int i = 1; i < numPoints; i++) {
        double distSquared = DistanceSquared(p, points[i]);
        if (distSquared < closestDistSquared) {
            closestPoint = points[i];
            closestDistSquared = distSquared;
        }
    }
    return closestPoint;
}
int main() {
    Point p = {1, 2, 3};
    Point points[] = {{4, 5, 6}, {7, 8, 9}, {10, 11, 12}};
    int numPoints = 3;
    Point closestPoint = FindClosestPoint(p, points, numPoints);
    cout << "The closest point to (" << p.x << ", " << p.y << ", " << p.z << ") is (" << closestPoint.x << ", " << closestPoint.y << ", " << closestPoint.z << ")" << endl;
    double distance = sqrt(DistanceSquared(p, closestPoint));
    cout << "The distance between the points is " << distance << endl;
    return 0;
}

LengthSquared() 함수를 사용하여 가장 가까운 점을 찾은 후에는, 이제 가장 가까운 점과 주어진 점 사이의 실제 거리를 제곱근 공식을 사용하여 계산할 수 있습니다. 하지만 많은 경우에 가장 가까운 점의 최종 결과값만 필요하고 실제 거리값은 필요하지 않을 수 있습니다.

사례 2 - 거리순으로 점 정렬하기 (Sorting Points)

LengthSquared() 함수가 유용하게 사용될 수 있는 또 다른 예시는, 주어진 점과 가까운 거리의 점들로 이루어진 배열을 정렬하는 문제입니다. 이 문제는 GPS 매핑, 이미지 처리, 객체 인식 등 많은 애플리케이션에서 발생합니다.

다음은 LengthSquared() 함수를 사용하여 주어진 점에서 가까운 거리 순서로 이루어진 점들로 배열을 정렬하는 C++ 코드의 예시입니다.

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
struct Point {
    double x, y, z;
};
bool ComparePoints(Point p1, Point p2, Point origin) {
    double dist1 = LengthSquared({p1.x - origin.x, p1.y - origin.y, p1.z - origin.z});
    double dist2 = LengthSquared({p2.x - origin.x, p2.y - origin.y, p2.z - origin.z});
    return dist1 < dist2;
}
int main() {
    Point origin = {0, 0, 0};
    Point points[] = {{1, 1, 1}, {2, 2, 2}, {3, 3, 3}, {4, 4, 4}, {5, 5, 5}};
    int numPoints = 5;
    sort(points, points + numPoints, [&](Point p1, Point p2) {
        return ComparePoints(p1, p2, origin);
    });
    for (int i = 0; i < numPoints; i++) {
        cout << "Point " << i + 1 << ": (" << points[i].x << ", " << points[i].y << ", " << points[i].z << ")" << endl;
    }
    return 0;
}

위 코드에서는 주어진 점과 가까운 정도에 따라 각 점들의 거리를 계산하여 정렬합니다. 이 때 LengthSquared() 함수를 사용하여 거리를 계산하고, ComparePoints() 함수를 사용하여 정렬합니다. 이렇게 하면 더 빠르게 정렬할 수 있습니다.

위와 같이 LengthSquared() 함수를 사용하면, 주어진 점과 가까운 거리에 따라 점들을 효율적으로 정렬할 수 있습니다.

사례 3 – 점 군집화 (Clustering Points)

머신러닝 애플리케이션에서, 클러스터링 또는 분류 작업을 수행하기 위해 데이터 점들 사이의 거리를 계산하는 것이 필요한 경우가 많습니다. 이 때 LengthSquared() 함수를 사용하여 거리를 계산하면, 최종 거리값이 필요할 때까지 불필요한 제곱근 계산을 피할 수 있습니다.

다음은 LengthSquared() 함수를 사용하여 중심점과 가까운 거리에 따라 점들을 군집화하는 C++ 코드의 예시입니다.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
struct Point {
    double x, y, z;
};
double LengthSquared(Point p) {
    return p.x * p.x + p.y * p.y + p.z * p.z;
}
vector<vector<Point>> ClusterPoints(vector<Point> points, vector<Point> centroids) {
    int k = centroids.size();
    vector<vector<Point>> clusters(k);
    for (Point p : points) {
        int closestCentroid = 0;
        double closestDistSquared = LengthSquared({p.x - centroids[0].x, p.y - centroids[0].y, p.z - centroids[0].z});
        for (int i = 1; i < k; i++) {
            double distSquared = LengthSquared({p.x - centroids[i].x, p.y - centroids[i].y, p.z - centroids[i].z});
            if (distSquared < closestDistSquared) {
                closestCentroid = i;
                closestDistSquared = distSquared;
            }
        }
        clusters[closestCentroid].push_back(p);
    }
    return clusters;
}
int main() {
    vector<Point> points = {{1, 1, 1}, {2, 2, 2}, {3, 3, 3}, {4, 4, 4}, {5, 5, 5}};
    vector<Point> centroids = {{0, 0, 0}, {6, 6, 6}};
    int k = centroids.size();
    vector<vector<Point>> clusters = ClusterPoints(points, centroids);
    for (int i = 0; i < k; i++) {
        cout << "Cluster " << i + 1 << ":" << endl;
        for (Point p : clusters[i]) {
            cout << "(" << p.x << ", " << p.y << ", " << p.z << ")" << endl;
        }
    }
    return 0;
}

이 예시에서는 LengthSquared() 함수를 사용하여 각 점과 각 중심점 사이의 제곱 거리를 계산합니다. 그리고 ClusterPoints() 함수는 제곱 거리를 기반으로 각 점을 가장 가까운 중심점에 할당하여 점들의 군집을 생성합니다.

사례 4 - 주어진 거리 이내에 존재하는 점들을 골라내기 (Collecting Points in Range)

LengthSquared가 제곱근을 사용하지 않기 때문에, 반대로 주어진 거리(범위)와 비교하려면 Range를 제곱하는 것이 유용합니다.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct Point {
    double x, y, z;
};
double LengthSquared(Point p) {
    return p.x * p.x + p.y * p.y + p.z * p.z;
}

vector<Point> CollectPointsInRange(Point BasePoint, vector<Point> Points, double Range) {
    double RangeSquared = Range * Range;
    vector<Point> collected_points;
    for (auto point : Points) {
        if (LengthSquared(BasePoint, point) <= RangeSquared) {
            collected_points.push_back(point);
        }
    }
    return collected_points;
}

int main() {
    Point BasePoint(0,0,0);
    vector<Point> Points = {Point(-2,2,0), Point(1,1,2), Point(4,4,1)};
    double Range = 3.0;
    vector<Point> collected_points = CollectPointsInRange(BasePoint, Points, Range);
    for (auto point : collected_points) {
        cout << "(" << point.x << "," << point.y << "," << point.z << ") ";
    }
    return 0;
}

LengthSquared 함수가 두 점 p1과 p2 사이의 거리의 제곱을 반환하기 때문에 실제 거리값을 계산하는 것은 아닙니다. 그렇다고 해서 실제 거리와 비교할 수 없는 것이 아니라 필요에 따라 실제 거리값을 제곱해서 비교하면 됩니다.

CollectPointsInRange 함수에서는 Base Point와 Points 벡터에 있는 모든 점들 간의 거리의 제곱을 LengthSquared 함수를 사용하여 계산하고, 이 값이 RangeSquared보다 작거나 같으면 수집합니다.

LengthSquared의 여러가지 이름들

LengthSquared()는 3D 프로그래밍에서 점들 간 거리를 비교하는 데 자주 사용되는 함수이기 때문에 다른 라이브러리나 언어에서도 제공하고 있지만 다른 이름이나 구문으로 사용되고 있습니다. 다음은 다른 이름으로 사용되는 몇가지 예시입니다.

1. OpenGL (C++): glm::length2()
2. Unreal Engine(C++): SizeSquared(), LengthSquared()
3. Unity (C#): sqrMagnitude().
4. 만약 해당 함수를 찾을 수 없는 경우, Vector::dot(p, p)를 사용하면 됩니다.

LengthSquared 함수의 활용

이상의 예에서 보았듯이, 여러 객체들 간의 거리를 비교해야 할 경우, LengthSquared()를 사용하면 Length() 보다 빠르고 효율적으로 작업을 수행할 수 있습니다. LengthSquared 함수가 실제 거리를 반환하지는 않지만, 특정한 상황에서는 유용한 도구가 될 수 있습니다. 한 번 시도해보고 코드의 성능 차이를 확인해보세요.