Determining ordering of vertices to form a quadrilateral

Question

Suppose I have 4 vertices in 2D space. Does anything know of an efficient algorithm which will give me an ordering of the vertices which corresponds to a simple quadrilateral? That is, it will label the vertices 1, 2, 3, 4 so that if I follow 1-2, 2-3, 3-4 I will have traced a simple (i.e. non-intersecting) quadrilateral.

Just providing the name of a standard algorithm which I can google would be fine.

Answer 1

If your shape is convex, you can go in winding order around the barycentre of your points (i.e. the centre of gravity, or "average"):

B = (X_1 + X_2 + X_3 + X_4) / 4

Both coordinates of each vertex will be either above or below the corresponding coordinate of the barycentre:

 (-,+)                   (+,+)
   X                       X

              B
      X
    (-,-)               X
                      (+,-)

So starting at any point, just move to one point for which only one of the two signs changes, but not both.

If your shape is not convex, you could first triangulate it with an interior edge, apply the vertex ordering with consistent orientation for each triangle, and then merge the edges by cancelling out the pairwise-opposite interiors.

Note that for a non-convex set of points (i.e. a set where one point is contained in the open interior of the convex hull of the set), there may be more than one quadrilateral with those points as vertices (think of all the ways of joining the inner vertex to two of the outer ones).

Answer 2

You may be interested in methods of convex hull computing, such as Graham scan.

Answer 3

You can just google for sorting points in clockwise order and you get e.g.:

Sort four points in clockwise order
Sort points in clockwise order?