Jarvis Algorithm - How to ?

Development Programming & Scripting C++
1

Hi, i’m trying to create some zone around point.

I did found the tutorial from : https://www.geeksforgeeks.org/convex-hull-set-1-jarviss-algorithm-or-wrapping/?fbclid=IwAR1ZKIpsH9MB9SHdY2hh8UUWMwD85jDvpNo_VFsGZYYk1J118RLwmBOdVGk

I tryied it to make it for c++ but seem to be stuck.

here’s the code (if someone can correct it for me) :

.h


UFUNCTION(BlueprintCallable, Category = "Physics")
        static TArray<FVector> JarvisAlgorithm(TArray<FVector> Points, int MaxPoints);


        static int orientation(FVector P, FVector Q, FVector R);

.cpp


TArray<FVector> UMyBlueprintFunctionLibrary::JarvisAlgorithm(TArray<FVector> Points, int MaxPoints)
{
    int L = 0;
    TArray<FVector> Hull;

    for (int j = 1; j < MaxPoints; j++)
    {
        if (Points[j].X < Points[L].X) {
            L = j;
        }
    };

    int P = L;
    int Q;

    do {

        Hull.Add(Points[P]);

        Q = (P + 1) % MaxPoints;
        for (int i = 0; i < MaxPoints; i++)
        {
            if (orientation(Points[P], Points*, Points[Q]) == 2)
            {
                Q = i;
            }
        }

    } while (P != L);

    return Hull;
};

int UMyBlueprintFunctionLibrary::orientation(FVector P, FVector Q, FVector R)
{
    int val = (Q.Y - P.Y) * (R.X - Q.X) -
        (Q.X - P.X) * (R.Y - Q.Y);

    if (val == 0) return 0;  // colinear 
    return (val > 0) ? 1 : 2; // clock or counterclock wise
};

I hope to find the solution :smiley:

2

The only issue I can see is, that you use a FVector as far as I know it’s a 3D Vector, so if you do “int n = sizeof(points)/sizeof(points[0]);”, it’s different because sizeof(points[0]) should be 2 and sizeof(FVector) should be 3.
But maybe that’s not the point, I can’t see another issue.

3

Hey, i have found my answer a while ago, i will share for everyone :

.H


UFUNCTION(BlueprintCallable, Category = "Physics")
        static void JarvisAlgorithm(TArray<FVector> Points, int MaxPoints, TArray<FVector>& Hull, int& NumbersOfPoints);

        static int orientation(FVector P, FVector Q, FVector R);

.cpp


void UMyBlueprintFunctionLibrary::JarvisAlgorithm(TArray<FVector> Points, int MaxPoints, TArray<FVector>& Hull, int& NumbersOfPoints)
{
    int L = 0;

    for (int j = 1; j < MaxPoints; j++)
    {
        if (Points[j].X < Points[L].X) {
            L = j;
            // UE_LOG(LogTemp, Warning, TEXT("%d -|- %d"), L, MaxPoints);
        }
    };

    NumbersOfPoints = -1;
    int P = L, Q;

    do {

        Hull.Add(Points[P]);
        NumbersOfPoints = NumbersOfPoints + 1;

        Q = (P + 1) % MaxPoints;
        for (int i = 0; i < MaxPoints; i++)
        {
            if (orientation(Points[P], Points*, Points[Q]) == 2)
            {
                Q = i;
            }
        }

        P = Q;

        UE_LOG(LogTemp, Warning, TEXT("%d -- hello"), NumbersOfPoints);

    } while (P != L);

};

int UMyBlueprintFunctionLibrary::orientation(FVector P, FVector Q, FVector R)
{
    int val = (Q.Y - P.Y) * (R.X - Q.X) -
        (Q.X - P.X) * (R.Y - Q.Y);

    if (val == 0) return 0;  // colinear 
    return (val > 0) ? 1 : 2; // clock or counterclock wise
};

Hope it can help some people.

4

this never gets past first index for me