How to Represent a Geometric Line Programmatically?

Assuming that your square might be rotated against whatever coordinates system you have in place, you can't rely on there being any repetition of X and Y values in your four points.

What you can do is calculate the distances between each of the four points. If you find the following to be true, you have a square:

1. There are two points, say A and C which are distance x from each other, and two other points, say B and D which are also distance x from each other.

2. Each point {A, B, C, D} is an equal distance from the two points which aren't x away. i.e.: If A is x away from C, then it will be z away from both B and D.

Incidentally, the distance z will have to be SQRT((x^2)/2), but you don't need to confirm this. If conditions 1 and 2 are true then you have a square. NOTE: Some people are concerned about the inefficiency of square root. I didn't say that you should do this calculation, I just said that if you did you would get a predictable result!

The bare minimum of work that you would need to do would be to pick a point, say A and calculate the distance to each of the other three points. If you can find that A is x from one point and z from two other points, then you just need to check those two other points against each other. If they are also x from each other then you have a square. i.e.:

• AB = z
• AC = x
• AD = z

Since AB = AD, check BD:

• BD = x

Just to be sure, you need to check the other sides: BC and CD.

• BC = z
• CD = z

Since AC = BD and since AB = AD = BC = CD, this is therefore a square.

Along the way, if you find more than two distinct edge distances then the figure cannot be a square, so you can stop looking.

Working Example Implementation

I have created a working example on jsfiddle (see here). In my explanation of the algorithm, I use arbitrary points A, B, C, and D. Those arbitrary points happen to be in a certain order for the sake of walking through the example. The algorithm works even if the points are in a different order, however, the example doesn't necessarily work if those points are in a different order.

Thanks to: meshuai, Blrfl, MSalters and Bart van Ingen Schenau for useful comments to improve this answer.

As you already suggest in your question, there is a big difference between implementing a formula, and implementing a calculation routine. Your paper solution is a routine, not a formula.

• You needed paper to write down numbers as intermediate results. Your algorithm will need something similar. Algorithms for solving systems of equations typically manipulate a matrix (2D array) of numbers. Put your equation factors into an 2D array, and try to describe the substitions as an operation on that matrix.

• When solving this on paper, you take decisions along the way. Eg. You choose to combine the first and third equation and solve that towards R. Then you used the second equation to solve p. This will not always work if there are some 0 factors in your equation. You might need to solve towards another variable, or combine the equations in a different order. The algorithm needs to take into account all these scenarios.

• Your problem is 'overdetermined': In general, 2 lines in 3D will not intersect. It will require a 'lucky shot' (special case) for them to intersect. Your paper example happens to have a solution. And it happens to be round numbers: easy to check. What if your first solution for P would be 1.0 and your second solution would be 0.9999999? Would that be a rounding error of the algorithm, or would the problem have no solution?