## Posted By

omarelsaid on 05/11/14

# Rectangle intersections

/ Published in: C++

This set of files is meant to read in a text file containing 2D coordinates of rectangles on each line, and determine whether any two of them intersect or not.

`//***************************************************//Beginning of Rects.hpp file//***************************************************//#ifndef HAWKEYERECTANGLES_RECT_H_#define HAWKEYERECTANGLES_RECT_H_ #include <limits.h>struct Point{    Point() : x(INT_MIN), y(INT_MIN) { }    Point(int x, int y) : x(x), y(y) { }     int x;    int y;}; //a Rect object is considered to be drawn from the top left corner to the bottom right cornerclass Rect{public:    Rect() { }    Rect(const Point& c1, const Point& c2, const Point& c3, const Point& c4);     bool isValid() const;    bool contains(const Point& point) const;    bool intersects(const Rect& other) const;     Point tl;    Point tr;    Point br;    Point bl; private:    unsigned int countContainedCorners(const Rect& rect, bool& cornerTouchingSide) const;}; #endif //***************************************************//End of Rects.hpp file//***************************************************// //***************************************************//Beginning of Rects.cpp file//***************************************************//#include "Rect.hpp"#include <iostream>#include <sstream>#include <fstream>#include <vector> Rect::Rect(const Point& c1, const Point& c2, const Point& c3, const Point& c4){    std::vector<Point> corners;    corners.push_back(c1);    corners.push_back(c2);    corners.push_back(c3);    corners.push_back(c4);    //set top left and bottom right corners    tl = c1;    br = c1;    for (unsigned int i = 1; i < corners.size(); ++i)    {        if (corners[i].x < tl.x || corners[i].y < tl.y)            tl = corners[i];         if (corners[i].x > br.x || corners[i].y > br.y)            br = corners[i];    }    //now set top right and bottom left corners    tr = c1;    bl = c1;    for (unsigned int i = 1; i < corners.size(); ++i)    {        if (corners[i].x == tl.x && corners[i].y == br.y)            bl = corners[i];         if (corners[i].x == br.x && corners[i].y == tl.y)            tr = corners[i];    }} bool Rect::isValid() const{    //checks that all four points are where they should be in respect to each other    return tl.x == bl.x && tl.y == tr.y && tl.x < tr.x && tl.y < bl.y && br.x == tr.x && br.y == bl.y;} bool Rect::contains(const Point& point) const{    //checks whether the point in question is within all four sides of the given rectangle    //NOTE: a corner that is touching a side of the rectangle counts as being inside the rectangle    return point.x >= tl.x && point.x <= br.x && point.y >= tl.y && point.y <= br.y;} bool Rect::intersects(const Rect& other) const{    bool cornerTouchingSide = false;    unsigned int numberOfCornersInRect = countContainedCorners(other, cornerTouchingSide);     if (0 == numberOfCornersInRect)        return false;     // if only 1 or 2 corners of one rect are inside the other, then there's a definite intersection of rectangles    if (numberOfCornersInRect > 0 && numberOfCornersInRect < 3)        return true;     //if all four corners of one rect are inside the other, then at least one contains the other    //(or they can both contain each other if they're the same rectangle)    //NOTE: 3 corners of one rectangle being inside the other => all 4 corners are inside, given the nature of rectangles    //in this case, we need to use the check above if one corner of one rectangle touches a side of the other rectangle    return cornerTouchingSide;} unsigned int Rect::countContainedCorners(const Rect& rect, bool& cornerTouchingSide) const{    std::vector<Point> corners;    corners.push_back(rect.tl);    corners.push_back(rect.tr);    corners.push_back(rect.br);    corners.push_back(rect.bl);     unsigned int numberOfCornersInRect = 0;    for (unsigned int i = 0; i < corners.size(); ++i)    {        if (contains(corners[i]))            ++numberOfCornersInRect;         //check whether this corner has common x or y coordinate with any corner of this rectangle        //this will mean that at least one corner of one rectangle will be touching a side of the other rectangle        //this check will be needed later in the case that one rect is contained inside the other        if (!cornerTouchingSide)            cornerTouchingSide = corners[i].x == tl.x || corners[i].x == br.x || corners[i].y == tl.y || corners[i].y == br.y;    }     if (numberOfCornersInRect != 0)        return numberOfCornersInRect;     //search for corners of this rectangle contained within the other rectangle    //NOTE: no need to set cornerTouchingSide boolean again     corners.clear();    corners.push_back(tl);    corners.push_back(tr);    corners.push_back(br);    corners.push_back(bl);    for (unsigned int i = 0; i < corners.size(); ++i)    {        if (rect.contains(corners[i]))            ++numberOfCornersInRect;    }     return numberOfCornersInRect;}//***************************************************//End of Rects.cpp file//***************************************************// //***************************************************//Beginning of RectIntersections.hpp file//***************************************************//#ifndef HAWKEYERECTANGLES_RECTINTERSECTIONS_H_#define HAWKEYERECTANGLES_RECTINTERSECTIONS_H_ #include "Rect.hpp"#include <string>#include <vector>#include <fstream> class RectIntersections{public:    RectIntersections(const std::string& rectsFilePath, const std::string& logFilePath = std::string())        : m_rectsFilePath(rectsFilePath), m_logFilePath(logFilePath) {  }    bool doAnyTwoRectsIntersect(); private:    bool extractRectsFromFile(std::vector<Rect>& rects, std::ofstream* log = NULL);     std::string m_rectsFilePath;    std::string m_logFilePath;}; #endif//***************************************************//End of RectIntersections.hpp file//***************************************************// //***************************************************//Beginning of RectIntersections.cpp file//***************************************************//#include "RectIntersections.hpp"#include <sstream>#include <algorithm> bool RectIntersections::extractRectsFromFile(std::vector<Rect>& rects, std::ofstream* log /*= NULL*/){    std::ifstream ifs(m_rectsFilePath);    if (!ifs.good())    {        if (log)            *log << "ERROR: The file specified could not be opened for reading or is invalid.";         return false;    }     std::string line;    while (std::getline(ifs, line))    {        std::istringstream isstream(line);        Point c1, c2, c3, c4;         isstream >> c1.x >> c1.y >> c2.x >> c2.y >> c3.x >> c3.y >> c4.x >> c4.y;         Rect rect(c1, c2, c3, c4);        if (!rect.isValid())        {            //user should be notified in the log file if one of the lines in the txt file has resulted in an ill defined rectangle            if (log)                *log << "ERROR: The rectangle defined by: '" << line << "' is invalid." << std::endl;             continue;        }         rects.push_back(rect);    }     if (rects.empty())    {        //user should be notified if there were no rectangles defined in the file input,        //either because it contained none, and was all writing        //or perhaps because of too few coordinates to define a rectangle        if (log)            *log << "ERROR: There were no well-defined rectangles defined in the file specified." << std::endl;         return false;    }     //if only one rectangle found in file, return false because there is no second rectangle to compare against    //should not to return true on the basis that the one rect intersects with itself    if (1 == rects.size())    {        if (log)            *log << "ERROR: Only one well defined rectangle in the file specified was found." << std::endl;         return false;    }     return true;} bool RectIntersections::doAnyTwoRectsIntersect(){    std::vector<Rect> rects;    bool extraction;     if (!m_logFilePath.empty())    {        std::ofstream log(m_logFilePath, std::ios_base::app);        extraction = extractRectsFromFile(rects, &log);    }    else    {        extraction = extractRectsFromFile(rects);    }     if (!extraction)        return false;     //now go through each rectangle read in from the file and determine whether any two of them intersect    for (unsigned int i = 0; i < rects.size(); ++i)    {        for (unsigned int j = i + 1; j < rects.size(); ++j)        {            if (rects[i].intersects(rects[j]))                return true;        }    }     return false;}//***************************************************//End of RectIntersections.cpp file//***************************************************//`