Rectangle intersections


/ Published in: C++
Save to your folder(s)

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.


Copy this code and paste it in your HTML
  1. //***************************************************//
  2. Beginning of Rects.hpp file
  3. //***************************************************//
  4. #ifndef HAWKEYERECTANGLES_RECT_H_
  5. #define HAWKEYERECTANGLES_RECT_H_
  6.  
  7. #include <limits.h>
  8. struct Point
  9. {
  10. Point() : x(INT_MIN), y(INT_MIN) { }
  11. Point(int x, int y) : x(x), y(y) { }
  12.  
  13. int x;
  14. int y;
  15. };
  16.  
  17. //a Rect object is considered to be drawn from the top left corner to the bottom right corner
  18. class Rect
  19. {
  20. public:
  21. Rect() { }
  22. Rect(const Point& c1, const Point& c2, const Point& c3, const Point& c4);
  23.  
  24. bool isValid() const;
  25. bool contains(const Point& point) const;
  26. bool intersects(const Rect& other) const;
  27.  
  28. Point tl;
  29. Point tr;
  30. Point br;
  31. Point bl;
  32.  
  33. private:
  34. unsigned int countContainedCorners(const Rect& rect, bool& cornerTouchingSide) const;
  35. };
  36.  
  37. #endif
  38.  
  39. //***************************************************//
  40. End of Rects.hpp file
  41. //***************************************************//
  42.  
  43. //***************************************************//
  44. Beginning of Rects.cpp file
  45. //***************************************************//
  46. #include "Rect.hpp"
  47. #include <iostream>
  48. #include <sstream>
  49. #include <fstream>
  50. #include <vector>
  51.  
  52. Rect::Rect(const Point& c1, const Point& c2, const Point& c3, const Point& c4)
  53. {
  54. std::vector<Point> corners;
  55. corners.push_back(c1);
  56. corners.push_back(c2);
  57. corners.push_back(c3);
  58. corners.push_back(c4);
  59. //set top left and bottom right corners
  60. tl = c1;
  61. br = c1;
  62. for (unsigned int i = 1; i < corners.size(); ++i)
  63. {
  64. if (corners[i].x < tl.x || corners[i].y < tl.y)
  65. tl = corners[i];
  66.  
  67. if (corners[i].x > br.x || corners[i].y > br.y)
  68. br = corners[i];
  69. }
  70. //now set top right and bottom left corners
  71. tr = c1;
  72. bl = c1;
  73. for (unsigned int i = 1; i < corners.size(); ++i)
  74. {
  75. if (corners[i].x == tl.x && corners[i].y == br.y)
  76. bl = corners[i];
  77.  
  78. if (corners[i].x == br.x && corners[i].y == tl.y)
  79. tr = corners[i];
  80. }
  81. }
  82.  
  83. bool Rect::isValid() const
  84. {
  85. //checks that all four points are where they should be in respect to each other
  86. 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;
  87. }
  88.  
  89. bool Rect::contains(const Point& point) const
  90. {
  91. //checks whether the point in question is within all four sides of the given rectangle
  92. //NOTE: a corner that is touching a side of the rectangle counts as being inside the rectangle
  93. return point.x >= tl.x && point.x <= br.x && point.y >= tl.y && point.y <= br.y;
  94. }
  95.  
  96. bool Rect::intersects(const Rect& other) const
  97. {
  98. bool cornerTouchingSide = false;
  99. unsigned int numberOfCornersInRect = countContainedCorners(other, cornerTouchingSide);
  100.  
  101. if (0 == numberOfCornersInRect)
  102. return false;
  103.  
  104. // if only 1 or 2 corners of one rect are inside the other, then there's a definite intersection of rectangles
  105. if (numberOfCornersInRect > 0 && numberOfCornersInRect < 3)
  106. return true;
  107.  
  108. //if all four corners of one rect are inside the other, then at least one contains the other
  109. //(or they can both contain each other if they're the same rectangle)
  110. //NOTE: 3 corners of one rectangle being inside the other => all 4 corners are inside, given the nature of rectangles
  111. //in this case, we need to use the check above if one corner of one rectangle touches a side of the other rectangle
  112. return cornerTouchingSide;
  113. }
  114.  
  115. unsigned int Rect::countContainedCorners(const Rect& rect, bool& cornerTouchingSide) const
  116. {
  117. std::vector<Point> corners;
  118. corners.push_back(rect.tl);
  119. corners.push_back(rect.tr);
  120. corners.push_back(rect.br);
  121. corners.push_back(rect.bl);
  122.  
  123. unsigned int numberOfCornersInRect = 0;
  124. for (unsigned int i = 0; i < corners.size(); ++i)
  125. {
  126. if (contains(corners[i]))
  127. ++numberOfCornersInRect;
  128.  
  129. //check whether this corner has common x or y coordinate with any corner of this rectangle
  130. //this will mean that at least one corner of one rectangle will be touching a side of the other rectangle
  131. //this check will be needed later in the case that one rect is contained inside the other
  132. if (!cornerTouchingSide)
  133. cornerTouchingSide = corners[i].x == tl.x || corners[i].x == br.x || corners[i].y == tl.y || corners[i].y == br.y;
  134. }
  135.  
  136. if (numberOfCornersInRect != 0)
  137. return numberOfCornersInRect;
  138.  
  139. //search for corners of this rectangle contained within the other rectangle
  140. //NOTE: no need to set cornerTouchingSide boolean again
  141. corners.clear();
  142. corners.push_back(tl);
  143. corners.push_back(tr);
  144. corners.push_back(br);
  145. corners.push_back(bl);
  146. for (unsigned int i = 0; i < corners.size(); ++i)
  147. {
  148. if (rect.contains(corners[i]))
  149. ++numberOfCornersInRect;
  150. }
  151.  
  152. return numberOfCornersInRect;
  153. }
  154. //***************************************************//
  155. End of Rects.cpp file
  156. //***************************************************//
  157.  
  158. //***************************************************//
  159. Beginning of RectIntersections.hpp file
  160. //***************************************************//
  161. #ifndef HAWKEYERECTANGLES_RECTINTERSECTIONS_H_
  162. #define HAWKEYERECTANGLES_RECTINTERSECTIONS_H_
  163.  
  164. #include "Rect.hpp"
  165. #include <string>
  166. #include <vector>
  167. #include <fstream>
  168.  
  169. class RectIntersections
  170. {
  171. public:
  172. RectIntersections(const std::string& rectsFilePath, const std::string& logFilePath = std::string())
  173. : m_rectsFilePath(rectsFilePath), m_logFilePath(logFilePath) { }
  174. bool doAnyTwoRectsIntersect();
  175.  
  176. private:
  177. bool extractRectsFromFile(std::vector<Rect>& rects, std::ofstream* log = NULL);
  178.  
  179. std::string m_rectsFilePath;
  180. std::string m_logFilePath;
  181. };
  182.  
  183. #endif
  184. //***************************************************//
  185. End of RectIntersections.hpp file
  186. //***************************************************//
  187.  
  188. //***************************************************//
  189. Beginning of RectIntersections.cpp file
  190. //***************************************************//
  191. #include "RectIntersections.hpp"
  192. #include <sstream>
  193. #include <algorithm>
  194.  
  195. bool RectIntersections::extractRectsFromFile(std::vector<Rect>& rects, std::ofstream* log /*= NULL*/)
  196. {
  197. std::ifstream ifs(m_rectsFilePath);
  198. if (!ifs.good())
  199. {
  200. if (log)
  201. *log << "ERROR: The file specified could not be opened for reading or is invalid.";
  202.  
  203. return false;
  204. }
  205.  
  206. std::string line;
  207. while (std::getline(ifs, line))
  208. {
  209. std::istringstream isstream(line);
  210. Point c1, c2, c3, c4;
  211.  
  212. isstream >> c1.x >> c1.y >> c2.x >> c2.y >> c3.x >> c3.y >> c4.x >> c4.y;
  213.  
  214. Rect rect(c1, c2, c3, c4);
  215. if (!rect.isValid())
  216. {
  217. //user should be notified in the log file if one of the lines in the txt file has resulted in an ill defined rectangle
  218. if (log)
  219. *log << "ERROR: The rectangle defined by: '" << line << "' is invalid." << std::endl;
  220.  
  221. continue;
  222. }
  223.  
  224. rects.push_back(rect);
  225. }
  226.  
  227. if (rects.empty())
  228. {
  229. //user should be notified if there were no rectangles defined in the file input,
  230. //either because it contained none, and was all writing
  231. //or perhaps because of too few coordinates to define a rectangle
  232. if (log)
  233. *log << "ERROR: There were no well-defined rectangles defined in the file specified." << std::endl;
  234.  
  235. return false;
  236. }
  237.  
  238. //if only one rectangle found in file, return false because there is no second rectangle to compare against
  239. //should not to return true on the basis that the one rect intersects with itself
  240. if (1 == rects.size())
  241. {
  242. if (log)
  243. *log << "ERROR: Only one well defined rectangle in the file specified was found." << std::endl;
  244.  
  245. return false;
  246. }
  247.  
  248. return true;
  249. }
  250.  
  251. bool RectIntersections::doAnyTwoRectsIntersect()
  252. {
  253. std::vector<Rect> rects;
  254. bool extraction;
  255.  
  256. if (!m_logFilePath.empty())
  257. {
  258. std::ofstream log(m_logFilePath, std::ios_base::app);
  259. extraction = extractRectsFromFile(rects, &log);
  260. }
  261. else
  262. {
  263. extraction = extractRectsFromFile(rects);
  264. }
  265.  
  266. if (!extraction)
  267. return false;
  268.  
  269. //now go through each rectangle read in from the file and determine whether any two of them intersect
  270. for (unsigned int i = 0; i < rects.size(); ++i)
  271. {
  272. for (unsigned int j = i + 1; j < rects.size(); ++j)
  273. {
  274. if (rects[i].intersects(rects[j]))
  275. return true;
  276. }
  277. }
  278.  
  279. return false;
  280. }
  281. //***************************************************//
  282. End of RectIntersections.cpp file
  283. //***************************************************//

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.