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?
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.
ozo:
start from upper left top most and go clockwise.
0
Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.
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.
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.
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?
(1,1) (1,-1) (-1,1) (-1,-1)
(2,2) (2,-2) (-2,2) (-2,-2)
could be
(-2,2) (2,2) (1,1) (1,-1) (2,-2) (-2,-2) (-1,-1) (-1,1)
or
(-2,2) (-1,1) (1,1) (2,2) (2,-2) (1,-1) (-1,-1) (-2,-1)
or
(-2,2) (2,2) (2,-2) (-2,2) (-1,-1) (1,-1) (1,1) (-1, 1)
or
(-2,2) (2,2) (2,-2) (1,-1) (1,1) (-1,1) (-1,-1) (-2,-2)
or
(-2,2) (2,2) (1,1) (-1,1) (-1,-1) (1,-1) (2,-2) (-2,-2)
or
(-2,2) (-1,1) (-1,-1) (1,-1) (1,1) (2,2) (2,-2) (-2,-2)
among others
How do you want to decide among them?
One way could be to prefer polygons with a shorter perimeter, which you can do
by solving the Traveling Salesman problem.
This could take a long time if you have a lot of points, but if near-optimal solution is good enough, you might use the
Christofides heuristic and start with a minimal spanning tree and convert it to a simple polygon by skipping nodes.
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...
0
Featured Post
Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline
When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20.
The divisors of 12 are 1, 2, 3, 4, 6, 12
The divisors of 20 are 1, 2, 4, 5, 10 20
The highest number among the c…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.