# Points on Polygons

Now my planes are sorted, I have say 20 points in space (pixels with a depth measurement) which all lie on the same plane, but I don’t know which are vertices and which arn’t. Is there a bodge way of merging all these points together to create a polygon? (the pixels are all connected)

don’t know if I explained that too well

thanks

gav

thanks

gav

Okay, if I understand you correctly you want to create a polygon of several points in a certain space. How bout calling glBegin(GL_POLYGON); and then adding all the points with glVertex3f() ?

–> Divide Overflow
“I’m a feature, not a bug”

That will work but the problem is that I will have to write a little algorithm that will choose the outer points/vertices and sort hem in the correct order for placing into the vertex call. I just wondered if I could just say ‘I have a polygon and all these points lie on it, finish it off for me’ if you see what I mean.

thanks

gav

I don’t think this is possible because in some cases, more than 1 polygon can be made from the same points.

(The next message contains an example)

See next message
…|…
…|…
…|…
.|/.

[This message has been edited by wolfman8k (edited 09-04-2000).]

ahh! the pics got messed up. This will work:

suppose you have four points:

1…2.
…3…

4…

(ignore the “.” their just placeholers)

Now, you can draw the polygon in two orders:
1, 2, 3, 4 - This will give you a boomerang shape.
1, 3, 2, 4 - This will give an arrow shape.

As you can see, I don’t think their is a solution to your problem. You will just have to store the order in which to draw the poly.

Hope this helps

[This message has been edited by wolfman8k (edited 09-04-2000).]

Actually, in general, there is a solution to this problem if you require the solution to be a convex polygon. What you want to find from the set of points is the convex hull of that set of points. And there are many methods for doing this. Here is a pretty good link that addresses the various methods for generating 2D and 3D convex hulls: http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html

We have some convex hull code, but its in java, so was just checking that there are no short cuts before I go and hack the code to c!

cheers for the help

gav

OK. So here is a pretty simple solution, assuming you know some linear algebra and a little extra math. I assume you can code it from there.

OK. First of all, take three points out of your set (you said that all points in space were certain to reside on a plane). Well, using the cross product of two vectors produced by these three points (assuming they’re non collinear) you can determine the normal vector of the polygon. Now, transform all the points so that the plane that they were on conincides with the x,y axis. Now that you have all the points on the XY plane, your job is simplified. You can perform what is commonly called the rubber-band convex hull algorithm (or any optimal 2D convex hull algorithm for points will do), to calculate the convex hull of this set of points. Once you have that convex hull (which is a sequence of points in clockwise order most of the time), you can re-transform those points into the original plane, by reversing the transformation you applied then. Having that convex hull, within the global 3D coordinates, you can render this polygon with absolutely no problem in OpenGL.