Algorithm to join 4 co-ordinates such that it always results in a quadilateral

Question

We're given the coordinates of 4 points on the 2D plane. How can we find an order to join them with lines to form a quadilateral (whenever it's possible)?

Answer 1

Consider the partition of the plane obtained by drawing the three lines defined by the first three points. It defines 7 regions. You can easily find to which region the fourth point belongs by means of three signed area tests (algebraic area of the triangles ABD, BCD, CAD).

Drawing a quadrilateral in every case is straightforward (there can be one, two or three solutions per case).

In the example below, with D in the region -++, ADBC will do.

Actually two area evaluations are enough: if the first test returns - (regions -+-, -++ or --+), ADBC is a solution, else if the second test returns - (regions +-+ or +--), ABDC is a solution, else (regions ++- or +++) ABCD is a solution .

Answer 2

Consider the affine transform

Px = Ax + u (Bx - Ax) + v (Cx - Ax)
Py = Ay + u (By - Ay) + v (Cy - Ay)

It maps (0, 0) to A, (1, 0) to B and (0, 1) to C. (This puts the triangle ABC in a canonical position.)

Solving the 2x2 linear system

Dx = Ax + u (Bx - Ax) + v (Cx - Ax)
Dy = Ay + u (By - Ay) + v (Cy - Ay)

gives you the values of (u, v) corresponding to D.

Then,

if u < 0 => ABCD
else if v < 0 => BCAD
else => CABD

The resulting quadrilateral has the same orientation as the triangle ABC.

Answer 3

For the sake of clarity, I'm considering as a point p_n a point with coordinates (x_n, y_n).

In order to connect 4 points you could follow these steps:

1. Get the point p_1 with the smallest x.
2. Calculate the slope of the 3 lines that go from p_1 to each of the remaining points.
3. Connect p_1 with the point p_2 that composes the line with the greatest slope.
4. Connect p_1 with the point p_3 that composes the line with the smallest slope.
5. Connect the remaining point p_4 with p_2 and p_3.

Let me know if something is unclear.

Answer 4

EDIT: As pointed out in the comments, it only works in specific situations and thus is a bad answer.

The quadrilateral can be drawn by finding which pair of points amongst the 4 points is separated by the largest distance. Once this pair is found, the quadrileteral is drawn by linking the two remaining points with each point of the pair.

Answer 5

Edit: This answer has already proven to be wrong.

1. Calculate the center of the four points.
2. Enumerate the points in the counter-clock wise direction (or clockwise).
3. Link them together.

Answer 6

You can use a simplification of any of the well-known algorithms for convex hull. Jarvis would be easy. If the convex hull is a triangle, the quadrilateral is convex. Just insert the missing point anywhere in the edge list. If the convex hull is a line (2 endpoints), just sort all the points on either x- or y-coordinate to get a degenerate quadrilateral. (If closer to horizontal (abs delta x > abs delta y), use x for sorting, else use y.)

Answer 7

i think, you just need to join two points each time, we will get a line segment and check if the remaining other two points are on the same side of that line segments, if not thats not a line segment of required quadrilateral, if yes then proceed with different set of points (i.e on point can be one of the coordinate of this segment and other one would be form remaining two points) and check the same thing until u get 4 line segments

Answer 8

Look around for convex hull algorithms. One of them consists of two steps: building an ordinary polygon on a given set of vertices (which may be concave), then removing 'concave vertices' so that the remaining polygon becomes convex.

The first step is a solution for your problem.

Of course it is kind of overkill. For 4 vertices just set them in a sequence (in any order) then verify if line segments joining points 1-2 and 3-4 intersect; if so, swap points 2 and 3; or possibly edges 2-3 and 1-4 intersect – then swap points 3 and 4. Done.

To verify if segment AB and CD intersect test if points A and B are on opposite sides of the line CD and points C and D are on opposite sides of line AB.

To identify the side of a line PQ where a point K lies, calculate the Z-part of the PQ×PK vector product: (xq-xp)(yk-yp)-(yq-yp)(xk-xp). The expression is positive on one side of the line and negative on the other one (and zero on the line).

Answer 9

One can solve this problem very easily with the help of a function that says whether two line segments intersect.

Given points A, B, C, D, there's only three different orders to join up the vertices: ABCD, ABDC and ACBD (vertex A either connects to vertex B or it doesn't. If it does, there's two ways to order C and D. If it doesn't then A connects to both C and D and each of those must connect to B).

An ordering of the four points produces a quadrilateral if none of the edges intersect (except at the corners). That gives this procedure for finding a working order:

If AB intersects with CD then return ACBD.
If AD intersects with BC then return ABDC.
Otherwise return ABCD.

The proof that this works is easy:

1. both ABCD and ABDC include the edges AB and CD, so if those pair of edges intersect, the good order must be ACBD.
2. both ABCD and ACBD include the edges AD and BC, so if those pair of edges intersect, the good order must be ABDC.
3. if neither AB/CD and AD/BC intersect, then the order ABCD produces a quadrilateral.

The code for determining if two line segments intersect can be found online if you can't figure it out yourself.

Answer 10

Here is a trivial, non-mathematical way of doing it. I've tried it on several examples and could not prove it wrong. Please let me know if you do or know how to make it better:

1. Choose the two points that are on the right of the others, say point 1 and 2.
2. Link points 1-2 together, as well as points 3-4.
3. Each point must be linked to only two other points so there are only 2 possibilities: linking points 1-3 and 2-4, or points 1-4 and 2-3.
4. Check if each line intersects another.

That should do it.

Note: when choosing the first two points, here are some special cases:

1. Point 1 is on the right of all others, but points 2 and 3 are on the same x coordinate. Pick the point that's closest to point 1.
2. If three points 1,2 and 3 have the same x-coordinate, link the two that are closest to each other. If the points are evenly separated, pick one of the two possibilities.

Answer 11

A few stages, assuming the end result needs to be 4 couples of points (and/or the equation of the line between them):

1. Take any three points, and make a triangle.
2. If the forth point is inside the traingle, swap it with ny of the three.
3. Having only the last point left, calculate which two point you want to attach it to. This is done by playing with the line eqations and finding where the intersecting points are. Clarification below.
4. Return two sides of the triangle + the 2 lines between the forth point and the ones you chose from stage 2.

Step 2 clarification:
Let us say that point A is not in the triangle (which is BCD). Every line devides the plain into two sides. we want to find the point (B, C or D) s.t. the line between it and A runs between the other two (they are on opposite sides of the line). This is the point we DO NOT want to attach to A.

Example: Given A(0,0), B(10,0), C(10,10) and D(0,10). We have the triangle BCD. The line BC leaves A & D on the same side of the plain. So does DC. The line AC leaves B & D on opposite sides of the plain - so we want to connect A to B & C.