• Advertisement
Sign in to follow this  

Finding a convex polygon

This topic is 4402 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Suppose you have N points, {v1,...,vn}, in a plane with a normal n. The points are given in no particular order. Suppose the points are vertices of a convex polygon and p is any point in the interior of the polygon, 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? · is the dot product × is the cross product Any thoughts? No rating++ for anyone suggesting a brute force method [wink] P.S. this is not homework but something that I came across when decomposing polyhedra for a BSP tree. Although the solution to this problem is unlikely to be the best approach for my BSP tree, I thought I'd share it with those who like to solve these kinds of things... and maybe I'll learn something new [smile]

Share this post


Link to post
Share on other sites
Advertisement
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

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
Aww, man! You guys are too smart! [smile]

Can you do it without trig functions?

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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:

// a and b is normalized. Returns true if a's heading has bigger number on "clocks" than b
// so if a is at 2 hours and b is at 3 hours , it return false.
bool compareangles(vec2 a, vec2 b){
if(a.x>0)
{
if(b.x<0)return false;
return a.y>b.y;
}else
{
if(b.x>0)return true;
return a.y<b.y;
}
}





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

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
edit: nevermind, i missed "and p is any point in the interior of the polygon". So just use p .

someusername, trigonometry in your description:
Quote:

find the angles of all vertices to the new origin (point p)

Share this post


Link to post
Share on other sites
Oops, you're right! It smells like atan() in there. I somehow had the impression that this exclusion of trigonometry was specific to only finding the positions of the vertices on the new plane. It shouldn't be that exprensive to calculate a bunch of atans() though. Unless -of course- this is called an insane amount of times per frame!

Share this post


Link to post
Share on other sites
Quote:
Original post by someusername
Oops, you're right! It smells like atan() in there. I somehow had the impression that this exclusion of trigonometry was specific to only finding the positions of the vertices on the new plane. It shouldn't be that exprensive to calculate a bunch of atans() though. Unless -of course- this is called an insane amount of times per frame!


Well, you're right in that it scales well. I just thought I'd better throw a wrinkle in the problem since you solved it so fast [wink]

Share this post


Link to post
Share on other sites
Quote:
Original post by someusername
Oops, you're right! It smells like atan() in there. I somehow had the impression that this exclusion of trigonometry was specific to only finding the positions of the vertices on the new plane. It shouldn't be that exprensive to calculate a bunch of atans() though. Unless -of course- this is called an insane amount of times per frame!

Agreed. Also, I posted code how to "compare angles" of unit directions directly without computing the angle, that's really very simple to do. It even could be done without normalizing or dividing (using pseudo cross product and few additional things), tho code will be longer.

Share this post


Link to post
Share on other sites
@jjd
Quote:

I wrote on a previous reply
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.

This is not correct. You have to use that procedure to find 2 random points on the plane, then find the vector from one to another. Normalize it and you have b1.
I just thought I'd mention this, since I noticed it in the first place.
There is enough feedback from many posters though, I'm sure you can optimize this to better suit your needs.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
For hints on implementing this efficiently, you can look for information on the Graham scan algorithm. Graham's scan is for finding a convex hull, and I think it's exactly what's been described in this thread, except that it is designed to work even when there are points that aren't on the convex hull.

Graham's scan starts by sorting the points in counterclockwise order. Efficient implementations usually find an extreme point first. Then the points can be efficiently sorted by angle relative to the extreme point by just using cross products for comparisons.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
For hints on implementing this efficiently, you can look for information on the Graham scan algorithm. Graham's scan is for finding a convex hull, and I think it's exactly what's been described in this thread, except that it is designed to work even when there are points that aren't on the convex hull.
An improvement over Graham's algorithm is Andrew's algorithm.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement