Do four points create a square?

Can you determine programmatically if four points create a square? This was the programming problem posed at Programming Praxis.

The idea is to find the distance between all points. Essentially, you create a complete graph, where the points are your nodes and the distances are the edges. Four of the distances should be equal. These represent the sides of the square. The other two (representing the diagonals), must be greater than any side but equal to each other, for all but the degenerate case in which the length of the sides of the square is zero (Is this a square?).

Below is my unsophisticated solution:

First, two helpers

//	Point
//	A container for a 2-D Point
public class Point {
	public double X { get; set; }
	public double Y { get; set; }
	
	public Point(double x, double y) {
		this.X = x;
		this.Y = y;
	}
}

//	EuclidianDistanceSquared
//	Finds the square of the Euclidian distance.
//	Returns: The Euclidian Distance between the two points.
public double EuclidianDistanceSquared(Point p1, Point p2) {
	return (p2.X - p1.X) * (p2.X - p1.X) + (p2.Y - p1.Y) * (p2.Y - p1.Y);
}

I thought it easiest to have a class to instantiate points and a helper distance function. When I originally created the metric, is used strict Euclidian distance

public double EuclidianDistance(Point p1, Point p2) {
	return Math.Sqrt((p2.X - p1.X) * (p2.X - p1.X)  + (p2.Y - p1.Y) * (p2.Y - p1.Y));
}

but since I was just comparing distances, I figure I could add the optimization of not computing the square root.

Now the IsSquare function will compute the six distances, store them in a list and sort the list. This alleviates the need to figure out which distances are sides and which are diagonals. The first four points in the list should be the distances of the sides of the square and the last two should be the distances of the diagonals. Finally, to determine if these point are indeed a square, the first and fourth entries in the list should be equal (all sides are equal) and the fifth and sixth entries (the lengths of the diagonals) should also be equal. For good measure, I also check if the length of one of the sides is less than or equal to the length of a diagonal.

//	IsSquare
//	Determines if four points create a square
//	Returns: True if the four point create a square, false otherwise.
public bool IsSquare(Point p1, Point p2, Point p3, Point p4) {
	double p1p2 = EuclidianDistanceSquared(p1, p2);
	double p1p3 = EuclidianDistanceSquared(p1, p3);
	double p1p4 = EuclidianDistanceSquared(p1, p4);
	double p2p3 = EuclidianDistanceSquared(p2, p3);
	double p2p4 = EuclidianDistanceSquared(p2, p4);
	double p3p4 = EuclidianDistanceSquared(p3, p4);
	
	List<double> distances = new List<double>() { p1p2, p1p3, p1p4, p2p3, p2p4, p3p4 };
	distances.Sort();
	
	return (distances[0] == distances[3]) && (distances[4] == distances[5]) && (distances[0] <= distances[4]);
}

Remarks:

Certainly some would argue this isn’t an elegant solution to the problem but I think it’s very readable and hopefully understandable to someone unfamiliar to the problem/solution.

I think it would be good when using metrics/distances to create a metric or distance class to be able to easily choose a distance function for use between points, lines, planes, etc.

Complete Source

//	Point
//	A container for a 2-D Point
public class Point {
	public double X { get; set; }
	public double Y { get; set; }
	
	public Point(double x, double y) {
		this.X = x;
		this.Y = y;
	}
}

//	EuclidianDistanceSquared
//	Finds the square of the Euclidian distance.
//	Returns: The Euclidian Distance between the two points.
public double EuclidianDistanceSquared(Point p1, Point p2) {
	return (p2.X - p1.X) * (p2.X - p1.X) + (p2.Y - p1.Y) * (p2.Y - p1.Y);
}

//	IsSquare
//	Determines if four points create a square
//	Returns: True if the four point create a square, false otherwise.
public bool IsSquare(Point p1, Point p2, Point p3, Point p4) {
	double p1p2 = EuclidianDistanceSquared(p1, p2);
	double p1p3 = EuclidianDistanceSquared(p1, p3);
	double p1p4 = EuclidianDistanceSquared(p1, p4);
	double p2p3 = EuclidianDistanceSquared(p2, p3);
	double p2p4 = EuclidianDistanceSquared(p2, p4);
	double p3p4 = EuclidianDistanceSquared(p3, p4);
	
	List<double> distances = new List<double>() { p1p2, p1p3, p1p4, p2p3, p2p4, p3p4 };
	distances.Sort();
	
	return (distances[0] == distances[3]) && (distances[4] == distances[5]) && (distances[0] <= distances[4]);
}

Here is a sample program using the IsSquare function:


Point p1 = new Point(0,0);
Point p2 = new Point(1,1);
Point p3 = new Point(0,1);
Point p4 = new Point(1,0);
		
Console.WriteLine(IsSquare(p1,p2,p3,p4));

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>