Solved

Reorder polygon vertex array

Posted on 2008-10-20
15
580 Views
Last Modified: 2010-07-27
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
0
Comment
Question by:steenpat
  • 7
  • 4
  • 4
15 Comments
 
LVL 17

Expert Comment

by:rstaveley
ID: 22758563
Homework?

If (0,0) is the centre and you have (-1,0) and (0,1), which would you say should come first?
0
 
LVL 17

Expert Comment

by:rstaveley
ID: 22758652
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?
0
 

Author Comment

by:steenpat
ID: 22762790
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.
0
 

Author Comment

by:steenpat
ID: 22762799
ignore deletion.
0
 

Author Comment

by:steenpat
ID: 22762802
ignore deletion.
0
 
LVL 84

Expert Comment

by:ozo
ID: 22762953
If you have
(0,0) (1,1) (1,-1) (-1,1) (-1,-1)
what order would you want the vertices to be in?
0
 

Author Comment

by:steenpat
ID: 22763166
ozo:
start from upper left top most and go clockwise.
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 

Author Comment

by:steenpat
ID: 22763190
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.
0
 
LVL 84

Expert Comment

by:ozo
ID: 22763199
so (-1,1)(1,1)(1,-1)(-1,-1)
where do we put (0,0)?
0
 
LVL 17

Expert Comment

by:rstaveley
ID: 22764950
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"?
0
 

Author Comment

by:steenpat
ID: 22772590
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.
0
 
LVL 84

Expert Comment

by:ozo
ID: 22772647
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?
0
 
LVL 17

Expert Comment

by:rstaveley
ID: 22774333
I'm fed up with repeating my question too. <resign>
0
 
LVL 84

Accepted Solution

by:
ozo earned 250 total points
ID: 22774608
(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.
0
 

Author Comment

by:steenpat
ID: 22776386
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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
how to understand recursion 12 219
basic hardware to learn oop advanced design patterns 3 88
C++ :Change value from  DisableCMD registry 4 51
Why isn't object file created? 6 43
Article by: Nadia
Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
Article by: Nadia
Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…

867 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now