We are asked to say if the passed three points are actually a triangle (alternatively, they could be collinear, lying on the same line); if it is acute (all angles are less than 90 degrees), right (one angle is exactly 90 degrees), or obtuse (one angle is more than 90 degrees); and if it is scalene (all sides have a different length) or isosceles. In case of equilateral triangle, we are allowed to give back an imprecise answer, falling back to isosceles.
Before even start thinking about coding, I think it is better to refresh the underlying theory, clarifying what I want to get.
Collinear points
Let's call our points A, B, and C. They determine three segments, AB, BC, and AC. If two of them are collinear, we get for free that the third one is collinear too. It is easy to figure out that, at least in a Euclidean geometry, it has no other chance.
Our job is to compare the slope of whichever two segments. If it is the same, the three points are collinear.
Given our two points, A = (ax, ay) and B = (bx, by), the slope of the line determined by them is: (by - ay) / (bx - ax).
Similarly goes for the other segment, say BC: (by - cy) / (bx - cx), so we could say that the three points are collinear if and only if:
(by - ay) / (bx - ax) = (by - cy) / (bx - cx)Cool. But you have to pay attention to a couple of details. Firstly, you don't want to divide by zero, and secondly you don't want to divide at all, if you just can avoid it. A division leads often to rounding problems, with consequent headaches.
So we'd better rewrite the equation above to multiply instead of divide. Also multiplications could give to the programmer their shares of trouble (overflow would probably be its name), but here the problem is designed to let them out of the window, since we deal with tiny numbers. This is the equation I am going to use in my code:
(by - ay)*(bx - cx) = (by - cy)*(bx - ax)Type by angles
Thanks to the Pythagorean theorem, we can easily detect if a triangle is right. As anyone should know, in a rectangle triangle, the sum of the squares of the lengths of the two catheti is equal to the square of the length of the hypotenuse.
Given the lengths of the three sides, it is just a matter of comparing the square of the biggest (let's call it SQx) against the sum of the square of the other two (SQy and SQz):
SQx < SQy + SQz -> obtuse SQx > SQy + SQz -> acute SQx = SQy + SQz -> rightType by sides
That's pretty easy. Assuming that we have the length of each side, if at least two of them are the same we say our triangle is isosceles. We could be more precise, and checking also if all the three of them have the same length (equilateral triangle), but this is not required, and so we should sadly avoid it.
Side length
Both the previous point require the sides length to work. Given two vertices coordinates, we calculate that side length applying (again) the Pythagorean theorem. Actually, to get the value, we should calculate the square of delta x and delta y, sum them, and then extract the square. But we'd better being lazy, and stop at the second step. Instead of calculating the length, get its squared value. In this way we'll avoid a costly operation, and also the usual rounding problems.
Besides, for determine the angles we are specifically requested for the squared values, and for the sides working with the actual value or its square is a non-issue.
This is what I have to do to calculate the squared length of a segment AB:
SQ(A,B) = square(B.y - A.y) + square(B.x - A.x)Work on triangles with class
Large part of the job is done. I just have to implement the solution. I choose C++ with gtest for the TDD support. It should be a non issue to adapt my code to other languages.
Firstly, a couple of type defines. We are working in a two-dimensional plane, where point are defined are pairs (abscissa, ordinate). And we'll need to operate to collections of exactly three points:
typedef std::pair<int, int> Point; typedef std::array<Point, 3> Points;Pair are a well know citizen of the STL nation, array joined the company with C++11. Letting us specify the number of elements in its declaration, it is more expressive than a vector in this context.
I designed a Triangle class having such private data members:
class Triangle
{
private:
enum Angle { OBTUSE, ACUTE, RIGHT };
Points vertices_; // 1
std::array<int, 3> squaredLengths_; // 2
bool collinear_; // 3
// ...
1. My triangle is described by its vertices.2. This data member is not strict necessity, it is just a way of saving some computation time using some more space.
3. Ditto.
The real job described above is done by three private function members:
class Triangle
{
private:
// ..
int squaredLength(const Point& a, const Point& b) // 1
{
return std::pow(b.second - a.second, 2) + std::pow(b.first - a.first, 2);
}
bool scalene() // 2
{
if(collinear_)
return false;
return !(squaredLengths_[0] == squaredLengths_[1] || squaredLengths_[0] == squaredLengths_[2] || squaredLengths_[1] == squaredLengths_[2]);
}
Angle angle() // 3
{
int ssq = squaredLengths_[0] + squaredLengths_[1];
return ssq < squaredLengths_[2] ? OBTUSE : ssq > squaredLengths_[2] ? ACUTE : RIGHT;
}
// ...
1. Utility function to calculate the squared length of the passed segment using the Pythagorean theorem. It is called by the constructor.2. Is this triangle scalene? If this is not an actual triangle (the three points are collinear) the question makes no sense. I could have thrown an exception, but I decided for a more forgiving behavior. Otherwise let's check if there is at least a couple of sides with the same length. Actually, for the reason described above, I check the squared lengths instead.
3. To ensure that I correctly apply the Pythagorean theorem, I have sorted the squared lengths (see the constructor). It is very easy now to determine if the triangle is obtuse, acute, or right.
In the public interface I left just the constructor and a method to get the required answer:
class Triangle
{
// ...
public:
Triangle(const Points& p) : vertices_(p), collinear_(false) // 1
{
if((p[1].second - p[0].second) * (p[2].first - p[0].first) == (p[1].first - p[0].first) * (p[2].second - p[0].second))
collinear_ = true;
squaredLengths_[0] = squaredLength(p[0], p[1]); // 2
squaredLengths_[1] = squaredLength(p[0], p[2]);
squaredLengths_[2] = squaredLength(p[1], p[2]);
std::sort(squaredLengths_.begin(), squaredLengths_.end());
}
std::string description() // 3
{
std::string result("triangle");
if(collinear_)
return "not a " + result;
Angle ang = angle();
result.insert(0, ang == OBTUSE ? "obtuse " : ang == ACUTE ? "acute " : "right ");
result.insert(0, scalene() ? "scalene " : "isosceles ");
return result;
}
};
1. The constructor create a triangle from a collection of three points. The points are stored in the private data member vertices_, the collinear_ flag is set accordingly to what we discussed in the section "Collinear points". A real life class should add more checking on the input parameters. Here I rely on the client fairness.2. Each side squared length is calculated and stored in the private data member squaredLengths_, then the array is sorted, following the natural sorting function, so that the longest one is last (position 2).
3. Build a string containing a triangle description.
Test cases
As usual, I let the design of my code to be driven by test cases. I'm using here the Google C++ Testing Framework (friendly known as googletest), but you should easily adapt them to any xUnit framework you like.
Firstly I have written the test cases provided by the problem itself. Here are the first and last of them:
#include "gtest/gtest.h"
TEST(TestTrilemma, CaseSample1)
{
Triangle triangle({{ Point(0, 0), Point(0, 4), Point(1, 2) }}); // 1
ASSERT_EQ("isosceles obtuse triangle", triangle.description());
}
TEST(TestTrilemma, CaseSample8)
{
Triangle triangle({{ Point(7, 7), Point(7, 7), Point(7, 7) }});
ASSERT_EQ("not a triangle", triangle.description());
}
1. Maybe is worthy spend a few words on this line. I am creating an object Triangle, passing to it a brace-enclosed initializer list (C++11 goodies) to initialize on the fly a temporary array object, as required by the constructor. Being this an rvalue, the move flavor for the Triangle vertices_ data member constructor will be called, resulting in sleeker code.Right. But why the double braces? Wasn't one brace enough? No, it wasn't enough. And this is a compiler, and not a language issue. Currently, the GCC compiler get sometimes confused by a single-braced initializer list. This is one of those cases. If you put just a single brace there, you should get a very confusing diagnostic output. But if you write the same code in a simpler way, like this:
Points ps = { Point(0, 0), Point(0, 4), Point(1, 2) };
Triangle triangle(ps);
You should get a cleaner message, a warning like "missing braces around initializer".Then I have added a few more test cases, exploring different setting. Here are some of them:
TEST(TestTrilemma, CaseCentered) // 1
{
Triangle triangle({{ Point(0, -2), Point(0, 2), Point(1, 0) }});
ASSERT_EQ("isosceles obtuse triangle", triangle.description());
}
TEST(TestTrilemma, CaseNegative) // 2
{
Triangle triangle({{ Point(-1000, -500), Point(-1000, -1000), Point(-100, -700) }});
ASSERT_EQ("scalene acute triangle", triangle.description());
}
TEST(TestTrilemma, CaseHuge3) // 3
{
Triangle triangle({{ Point(-1000, 0), Point(-1000, -1000), Point(1000, 1000) }});
ASSERT_EQ("scalene obtuse triangle", triangle.description());
}
1. What if the triangle is (sort of) centered on the plane origin?2. Could we have an issue on a Triangle lying in the plane negative quarter?
3. The problem requirements state that the Triangle points must be in the [-1000, 1000] range. I didn't enforced this constrain in the code, but I ensured with a number of tests that my class works fine with the biggest expected triangles.
No comments:
Post a Comment