Sign in to follow this  

Sort unit vectors clockwise

This topic is 806 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

I don't actually need to code this anywhere. I just was thinking about how an algorithm to sort a circular list of unit vectors to be in a clockwise order would work.

 

Conditions

After sorting, it doesn't matter what unit vector is first in the list as long as each adjacent unit vector in the list is clockwise to the last without any other unit vector between them

The list is circular, so the first vector in the list follows the last vector.

My own restriction here, but no trig functions allowed (Eg no atan2, atan ect) Use dot products or cross products instead

 

I have already come up with an algorithm that kinda looks like a bubble sort but has the draw back of being O(n^2) complexity. Any O(n log n) solutions?

 

Edit:

Just after posting I realized that this could be solved pretty trivially by using any sort function with simple comparison function that checks the sign of the x component and sorts on the y. I guess I could also add the restriction that they aren't unit vectors and you aren't allowed to normalize them to make the problem more difficult again.

Edited by HappyCoder

Share this post


Link to post
Share on other sites

The solution, with unit vectors, is as simple as making a sort function

unitVectors.sort((a, b) => {
    if (a.y > 0.0f) {
        if (b.y > 0.0f) {
            return b.x - a.x;
        } else {
            return -1;
        }
    } else if (a.y == 0.0) {
       if (a.x > 0) {
           return a.x - b.x;
       } else {
            if (b.y > 0.0f) {
                return 1;
            } else if (b.y == 0.0f) {
                return b.x - a.x;
            } else {
                return -1;
            }
       }
    } else {
       if (b.y < 0.0f) {
           return a.x - b.x;
       } else {
           return 1;
       }
    }
});

Not a very elegant solution and it assumes the vectors are unit vectors, but it gets the job done. I'm still curious if there is a method that can sort vectors without trig or without normalizing them.

Share this post


Link to post
Share on other sites
bool compare(a,b)
{
return a.x*b.y + a.y*b.x < 0
}

a is less than b, if dot(a, perpendicular(b)) < 0

 

EDIT:

Uh... assuming a number line that wraps around smile.png (you dont have an absolute ordering in such a space)

 

First youd use this to split the space in two along a unit vector of your choice, then sort those using the same function, then join the halves.

Edited by Waterlimon

Share this post


Link to post
Share on other sites

Split vectors in two halves, those with y < 0, and those with y > 0. Then first make the vectors with y < 0 always precede those with y > 0, and if the vectors have the same sign, then do the dot product. That is, something like

bool compare(a,b)
{
    if (a.y*b.y <= 0) // If a and b have different signs on their y coordinate?
       return a.y < b.y || (a.y == b.y && a.x < b.x); // Then the one pointing down comes before. If both have y = 0, then test x coord.
    else
       return a.x*b.y - a.y*b.x < 0; // Same y signs, establish ordering with a perpdot b.
}

I did not test this code in practice, but I know I use something like this in a recent project, though I don't have the source at hand now to verify. In particular, be sure to test the case when both vectors have y = 0 and only x coordinates differ.

Share this post


Link to post
Share on other sites

This topic is 806 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this