Jump to content
  • Advertisement
Sign in to follow this  
TheComet

Sorting (mathematical) vectors in list

This topic is 1689 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi,

 

Google is being rather unhelpful, as any search for "sorting vectors" inevitably results in std::sort because the unfortunate name of a dynamic array in C++ is "vector".

 

I wish to sort the following data structure(s) contained withing a list:

struct Vector2
{
   int x;
   int y;
};
struct Vector3
{
   int x;
   int y;
   int z;
};

The more I play around with the implementation of the overloaded comparison operators, the more I'm lead to believe it's simply not possible to perform the check "A<B" where A and B are both Vector2 or Vector3 objects.

 

Here's an example program thingy to play around with:

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>


template <class T>
class Vector2
{
public:
    Vector2() {}
    Vector2( int x, int y ) : x(x), y(y) {}
    ~Vector2() {}
    int x;
    int y;
    template <class T_> friend inline bool operator==( const Vector2<T_>& lhs, const Vector2<T_>& rhs );
    template <class T_> friend inline bool operator!=( const Vector2<T_>& lhs, const Vector2<T_>& rhs );
    template <class T_> friend inline bool operator< ( const Vector2<T_>& lhs, const Vector2<T_>& rhs );
    template <class T_> friend inline bool operator> ( const Vector2<T_>& lhs, const Vector2<T_>& rhs );
    template <class T_> friend inline bool operator<=( const Vector2<T_>& lhs, const Vector2<T_>& rhs );
    template <class T_> friend inline bool operator>=( const Vector2<T_>& lhs, const Vector2<T_>& rhs );
};


template <class T>
inline bool operator==( const Vector2<T>& lhs, const Vector2<T>& rhs )
{
    return ( lhs.x==rhs.x && lhs.y==rhs.y );
}
template <class T>
inline bool operator!=( const Vector2<T>& lhs, const Vector2<T>& rhs )
{
    return !operator==( lhs, rhs );
}
template <class T>
inline bool operator<( const Vector2<T>& lhs, const Vector2<T>& rhs )
{
    if( lhs.x>=rhs.x ) return false;
    if( lhs.y>=rhs.y ) return false;
    return true;
}
template <class T>
inline bool operator>( const Vector2<T>& lhs, const Vector2<T>& rhs )
{
    return operator<( rhs, lhs );
}
template <class T>
inline bool operator<=( const Vector2<T>& lhs, const Vector2<T>& rhs )
{
    return !operator>( lhs, rhs );
}
template <class T>
inline bool operator>=( const Vector2<T>& lhs, const Vector2<T>& rhs )
{
    return !operator<( lhs, rhs );
}


int main()
{


        std::vector< Vector2<int> > myListOfVectors;
        for( int n = 0; n != 10; ++n )
                myListOfVectors.push_back( Vector2<int>(rand()%100,rand()%100) );


        std::sort( myListOfVectors.begin(), myListOfVectors.end() );


        for( std::vector< Vector2<int> >::iterator it = myListOfVectors.begin(); it != myListOfVectors.end(); ++it )
                std::cout << it->x << "," << it->y << std::endl;


        return 0;
}
 

Any help?

Edited by TheComet

Share this post


Link to post
Share on other sites
Advertisement

Thanks for the quick reply!

 

For higher dimensions, would this be correct?

template <class T>
inline bool operator<( const Vector3<T>& lhs, const Vector3<T>& rhs )
{
if (lhs.x < rhs.x) return true;
if (lhs.x > rhs.x) return false;
if( lhs.y < rhs.y) return true;
if( lhs.y > rhs.y) return false;
return lhs.z < rhs.z
}

Share this post


Link to post
Share on other sites

Yes, that looks right. Note that while this is a valid comparison for the purposes of sorting, it may not be a particularly meaningful sort. In particular when used with floating point numbers, it may not be useful for search.

Share this post


Link to post
Share on other sites

You could create a sort method that takes in a lambda expression so you can sort differently depending on your case. I can envision a lot of ways to sort vectors (by length, by coordinate, by dot product with another vector, etc.) so you might want to keep your options open.

Share this post


Link to post
Share on other sites

Yes, that looks right. Note that while this is a valid comparison for the purposes of sorting, it may not be a particularly meaningful sort. In particular when used with floating point numbers, it may not be useful for search.

Noted, thanks.

 

The purpose of all this is to decrease a bottleneck I have with quickly searching a grid for the existence of an entity. I decided to insert the integer coordinates of the entities I'm interested in into a sorted list so I can do a binary search on the data (O(log n)) instead of having to traverse it (O(n)). The list has well over a thousand entries, so hope this will be more effective.

 

 

You could create a sort method that takes in a lambda expression so you can sort differently depending on your case. I can envision a lot of ways to sort vectors (by length, by coordinate, by dot product with another vector, etc.) so you might want to keep your options open.

Sorting by length and dot product is ambiguous, for instance: vec2(1,1).length() == vec2(-1,-1).length(). I can imagine this would require a more elaborate search algorithm, as I think one of the requirements of binary search is each entry in the list needs to be unique.

Edited by TheComet

Share this post


Link to post
Share on other sites


Sorting by length and dot product is ambiguous, for instance: vec2(1,1).length() == vec2(-1,-1).length(). I can imagine this would require a more elaborate search algorithm, as I think one of the requirements of binary search is each entry in the list needs to be unique.

 

For your purposes, lexicographic order sounds right, but other purposes other kinds of ordering might be better -- for example, if the question is "does an entity exist at X,Y" lexicographic ordering is good, but if the question was "which entities are located between 3 and 5 units from X, Y" then length (defined as distance from X,Y) is good.

 

In general, binary searches have to deal with ambiguity in some way -- as in the list [1,2,3,3,4,5] -- if the result is 3, which 3? In some cases it may not matter to you which 3 is returned or the one returned by convention happens to be the one you're interested in, but if it does matter to you, you might need to apply further criteria.

Share this post


Link to post
Share on other sites

The purpose of all this is to decrease a bottleneck I have with quickly searching a grid for the existence of an entity. I decided to insert the integer coordinates of the entities I'm interested in into a sorted list so I can do a binary search on the data (O(log n)) instead of having to traverse it (O(n)). The list has well over a thousand entries, so hope this will be more effective.

In that case you may want to consider a hash container rather than a sorted list.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!