矩形相交(垂直线) [英] Rectangles Intersection (Vertical line)

问题描述

对于给定的矩形R1，我试图找出哪些其他矩形可以与其相交. IF 我绘制了一条线段.

For a given rectangle R1 I am trying to find out which are the other rectangles that could intersect with it IF I draw a vectical line segment.

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

The rectangles that intersect with R1 are marked in Red.

每个矩形都有其(top, left)和(bottom, right)坐标.

Every rectangle is characterized by its (top, left) and (bottom, right) coordinates.

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

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

By using the coordinates and the vertical line. I want to find the rectangles that intersects with R1

我找到了以下库，其功能与icl boost库相同，但必须更简单: 下载站点:[ https://github.com/ekg/intervaltree][2]

I found the following library which does the same work as the icl boost library but 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;
}

---

示例

• LEFT = 4;
• RIGHT = 10;
• 结构{1,2，"rc1"};

---

Example

• LEFT = 4;
• RIGHT = 10;
• structure {1,2,"rc1"};

intervals.push_back(Interval(4,1​​0，{1,2，"r1"})));

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

推荐答案

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

You don't care where the rectangles are vertically. You can project everything onto the x-axis and then solve the corresponding 1-dimensional problem: you have a set of intervals and you want to know which overlap with a given interval. This is exactly what an interval tree is does:

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

这篇关于矩形相交(垂直线)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！