c++ - Rectangles Intersection (Vertical line) -

for given rectangle r1 trying find out other rectangles intersect if draw vectical line segment.

the rectangles intersect r1 marked in red.

every rectangle characterized (top, left) , (bottom, right) coordinates.

r1 = [top, left, bottom, right],...,rn = [top, left, bottom, right] 

by using coordinates , vertical line. want find rectangles intersects r1

solution

i found following library same work icl boost library must simpler: download site: [https://github.com/ekg/intervaltree][2]

#include <iostream> #include <fstream> #include "intervaltree.h"  using namespace std;  struct position {     int x;     int y;     string id; };  int main() {     vector<interval<position>> intervals;     intervals.push_back(interval<position>(4,10,{1,2,"r1"}));     intervals.push_back(interval<position>(6,10,{-6,-3,"r2"}));     intervals.push_back(interval<position>(8,10,{5,6,"r3"}));      vector<interval<position> > results;     vector<string> value;     int start = 4;     int stop = 10;      intervaltree<position> tree(intervals);    // tree.findcontained(start, stop, results);     tree.findoverlapping(start, stop, results);     cout << "found " << results.size() << " overlapping intervals" << endl; } 

---

example

• left = 4;
• right = 10;
• structure {1,2,"rc1"};

intervals.push_back(interval(4,10,{1,2,"r1"}));

you don't care rectangles vertically. can project onto x-axis , solve corresponding 1-dimensional problem: have set of intervals , want know overlap given interval. interval tree does:

https://en.wikipedia.org/wiki/interval_tree