steenpat
asked on
Reorder polygon vertex array
I have an array of vertices from a polygon in random order. I need some kind of algorithm to reorder them so that they start from upper left and go clockwise
Clue: If you want to figure out the neighbours for a vertex, do you simply want to figure out the least acute (i.e. largest) angle that it makes with two other vertices?
ASKER
ignore deletion.
no this is not 'homework'.
Clue: If you want to figure out the neighbours for a vertex, do you simply want to figure out the least acute (i.e. largest) angle that it makes with two other vertices?
This won't work all the time if you have a concave or convex object for instance.
no this is not 'homework'.
Clue: If you want to figure out the neighbours for a vertex, do you simply want to figure out the least acute (i.e. largest) angle that it makes with two other vertices?
This won't work all the time if you have a concave or convex object for instance.
ASKER
ignore deletion.
ASKER
ignore deletion.
If you have
(0,0) (1,1) (1,-1) (-1,1) (-1,-1)
what order would you want the vertices to be in?
(0,0) (1,1) (1,-1) (-1,1) (-1,-1)
what order would you want the vertices to be in?
ASKER
ozo:
start from upper left top most and go clockwise.
start from upper left top most and go clockwise.
ASKER
so, that would be -1,1. this object will work fine if you use the least acute angle method, if for instance you make a hollow "C" shape object then it doesnt work anymore because you have pts that have lower angles which shouldnt come next in the list.
so (-1,1)(1,1)(1,-1)(-1,-1)
where do we put (0,0)?
where do we put (0,0)?
Assuming (0,0) is the origin in the middle, (-1,0) is as "left" as (0,1) is "top", so which do you decide is the most "top left"?
ASKER
look I have already have code that will grab the same corner pt every time. so.. dont worry about that.
I just need a way of reordering the pts for objects like described above.i dont really feel like repeating myself several times, so i'll say it again, the least acute angle method will not work for these types of objects.
I just need a way of reordering the pts for objects like described above.i dont really feel like repeating myself several times, so i'll say it again, the least acute angle method will not work for these types of objects.
please describe where in the order the (0,0) point would belong.
Do you want to maximize the area of the polygon?
Do you want to minimize the perimeter of the polygon?
So you want it to be starshaped from its centroid?
Do you want to maximize the area of the polygon?
Do you want to minimize the perimeter of the polygon?
So you want it to be starshaped from its centroid?
I'm fed up with repeating my question too. <resign>
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Ozo: I see what you're saying. in my case actually the vertices are in an order, but not in the same starting order everytime. i guess i misphrased this question when i said random order because i was in a hurry. i think all i need to do is to find the topmost, leftmost pt and then shuffle the array so they start with that pt and thats it...
If (0,0) is the centre and you have (-1,0) and (0,1), which would you say should come first?