Sort unit vectors clockwise

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

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 on other sites

1. Store them in 4 buckets for each quadrant by comparing the x and y sign.

2. calculate each tangent y/x

3. sort by tangent using your favorite sorting algorithm

4. combine quadrant buckets in clockwise order

Share on other sites

Or if you aren't looking for speed you could use atan2 to obtain the angle between your vector and  Ox.

Obviously you are ...

Edited by imoogiBG

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 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  (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 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.

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 26
• 9
• 11
• 9
• 9
• Forum Statistics

• Total Topics
633710
• Total Posts
3013486
×