Determining ordering of vertices to form a quadril

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

A morton-curve or z-curve will deliver it. But I suggest a hilbert-curve or a moore-curve because of better space filling attributes.

Answer 2

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?

Answer 3

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

Answer 4

There is a solution which does not require computing a "center", involves only a few multiplications and additions, and gracefully handles degenerate cases (such as all points collinear).

Consider a quadrilateral with corners ABCD (ie there are lines AB, BC, CD, and DA).

Consider the four triangles ABC, ABD, ACD, BCD

There is a simple formula for working out the area of each triangle, see http://www.cs.princeton.edu/~rs/AlgsDS07/16Geometric.pdf page 9, if the vertices are (Ax, Ay), (Bx, By), (Cx, Cy)

Area = (Bx - Ax)(Cy - Ay) - (By - Ay)(Cx - Ax)

If the area if positive the points are counter clockwise, negative they are clockwise, zero they are collinear.

It is possible for a non-intersecting quadrilateral to have three collinear points. So one of the triangles ABC, ABD, ACD, BCD could have area zero. But if two of them have zero area, it means ABCD must be collinear and so all four triangles have zero area. In this case, a nonintersecting arrangement is impossible.

So calculate the areas corresponding to ABC, ABD, and ACD (you only need to consider three triangles).

If two of them have zero area, all three will have zero area, the four points ABCD are collinear.

If one of them has zero area, pick the other two areas.

If none of them has zero area, just pick any two of the three areas.

If the quadrilateral does not intersect, then these two triangles must wind the same way, ie both clockwise or both counterclockwise. Which means the product of the two areas must be positive (a positive by a positive or a negative by a negative). So simply form the product of the two areas, both of which are nonzero, to get a non zero result. If the product of the areas is greater than zero, the quadrilateral does not self-intersect, if it is less than zero it does self-intersect.

Answer 5

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).