Algorithm for sorting Vertices

Moderator
Posts: 133
Joined: 2008.05
Post: #1
I have a set of vertices that are in a circular pattern(not a circle though) and want to sort them so they go in order arond the circle. I know the orientation of the circle, ie what axis contains the center point of the circle, I just need to know how to reorder them so that they go in an order like this:

...........1.............
......10......2........
...9...............3....
...8...............4....
.......7.......5........
...........6.............

when the vertexes are totally in a random order.
Quote this message in a reply
Member
Posts: 469
Joined: 2002.10
Post: #2
cross product

---Kelvin--
15.4" MacBook Pro revA
1.83GHz/2GB/250GB
Quote this message in a reply
Moderator
Posts: 133
Joined: 2008.05
Post: #3
Ahhh! Thanks, I just figured it was dot-product and I had to interpolate the coefficients between the vertices in accordance with their normals, and from there apply the projection matrix to the quadric produced by the coordinates in global space.

Here is my code:
Code:
cross product;


It doesn't work though?
Quote this message in a reply
Feanor
Unregistered
 
Post: #4
Using a point on the axis through the centre and a reference point, you can calculate the angles between the reference point and each other point, and organize them that way. If you don't know the centre point itself (that is, the points are not truly on a circle but are on a cylinder), choose as centre the point that is perpendicular to the reference point, so that the angles are as large as possible (thinking in 3d).

I don't think using the cross product is any use since that gets you a vector perpendicular to the plane containing the tested points and the centre point. If the arranged points are a true (planar) circle, the vectors will all be the same on one half of the circle and opposite on the other half, which is no help.

It would take me a while to get the math right so hopefully this description is enough.
Quote this message in a reply
Moderator
Posts: 133
Joined: 2008.05
Post: #5
Been working on this some... here is my idea so far, it doesn't really work, but it's probably a start.

I start with one arbitrary vertice, and I find the vertice closest to it via the 3D distance formula(which doesn't seem to work properly, or it's my code, that is for you to judge, d = sqrt(x^2+y^2+z^2), where x,y,z = x1-x2, and so on).

Anyway, once I find the closest vertex I remove that vertex from the list so it will pick the next closest. The idea is that it just traverses around in a circle because the next closest point should be the next one on the circle... keep in mind, it's not really a circle. Unfortunately, this isn't working, it's picking vertices that are not even close, especcialy when it gets close to the end and a lot of the vertices are missing. I think when a vertex shares the same y as another one, it'll automatically assume it's closer or something? I don't really know, so any kind of insight would help.
Quote this message in a reply
Member
Posts: 184
Joined: 2004.07
Post: #6
Your 'gift wrapping' method will work if the vertices are close enough together. If there is significant gap it will fail. One way you could potentially make it work is instead to use closest distance, if you could use smallest angle instead. What I mean by that is, in 2d for example, you could select the point the furthest lowest and to the right, and then the next point on the circle is the one making the smallest angle between the x axis. Then the next point on the circle is the one with the smallest angle between the tangent line at those two points, and so forth. This is a method you can use to get the convex hull of a set of points, so it's a bit of overkill.


Here's one way to do what Feanor was suggesting: first reduce this problem to 2d, and then just sort by angle to the center of the circle. You said you know the axis the center of the circle goes through, so you can project all the points onto a plane with normal of that axis. If you don't know how to do this, the way it can be done is to first take an arbitrary point on your circle, and subtract the center of the circle from it. This is your resulting 'y' axis. Take the cross product of the axis going through the center of the circle and this 'y' axis, and you have your 'x' axis. Dot each vector from the center of the circle to a point on the circle with each axis to get your new projected components. Voila! Each point is now projected onto the plane defined by your resulting axes.

Once in 2d, you can translate all the points so that the center of the circle is the origin. Then to get the angle of each point you can use something with the arctangent function- for example, here's some code of mine that converts a vector into an angle:

Code:
ftype ftuvtoa(ftype x, ftype y){
    if(x==0.0) return y ? PI/2.0 : (3*PI)/2.0;
    if(y==0.0) return (x>0.0) ? 0 : PI;
    ftype a = atan(y / x);
    if(a<0){
        a+=PI;
    }
    if( (a>0) && (y<0)){
        a+=PI;
    }
    return a;
}


-p.
Quote this message in a reply
Bames53
Unregistered
 
Post: #7
Quote: d = sqrt(x^2+y^2+z^2)
what language are you working in? if you wrote that in C or C++ then you should know that 'x^2' ? 'x squared'

anyway, take the average of all the points (if you don't already know the general center) and then construct a reference vector from the center to any of the other points. use the dot product to get the angle between the reference vector and the vector to each point in turn. now just sort the points by the angle.

to construct the vectors, take each point's coordinates and subtract them from the center point's coords. so center point ( 1, 2, -1) and outside point ( 3, 1, 2) will yield vector <2, -1, 3>

the dot product aïb will yield |a||b|cos ? where ? is the angle between the vectors. so sorting by (aïb)/|a||b| will give you the order.

the dot product of two vectors <x1, y1, z1> ï <x2, y2, z2> = (x1*x2+y1*y2+z1*z2)

so < 1, 2, -1> ï < 3, 2, -1> = ( 1*3+2*2+-1*-1) = 8
the magnitude of the vectors is ?6 and ?14 respectively. 4?21
so cosine ? is 8/(?6?14) or ? 0.872871561 (which is about 30∞Wink
Quote this message in a reply
Bames53
Unregistered
 
Post: #8
stupid forum. the ?s in the above post are actually other characters.
the first is "not equal to"
second and third are "theta"
fourth and fifth are "square root sign"
ignore the sixth
seventh is "theta" again
eighth and ninth are "square root" again
tenth is "approximately"

that's how it looks on my screen anyway.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Need help with 2D algorithm neigaard 7 4,025 Jan 30, 2009 08:02 AM
Last Post: neigaard
  bad depth sorting in Cocoa OpenGL aldermoore 2 4,689 Dec 30, 2008 03:07 PM
Last Post: ThemsAllTook
  Depth-first sorting cecilkorik 8 5,111 Oct 18, 2007 12:26 PM
Last Post: OneSadCookie
  Help With Procedural Tree Algorithm Nick 1 3,747 Jul 26, 2006 10:56 AM
Last Post: unknown
  Rescaling vertices? WhatMeWorry 3 2,359 May 19, 2006 12:55 PM
Last Post: WhatMeWorry