Sign in to follow this  

Sort about pivot

This topic is 4855 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 I am tring to implement an algorithm to find the 2d convex hull. I am using the following set of points as a test... (0 , 0) (4 , 0) (4 , 4) (0 , 4) (2 , 2) Pretty simple. Just by looking we can see that (2 , 2) won't be a part of the convex hull. Now I find an extreme point to act as the pivot, that point is (4 , 0) Could someone please tell me the result of sorting the points in order of increasing angle about the pivot. I seem to be ending up with the following x: 4 y: 4 x: 2 y: 2 x: 0 y: 4 x: 4 y: 0 x: 0 y: 0 Thank you.

Share this post


Link to post
Share on other sites
not sure what you are trying to achieve, and I think what I'm thinking, your example is wrong :)

so you want to list the points in increasing angle from a pivot.

using the point (4, 0), I'd get the order

(4, 4) (+90)
(2, 2) (+45)
(0, 4) (+45)
(0, 0) (+180)

so what you need is a way to compute the angle of each point from the pivot, and a base axis, which here, is the X axis (1, 0)

from there, for a convex hull, I guess you can take the min point, (4, 4), which will give you two segments, and build the convex hull by finding the next point that deviates the less from the segment (4, 0)-(4, 4). since you may have points which are aligned, I'd also sort them by distance.

You do that until you reach the first point, which you should do. If not, then that point maybe in the middle of a flat segment, or something like that. To solve that, instead of starting your hull from (4, 0), start it from (4, 4) and carry on until you loop around to (4, 4).

if you find an angle > 180 degrees, then something went wrong.

to find an angle between two segments a and b, it's

angle = atan2(ax*by-ay*bx, ax*bx+ay*by) * (180.0f / Pi) + 180.0f;

first test, as I said, would have the segment a = (1, 0).

Share this post


Link to post
Share on other sites
I guess my question would be whether you got this from some source or came up with it on your own? If you came up with it on your own then one thing to consider is how to find the rightmost point without regard to ordering all the points. If C is your current point, N is a potential next point and O is some other point then you can define a forward vector, F=N-C, and a right vector, R=(F.y,-F.x). Now if the dot product of O-C and R is negative then O lies to the left when standing at C facing N. So you select your starting point as you do now and eliminate it from the list. You take the first point in the list and call it N. Then you check all the rest of the points. If any lie to the left then it becomes your new N and you continue through your list. When you get to the end you add whatever you came up with as N to your convex hull and repeat the process always checking the first point as well so that you know when you have completed the loop. That will get you a convex hull.

Some points may lie in the same direction. When they do the furthest point has the largest magnitude for the dot product so you can find the furthest one without actually calculating the distance, i.e. no need for sqrt. If you are following some description of an algorithm rather than coming up with this on your own then where points that are not part of the convex hull lie in the list most likely does not matter. That's because you are going to have to eliminate them once you have the list in order. Anywhere you put them they will be eliminated. All that matters is that those on the convex hull are in the correct order. So in your example (2,2) is equally valid before or after (0,4). If (2,3) was in there it would be the only one in that direction and it would have to be eliminated. Presumably if (4,2) was in there it should be eliminated as well although you could construct an legitimate convex hull including it.

Share this post


Link to post
Share on other sites

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