The largest vector in an array

Question

I'm working on a game engine in C# at the moment and I've come across a matter I find confusing. I need to know how to get the maximum three component vector in an array.

There is a method in OpenTK that can compare two Vector3s to find out the max, I need this on a larger scale.

I've tried using Array.Max(), but I get the error :

At least one object must implement IComparable

Answer 1

Linq method of solving this would be using MaxBy coupled with a method mapping vector to a scalar type, e.g. LengthSquared or ComponentMax which gives float,

var resVec = array.MaxBy(vec => vec.LengthSquared);

Answer 2

Having a look at the Vector3 class of monotk gives us a hint why this doesn't work. Classes such as Sort() and Max() require your datastructure to implement the IComparable interface, which requires the CompareTo() method.

With this method you define a new binary relation. You can implement a lexicographical relation (aa > ab (this only works because the characters are ordinal) ) for strings, use distances if your class is a topological graph,...

Comparing two vectors ( dimension > 1) isn't so straight-forward. Which vector is greater: (100,10) or (10,100) or (67,43)? To compare vectors in a metric space, you have to rely on a norm. You might however want to create a different ordering, such as: First compare the Y coordinate, then the X coordinate. This gives us (for points) all the points sorted row by row.

As you can see, it is not trivial to compare vectors, and different use cases need a different definition of "the greatest of two vectors". The trivial case, where you want to know if two vectors are equal, is implemented (overloading the == and != operator).

Now what? You can extend the Vector3 class and implement the IComparable interface to be able to use Array.Max(). Or you can simply create a loop and compare your vectors on your own, and define what you want as "max". You can compare their norms, or use the implemented ComponentMax() functions, which compares the vector by, you guessed it, components.

All in all, once you defined "your maximum vector", the implementation is straight-forward.

Answer 3

You can do this in linear time:

Vector3 best = yourArray[0];

for (int i = 1; i < yourArray.Length; i++)
{
    if (yourArray[i] > best)
        best = yourArray[i];
}