7
\$\begingroup\$

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 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() {
            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 radius
class 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 points
class 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 b
template <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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I think there are better ways to detect intersections. See the book Computational Geometry in C for inspiration and details. I have nothing to do with the author or publisher, but I'm a fan of the book. \$\endgroup\$ – Edward Jul 9 '15 at 14:56
4
\$\begingroup\$

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 to Apple's goto fail; bug which is probably something you don't want.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks @Morwenn, your response is very comprehensive! I'll give some thought to freeing up the intersect function - not quite sure how to represent the objects yet. Perhaps as a combination of line/curves equations? \$\endgroup\$ – Wheeldog Jul 13 '15 at 1:17
4
\$\begingroup\$

Morwenn has already done an excellent review. I will just add one example on how to handle the many combinations of order of arguments for the intersection of the shapes.

A call to intersect(circle, line) should have the same result as a call to intersect(line, circle). But that means you'd have to implement quite a few intersect signatures.

Luckily there is a function overload resolution rule that essentially says that a non-template overload will be preferred to a template overload. Which means that if you define intersect for one combination of shapes, you can have a template overload which will just swap the arguments.

Attempting to call the intersect() template overload for two types for which a non-template overload isn't defined will result in a infinite recursion in runtime. This isn't really desirable so one can use SFINAE or some other technique to create a compile time error should the template overload intersect be used with types for which a non-template overload doesn't exist.

In the example code below I choose to use a simple dummy argument that is always false (note false is slightly better than true here because zero is the easiest value to generate and compare against for many CPUs, but it's a matter of a few instructions at most). This technique has a slight runtime cost: Passing one extra argument, which if the compiler inlines the code might be removed; But it is the easiest to understand. With a little work you can make a zero-overhead compile time check (left as an exercise for the reader).

Example code:

#include <iostream>

struct A{
    int i = 0;
};

struct B{
    int j = 1;
};

struct C{
    double j = 0.0;
};

bool intersect(const A& a, const B& b, bool=false){
    std::cout<<"Non template called!"<<std::endl;
    return a.i == b.j;
}

template<typename T1, typename T2>
bool intersect(const T1& a, const T2& b){
    std::cout<<"Template overlord called!"<<std::endl;
    return intersect(b, a, false);
}

int main() {
    A a;
    B b;
    C c;
    
    std::cout<<intersect(a,b)<<std::endl;
    std::cout<<intersect(b,a)<<std::endl;
    //intersect(c,a); // Compile error
    
    return 0;
}

Output:

Non template called! 
0
Template overlord called!
Non template called!
0
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ That's pretty clever. I like that solution :) \$\endgroup\$ – Morwenn Jul 8 '15 at 13:48
  • \$\begingroup\$ Thanks Emily! I'll try to work that in with Morwenn's suggestions \$\endgroup\$ – Wheeldog Jul 13 '15 at 2:16
  • \$\begingroup\$ What if you want to make those classes polymorphic. All the class inherit from common base class. \$\endgroup\$ – solti Feb 5 '19 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.