Find order of points to make a quadrilateral

Question

While giving an answer to "Given four coordinates check whether it forms a square", I came across this answer, which checks for a parallelogram, then for a right angle. This works, but only if the points coming in are in a certain order. Namely, P1 and P3 must be "opposite" from each other, not adjacent.

So, the question. If the four points coming in could be in any order, how can you sort them so that they are in the "correct" order to make a quadrilateral?

The simplest thing I could come up with is something like:

for each valid permutation of points[]{ // see below for "valid"
    generate line segment for:
        points[0] -> points[1]
        points[1] -> points[2]
        points[2] -> points[3]
        points[3] -> points[0]
    if any line segment crosses another // use cross product
        continue
    return permutation
}

I know that most permutations are simple rotations(0123 == 1230), so I can keep the first point 'fixed'. Also, I think I could cut it down by only considering what points are in the 0 and 2 of each permutation spots, since the order of the other two don't matter. For example, if 0123 is a polygon, 0321 is also, since it generates the same segments.

This leaves me with only three basic permutations to check:

• [0,1,2,3]
• [0,1,3,2]
• [0,2,1,3]

Each permutation has six segment-to-segment checks, so that's a total of 18 comparisons.

I can't think of any other way to do this, but it seems like I'm missing something. Is there a better way to do this? The answer given for the square question is good, but if I have to make an additional(up to) 18 checks to verify the points are in the correct order, it would be quicker just to use inter-corner distances.

Answer 1

Wouldn't it be simpler to do the following:

1. Check if points 0, 1 and 2 span a triangle (if they are co-linear the quadrilateral is degenerate too)
2. Check the following segments for intersection:

[0, 3] and [1, 2]
[1, 3] and [0, 2]
[2, 3] and [0, 1]

If none of them intersects, the quadrilateral is non-convex.

Otherwise, you should have exactly one intersecting case. You found your opposite vertices there.

Answer 2

Can't you simply check all of the below until you find one that's true? (that is, check P1 opposite each other point)

P3 = P1 + (P2-P1) + (P4-P1)
P2 = P1 + (P3-P1) + (P4-P1)
P4 = P1 + (P2-P1) + (P3-P1)

For the square variant, if they happen to be axis-aligned, you can do: (that is, the opposite point is the one which doesn't have a coordinate in common)

if (P1.x != P3.x && P1.y != P3.y)
  check P3 = P1 + (P2-P1) + (P4-P1)

if (P1.x != P2.x && P1.y != P2.y)
  check P2 = P1 + (P3-P1) + (P4-P1)

if (P1.x != P4.x && P1.y != P4.y)
  check P4 = P1 + (P2-P1) + (P3-P1)

otherwise return false

Answer 3

Each permutation has six segment-to-segment checks, so that's a total of 18 comparisons.

You do not need to check all the segments: it would be sufficient to check that segments [0-2] and [1-3] (i.e. the two diagonals) intersect. You need to check that the segments intersect, not the lines to which the segments belong, i.e. an intersection outside of the segments does not count.

Once you fix the starting point "A", you end up with six possible permutations:

Two of them (A-B-D-C and A-C-D-B) are good; the remaining four are bad. You can arrive at a good one with only two checks:

• Check the initial permutation; if it is good, keep it; otherwise
• Swap points 1 and 2, and check the permutation; if it is good, keep it; otherwise
• Revert to the original permutation, swap points 2 and 3, and keep that permutation; it is bound to be "good".

Answer 4

Implement a method called isParallelAndEqual(p0,p1,q0,q1). This checks if lines p1-p1 and q0-q1 are parallel and of equal length.

Given points a,b,c and d, the final result looks like:

ifParallelAndEqual(a,b,c,d)||ifParallelAndEqual(a,c,b,d)