8

I currently have a vector of points

vector<Point> corners;

where I have previously stored the corner points of a given polygon. Given that, I know for sure that the points form a simple polygon that does not contain any self-intersecting edges. However, in the process of storing these vertices, the order in which they connect to each other was not preserved.

I now have a function that, given a vector of points, connects them and draws me a closed figure. However, I need to give this function the sequence of points in the order they need to be connected. Can anyone suggest a way that I could sort these points in the correct order? They form a very simple concave polygon, not a convex hull. An algorithm to find the center point among all the (7) points would also be helpful :)

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Everaldo Aguiar
  • 4,016
  • 7
  • 26
  • 31
  • Is there a particular polygon you know the points make? What have you tried? – AJG85 Sep 13 '11 at 21:13
  • Yes, I know which polygon the points map to. I have tried randomizing the points and checking if the edges produced intersect. And if they don't, usually I get the correct answer. However, I would like to have something simpler than that. – Everaldo Aguiar Sep 13 '11 at 21:50
  • 1
    Am I missing something? Why not take the average of the points as the center and, representing them in polar, simply connect the points in angular order about the center? Others have pointed out that there is generally no unique concave polygon, but this should produce *a* simple polygon. – phs Sep 14 '11 at 00:16

3 Answers3

11

There is no unique solution for a concave polygon:

enter image description here

The convex polygon could be find uniquelly as the convex hull of the points (if you know that the points build a convex polygon).

Jiri Kriz
  • 9,192
  • 3
  • 29
  • 36
  • Thanks for the nice and pretty looking images :) I knew there was no unique solution to it, though I thought there would be some way of at least assuring that I would order the points in some fashion that would prevent the edges from crossing. – Everaldo Aguiar Sep 13 '11 at 21:52
  • Now that I think about it, I don't think that is possible either. Maybe I'll have to go back in my code, label things and store information about connectivity – Everaldo Aguiar Sep 13 '11 at 21:53
8

A given set of points can generally be joined up many ways to form a non-self-intersecting polygon. You may be out of luck unless you have more information about the kinds of polygons the points could represent.

Ned Batchelder
  • 364,293
  • 75
  • 561
  • 662
  • A good example is four points in a square, with one point in the middle. The general shape is obvious, a square with a quarter missing, but which quarter is impossible to say. – Mooing Duck Sep 13 '11 at 21:22
  • Although you can at least give an algorithm for the center point. – Mooing Duck Sep 13 '11 at 21:23
  • @Mooing Duck How could you give an algorithm for the center point if you don't even know the shape? You can take the weighted average of the vertices, but that is not equal to the center point. – H. Brandsmeier Sep 13 '11 at 21:31
  • @cideous: oh center of mass vs average position? Yeah, you're right. – Mooing Duck Sep 13 '11 at 21:32
  • Thanks for the discussion, guys. I suspected there wasn't a general solution to this so now I'm convinced that the best way to go about it will be to simply write a quick routine that solves this specific case. That's all I need in fact. – Everaldo Aguiar Sep 13 '11 at 21:57
7

1. Heuristic to determine the shape

There is no unique solution so there is no simple algorithm. You could try to somehow mimic your intuition.

  • start by a random point and connect each point to its closest neighbor. Then connect the last point to the first one.
  • start by selecting a point and its closest neighbor and connect them by a line. Now iteratively add another point. Always select the point which minimizes the angle between the last line segment and the newly added line segment.

Both methods don't really work in general, they don't even guarantee to avoid intersections. You can try to address this by backtracking, if you detect an obvious error (e.g. an intersection) then backtrack to the last point of decision and take the "second best" approach instead, ....

But again as the solution is not unique, don't expect too much from those heuristics.

2. Average of the vertices

The average point for the vertices is easy to compute. Just add all points together and divide through the number of points you just added, this is the average. What you are probably more interested is the center point in the sense of "Center of mass", see below.

3. Center point

To determine the center of mass you first have to define the shape. That means you have to do something like step 1.

An easily implemented method to compute the center point given the polygon is.

  • Put a bounding box around the polygon.
  • Randomly generate points inside the bounding box.
  • For each of those points determine if it is inside the bounding box, if not, then throw it away. To determine if a point is inside an arbitrary polygon use a ray test.
  • For all points that you kept, apply approach 2. The Average point of those points is a good approximation to the center point.
H. Brandsmeier
  • 957
  • 5
  • 19
  • Great overview. You brought up a good point. I do know what shape I will be representing. In fact I have it right here in front of my face. I will try to derive some simple algorithm that orders the points. I don't need it to be general, it only needs to work for this case. – Everaldo Aguiar Sep 13 '11 at 21:55