c++ - 矩形交点(垂直线)

Question

对于给定的矩形 R1 我试图找出哪些是可以与其相交的其他矩形 IF 我画了一个 vector 线段。

与 R1 相交的矩形标记为红色。

每个矩形都由其(top, left) 和(bottom, right) 坐标表征。

R1 = [top, left, bottom, right],...,Rn = [top, left, bottom, right]

通过使用坐标和垂直线。我想找到与 R1 相交的矩形

解决方案

我发现以下库与 icl boost 库的工作相同，但必须更简单:下载地址:[ 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;
}

---

例子

• 左 = 4;
• 右 = 10;
• 结构{1,2,"rc1"};

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

Answer 1

您不关心矩形的垂直位置。您可以将所有内容投影到 x 轴上，然后解决相应的一维问题:您有一组间隔，并且您想知道哪些与给定间隔重叠。这正是区间树的作用:

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