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.”
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)
suppose you want to connect points A through F.
- Calculate O by taking the sum of all the X/Y coordinates, and dividing by the number of points.
- For every point, calculate the offset from point O, and then use atan2(dy,dx) to get the angle.
- 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.