//***************************************************//
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 corner
class 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
//***************************************************//

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.

Rectangle intersections

C++