C++ 2D shape intersections - template reduction

I've created a short piece of code to determine whether or not various 2D shapes (circles/lines/rectangles) intersect. It was a job interview question, but now it's just about self-improvement.

I'd like any suggestions for how best (in terms of code cleanliness and scalability) to handle the fact that in implementation terms, lines only know about lines, circles know about lines and circles, and rectangles know about all three shapes. However from the user's point of view, the intersect method should be callable from any shape to any other shape, such as being called on a rectangle object from a line object.

At the moment, the templated intersect(Type1 &&a, Type2 &&b) function just calls the intersect method of object a on object b, which will result in some situations where the object being called doesn't have a method for the type of object it's being called on. To solve that, I implemented a templated method inside both Line and Circle which acts as a catchall by swapping the calling object with the called object.

template 
bool intersect(Type a) {
    return a.intersect(*this);
}

However, that feels like a pretty weak solution, and not very scalable. Is there a way to do without the catchall methods inside the shape classes?
The full code is below:

```
#include
#include

using namespace std;

// Point class, defined by x and y coordinates
class Point {
public:
double x, y;
Point(double xPos, double yPos)
: x(xPos)
, y(yPos)
{ }
// Calculate distance between points
double distance(Point a) {
double dX = x - a.x;
double dY = y - a.y;
return sqrt(pow(dX,2) + pow(dY,2));
}

};

// Line class, defined by two endpoints
class Line {
public:
Point start, end;
Line(Point start, Point end)
: start(start)
, end(end)
{ }
// Return length of line
double length() {
retu

The intersect function

First of all, I do believe that intersect should only be a free function that takes any number of mathematical objects and returns whether these objects intersect at some point (or line, or other). I also believe that your shape classes should expose enough properties so that intersect can be computed between any two objects without needing to access the classes internals. Therefore, I would simply define intersect as an overload set of free functions and I would drop the intersect methods in the classes.

Handle divisions by zero

Your gradient method will consistently make a division by zero with vertical lines. While this is the "expected behaviour" of a gradient method, be sure that your computations using gradient handle this special case before calling the method.

For example, your method onLine needs to be fixed. Currently, it will perform a division by zero because of gradient when the line is vertical. Let's add a condition at the beginning of onLine to handle this case:

// Handle vertical lines
if (start.x == end.x) {
    return a.x == start.x;
}

The std::hypot function

Instead of std::sqrt(std::pow(dX,2) + std::pow(dY,2));, you could use the standard library function std::hypot:

return std::hypot(dX, dY);

That said, be aware that the function might be a little slower than your formula since it is implemented in such a way that it avoids overflows and underflows in the intermediate stages of computation. That's speed vs. security.

Comparing distances

In Circle::intersect(Circle) you compare distances to know whether two circles intersect. While it works, it is generally advised to compute squared distances instead of distances because it avoids to compute a potentially expensive std::sqrt. The function could be rewritten as follows:

bool Circle::intersect(Circle a) {
    double sqr_dist = a.centre.squared_distance(centre);
    return sqr_dist <= std::pow(a.radius + radius, 2);  
}

Where Point::squared_distance(Point) represents the squared distance between two points:

double Point::squared_distance(Point a) {
    double dX = x - a.x;
    double dY = y - a.y;
    return std::pow(dX,2) + std::pow(dY,2);
}

Lazy evaluation

Compute only what you need. If something can be computed later without a loss of efficiency, then compute it later. That's what we call lazy evaluation. Take for example these lines from the line-circle intersect function:

// Since discriminant >= 0, find roots
double x1 = (-B+sqrt(discriminant)) / (2*A);
double y1 = m*x1 + b;
double x2 = (-B-sqrt(discriminant)) / (2*A);
double y2 = m*x2 + b;

// If either root exists on line, the line intersects the circle
if (a.onLine(Point(x1,y1))) { 
    return true;
} else if (a.onLine(Point(x2,y2))) {
    return true;
}

It appears that if a.onLine(Point(x1,y1)) is true, you simply don't need to compute x2 and y2, which means that you can rewrite your code like this:

double x1 = (-B+sqrt(discriminant)) / (2*A);
double y1 = m*x1 + b;
if (a.onLine(Point(x1,y1))) { 
    return true;
}

double x2 = (-B-sqrt(discriminant)) / (2*A);
double y2 = m*x2 + b;
if (a.onLine(Point(x2,y2))) {
    return true;
}

Use strongly typed enums

For your orientation function, the return type int is at best misleading since the values only represent abstract concepts. You should drop the int and replace it by a dedicated type Orientation, implemented as a strongly typed enum class or enum struct:

enum struct Orientation
{
    colinear,
    clockwise,
    counter_clockwise
};

With such a type, you don't even have to comment what the constants mean anymore and you make sure that your enumeration won't implicitly convert to an integer. It's all benefit :)

Miscellaneous pedantic tidbits

Syntax, idioms... we leave the real of semantics and focus on writing idiomatic C++ code. While it won't change a thing for users, it may please people reading your implementation:

-
You should always fully qualify the functions you use, even those from the standard library. That means that instead of pow, sqrt, etc... you should be using std::pow, std::sqrt, etc... That means searches for std:: easier and may avoid some name clashes.

-
There are several places in Rectangle where you have redundant collections of if that you could simplify. For example:

if (pointOn(a.lowerLeft)) {
    return true;
} else if (pointOn(a.upperRight)) {
    return true;
} else if (pointOn(a.upperLeft)) {
    return true;
} else if (pointOn(a.lowerRight)) {
    return true;
}
return false;

You can change it to a single return statement without hindering readability:

return pointOn(a.lowerLeft)
    || pointOn(a.upperRight)
    || pointOn(a.upperLeft)
    || pointOn(a.lowerRight);

-
Please, try to always use curly braces with if, even when there is a single statement to execute. Otherwise, you may someday be subject t

StackExchange Code Review Q#95935, answer score: 4