Finding a polygon out of several points

OpenGL
1

Hi,

is there a efficient way of constructing a polygon of n sides from n given points? All the points lie on the same plane, so the polygon can always be constructed. I am looking for a fast way of doing it other than “for each point in the list, caculate the distance between them and store the shorter. Mark those points as sharing an edge. Repeat until n edges are found.”

Thanks!

2

I think you’re asking a lot considering the amount of information you’re giving.
The thing is that you’re not saying what type of polygon you’re looking for.

The method you’re describing seems to be a shortest path method. But that will not work with all polygons (think of star-shaped polygons).

If you’re looking for something circle-like, how about sorting the points by the angle they make with the center of mass? (Note that this may create a different polygon than intended, but at least it will connect all points)

E.g.
suppose you want to connect points A through F.

 

      A
                      F

    B       O
                   E


              D
        C
  1. Calculate O by taking the sum of all the X/Y coordinates, and dividing by the number of points.
  2. For every point, calculate the offset from point O, and then use atan2(dy,dx) to get the angle.
  3. sort the points on angle (you can use qsort for that), and insert them into whatever structure you use to store your polygon definition

Of course, if all points are already centered around (0,0), you can skip step 1 and simplify step 2.

3

Originally posted by T101:
I think you’re asking a lot considering the amount of information you’re giving.
The thing is that you’re not saying what type of polygon you’re looking for.

Sorry, this is because the only restrictions the points obey is that all of them lie on the same plane. I’m looking for something rather generic.

[b]
The method you’re describing seems to be a shortest path method. But that will not work with all polygons (think of star-shaped polygons).

[/b]
Oh, I did not even noticed that my method could not handle non-convex polygons! :stuck_out_tongue:

[b]

If you’re looking for something circle-like, how about sorting the points by the angle they make with the center of mass? (Note that this may create a different polygon than intended, but at least it will connect all points)
[/b]
I see what you mean. I’ll try to study these cases. However, I expect mine is not one of them.

[b]
E.g.
suppose you want to connect points A through F.

 

  A
                  F

B       O
               E

          D
    C

1. Calculate O by taking the sum of all the X/Y coordinates, and dividing by the number of points.
2. For every point, calculate the offset from point O, and then use atan2(dy,dx) to get the angle.
3. sort the points on angle (you can use qsort for that), and insert them into whatever structure you use to store your polygon definition

Of course, if all points are already centered around (0,0), you can skip step 1 and simplify step 2.[/b]
You have helped me a lot. Thank you very much!