Couldn't you compute the (2D) convex hull and take the ordering of it? Since the polygon is convex... Otherwise a left-to-right sweep algorithm comes to mind.

Illco

Quote:
how do you find the ordering such that n ·(vi-1-p)×(vi-p) > 0 for all i = 1 + j mod n, and j = 1,...,n?

both vertices have i in their subscripts. Was this intended? What is j for? Are you supposed to fix j at a certain value and then have the inequality hold for all appropriate i?

this means an ordering where they are all clockwise ( or ccw )???

btw you didnt use j, you wrote i-1 instead

if it's just about finding the a CW or CCW order of traversal, you can do the following:

1. transform the given plane into the regular XY plane *by placing the point p at the origin*
2. find the coordinates of all points in the transformed plane
3. find the angles of all vertices to the new origin (point p)
4. Sort the vertices, given their angle.
Smaller first means CCW order. Larger first means CW.

I haven't given this much thought. I suppose it should work

edit:
To clarify a little on step 1, you should do a parallel translation of the system of coordinates, so that point p is your new origin. This can be achived by the matrix T:
[ 1 0 0 -p.x ]
[ 0 1 0 -p.y ]
[ 0 0 1 -p.z ]
[ 0 0 0 1 ]

The equation for the translated plane is now: Ax+By+Cz = 0.
There is no constant since it passes through the origin.
Now, you must transform that plane into the regular XY plane you're used to seeing 2d figures in. For this, must find a base B of 3 orthonormal vectors in the pre-transformed space and map them onto the regular base of R^3 {{1,0,0},{0,1,0},{0,0,1}}.
Clearly, one of these vectors, call it b3, must be the plane's normal. You can find another one, b1, by setting its 2 coordinates to random values and then solving for the third from the plane's equation. Normalize it.
You can find the last vector for the vector base, from the equation:
b2 = -b1 x b3;

Now {b1,b2,b3} is an orthonormal base, where b1,b2 are unit vectors that lie on the plane and are normal to each other, and b3 is the original plane's normal. The matrix that maps that plane onto the regular XY plane, is O :
[ b1.x b2.x b3.x 0 ]
[ b1.y b2.y b3.y 0 ]
[ b1.z b2.z b3.z 0 ]
[ 0 0 0 1 ]

Left-multiply your polyhedron's vertices with O*T and they should all be mapped onto a new XY plane around the new origin (point P) at a random rotation.
You can now look into the problem in 2D and continue with steps 2,3,4 as I described

[Edited by - someusername on December 29, 2005 9:51:28 AM]

A suggestion (w/o trig):

(1) transform the plane w/ all the points to 2D (hmm, this could be avoided, couldn't it?)
(2) choose a vertex va
(3) choose a vertex vbfrom the remaining vertices
(4) compute a line segment va to vb
(5a) iterate the now remaining vertices and look whether they lie on the same side as p does
(5b) if a vertex vi not obeying (5a) is found, replace vb by vi and continue iteration
(6) declare the surviving vb as new va, and continue w/ (3)

Haven't prooved this method yet...

EDIT: Yep, it seems that (1) need not to be done. With
k := ( p - va ) dot ( vb - va ) / | vb - va |
being the projected length of va to p, a "normal"
n := p - k * ( vb - va )
could be determined. Similarly the normal of any vertex investigated in (5b) could be computed. Then the test of (5b) consists of looking at the sign of the dot product of both "normals". This works well, since all points are known to reside in the plane.

EDIT2: The only caveat I see is if 3 vertices are co-linear, so that the normal of a vi becomes null. If such case is possible in the given environment, a distance test is needed as (5c) to replace vb by the closer vertex if needed.

[Edited by - haegarr on December 29, 2005 10:07:38 AM]

edit: missed part of OP about point p.
As few others suggested, just compute 2D coordinates of points on plane relatively to p, then sort other points by angle (by angle there i mean direction angle).

Note: if you deal with convex polygons that could have angle of exactly 180 degrees, there might be some minor problems. Such as
(0,0) ,(0,1) ,(0,2), (1,1)
(so looking from 0,0 , 0,1 and 0,2 will have same angle)
There you will need to do some sorting by distance i think.

If you don't want to do trig, you can write custom comparison that uses values of sine and cosine of angle directly to compare angles.

edit: you posted it's what you want...
you can compare directions without trig this way:

You can do that without normalizing too, bit more complicated but same idea.

[Edited by - Dmytry on December 29, 2005 9:08:53 AM]

for each vert calc dot(p, v_i-p) this will give you wich side of the line perpendicular to OP

for those which dot(p, v_i-p) is less than 0 ( on the left side of the 2d plane ) find the one with the smallest y component then the next smallest and so on. if 2 y components are the same you will need to have an extra var that tests the x component but you will have to see if you are walking left or right first. Then for those that dot(p, v_i-p) > 0 do the same exept start with the biggest y component and and sort in ascending order. again if 2 points have the same y you will need an extra var to tell wether you are walking left or right to pick the right one. This does make the assumption that you got the problem into a 2d one (where you can check x and y ) wich will probably take some trig though.

The procedure I described doesn't involve any trigonometric functions nor their inverse. You'll only need a matrix product and a vector cross product to transform the vertices in 2d.

Btw, if it doesn't seem to work, try using the transpose of (O*T) I mentioned, which is (transpose(T)*transpose(O)). I don't know what vector format you work with, that's why...
Just keep in mind that the plane's normal {a,b,c} should be transformed to {0,0,1}... That is:
O*T*transpose({a,b,c}) == transpose({0,0,1})
and you should figure out the correct order.

@Dmytry,
You are taking the test point p to be a vertex of the polyhedron. Clearly this case should be left out, as atan(0/0) is undefined