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 <typename Type>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 <iostream>#include <cmath>using namespace std;// Point class, defined by x and y coordinatesclass 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 endpointsclass Line {    public:        Point start, end;        Line(Point start, Point end)            : start(start)            , end(end)        { }        // Return length of line        double length() {            return start.distance(end);        }        // Return true if point a exists on this line segment        bool onLine(Point a) {            if (a.x <= max(start.x, end.x) && a.x >= min(start.x, end.x) && a.y <= max(start.y, end.y) && a.y >= min(start.y, end.y)) {                double m = gradient();                double b = yIntercept();                return a.y == m * a.x + b;            }            return false;        }        // Return gradient of line        double gradient() {            double dX = start.x - end.x;            double dY = start.y - end.y;            return dY/dX;        }        double yIntercept() {            double m = gradient();            return start.y - m*start.x;        }        // Return orientation of line endpoints & point a        int orientation(Point a) {            double val = (end.y - start.y) * (a.x - end.x) - (end.x - start.x) * (a.y - end.y);            if (val == 0) {                return 0;   // 0 = colinear            } else if (val > 0) {                return 1;   // 1 = clockwise            } else {                return 2;   // 2 = counter-clockwise            }        }        // Return true if this line intersects line a        bool intersect(Line a) {            // Orientations: 0 is colinear, 1 is clockwise, 2 is counter-clockwise            int o1 = a.orientation(start);            int o2 = a.orientation(end);            int o3 = orientation(a.start);            int o4 = orientation(a.end);            // General case - each line's points are on opposite sides of the other line            if (o1 != o2 && o3 != o4) {                return true;            // Line a and this line's start are colinear and this line's start lies on line a's segment            } else if (o1 == 0 && a.onLine(start)) {                return true;            // Line a and this line's end are colinear and this line's end lies on line a's segment            } else if (o2 == 0 && a.onLine(end)) {                return true;            // This line and a.start are colinear and a.start lies on this line segment            } else if (o3 == 0 && onLine(a.start)) {                return true;            // This line and a.end are colinear and a.end lies on this line segment            } else if (o4 == 0 && onLine(a.end)) {                return true;            }            return false; // Doesn't fall in any of the above cases        }        // Catch-all intersect function in case intersect is called on a higher shape        template <typename Type>        bool intersect(Type a) {            return a.intersect(*this);        }};// Circle class, defined by centre point and radiusclass Circle {    public:    Point centre;    double radius;    Circle(Point centre, double radius)        : centre(centre)        , radius(radius)        { }    // Return true if this circle intersects line a    bool intersect(Line a) {        // Line equation coefficients: y = mx + b        double m = a.gradient();        double b = a.yIntercept();        // Circle equation coefficients: (x - p)^2 + (y - q)^2 = r^2        double p = centre.x;        double q = centre.y;        double r = radius;        // Quadratic equation coefficients: Ax^2 + Bx + C = 0        double A = pow(m,2) + 1;        double B = 2*(m*b - m*q - p);        double C = pow(q,2) - pow(r,2) + pow(p,2) - 2*b*q + pow(b,2);        // A discriminant < 0 results in imaginary roots, therefore line does not intersect circle        double discriminant = pow(B,2)-4*A*C;        if (discriminant < 0) {            return false;        }        // 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;        }        // Otherwise, if neither intesect appear on line segment, shapes do not intersect        return false;    }    // Return true if circle a intersects this circle    bool intersect(Circle a) {        double distance = a.centre.distance(centre);        if (distance <= a.radius + radius) {              return true;            }        return false;    }    // Catch-all intersect function in case intersect is called on a higher shape    template <typename Type>    bool intersect(Type a) {        return a.intersect(*this);    }};// Rectangle class, defined by lower left and upper right pointsclass Rectangle {    public:        Point lowerLeft, upperRight;    private:        Point upperLeft, lowerRight;        Line topLine, bottomLine, leftLine, rightLine;    public:        // Initialise object with corner points and edge lines        Rectangle(Point lowLeft, Point upRight)            : lowerLeft(lowLeft)            , upperRight(upRight)            , upperLeft(Point(lowLeft.x, upRight.y))            , lowerRight(Point(upRight.x, lowLeft.y))            , topLine(upperLeft, upperRight)            , bottomLine(lowerLeft, lowerRight)            , leftLine(lowerLeft, upperLeft)            , rightLine(lowerRight, upperRight)        { }        // Return true if point a is on or in this rectangle        bool pointOn(Point a) {            if (a.x < lowerLeft.x || a.x > upperRight.x) {                return false;            } else if (a.y < lowerLeft.y || a.y > upperRight.y) {                return false;            }            return true;        }        // Return true if line a is inside this rectangle        bool isInside(Line a) {            if (pointOn(a.start)) {                return true;            } else if (pointOn(a.end)) {                return true;            }            return false;        }        // Return true if circle a is inside this rectangle        bool isInside(Circle a) {            return pointOn(a.centre);        }        // Return true if any corners of rectangle a are inside this rectangle        bool isInside(Rectangle a) {            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;        }        // Return true if shape a intersects with this rectangle        template <typename Type>        bool intersect(Type a) {            // Determine if shape a is inside this rectangle            if (isInside(a))                return true;            // If not, do any of the rectangle's lines intersect shape a?            if (a.intersect(topLine))       return true;            if (a.intersect(bottomLine))    return true;            if (a.intersect(leftLine))      return true;            if (a.intersect(rightLine))     return true;            // None do, therefore no intersection            return false;        }};// Function to determine intercept - call intercept method of object a on object b// If object a is of lesser rank than b, object a will call intercept method of btemplate <typename Type1, typename Type2>bool intersect(Type1 &&a, Type2 &&b) {    return a.intersect(b);}Circle c1(Point(1,0),2);Circle c2(Point(3,0),2);Circle c3(Point(0,10),2);Line l1(Point(3,0),Point(10,7));Line l2(Point(3,7),Point(10,5));Line l3(Point(-100,-50),Point(-100,-40));Rectangle r1(Point(4,-2),Point(6,2));Rectangle r2(Point(5.5,1),Point(7.5,3));Rectangle r3(Point(100,90),Point(110,100));template <typename Type>void printLine(const char* label, Type a) {    cout << label;     cout << intersect(a,c1) << ,   << intersect(a,c2) << ,   << intersect(a,c3) << ,  ;    cout << intersect(a,l1) << ,   << intersect(a,l2) << ,   << intersect(a,l3) << ,  ;    cout << intersect(a,r1) << ,   << intersect(a,r2) << ,   << intersect(a,r3) << endl; }int main(){   cout <<     C1, C2, C3, L1, L2, L3, R1, R2, R3 << endl;    printLine(C1:  , c1);   printLine(C2:  , c2);   printLine(C3:  , c3);   printLine(L1:  , l1);   printLine(L2:  , l2);   printLine(L3:  , l3);   printLine(R1:  , r1);   printLine(R2:  , r2);   printLine(R3:  , r3);   Line l(Point(1,1),Point(3,3));   Point p(2,2);   cout << l.onLine(p);   intersect(Line({2,1},{3,4}),Circle({0,0},0));   return 0;}
C++ 2D shape intersections - template reduction
c++;c++11;interview questions;template
The intersect functionFirst 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 zeroYour 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 linesif (start.x == end.x) {    return a.x == start.x;}The std::hypot functionInstead 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 distancesIn 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 evaluationCompute 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 rootsdouble 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 circleif (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 enumsFor 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 tidbitsSyntax, 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 to Apple's goto fail; bug which is probably something you don't want.