How to group sub-vector by intersect or not in C++

Question

I have a 2d vector

vector<vector<double>> vec = { { 1, 0.5 },{ 2, 0.5 },{ 2.25, 0.5 },{ 2.6, 0.3 },
{3.3, 0.5 },{ 3, 0.5 },{ 3.1, 0.5 },{ 4, 0.6 } };

The first element is the start about a line. The second element is the length about the line. I can show it as follow graph

Now I want to get the group of the line index as they intersect or not. I mean I hope the result is

{{1},{2,3,4},{5,6,7},{8}}

If I'm in Wolfram Mathematic, I can use follow code

list = {{1, 0.5}, {2, 0.5}, {2.25, 0.5}, {2.6, 0.3}, {3.3, 0.5}, {3, 
    0.5}, {3.1, 0.5}, {4, 0.6}};
g = RelationGraph[#[[2]] < #2[[2]] < #[[2]] + #[[3]] || #[[2]] < 
#2[[2]] + #2[[3]] < #[[2]] + #[[3]] &, 
  MapIndexed[Prepend[#, First[#2]] &, list]]
Map[First] /@ ConnectedComponents[g]

But how to implement this in C++?

Use [Disjoint-set](https://en.wikipedia.org/wiki/Disjoint-set_data_structure). (and record interval). Use [find-all-overlapping-intervals](https://stackoverflow.com/questions/4542892/possible-interview-question-how-to-find-all-overlapping-intervals) to know which interval to join. — Jarod42, Mar 29 '18 at 14:50

score 1 · Accepted Answer · answered Mar 29 '18 at 19:44

In this problem, what you basically need to do is group all the intervals together, that overlap or intersect directly or indirectly.

Let's assume that we converted (start, len) pairs to (start, end) pairs. So, now we have a list of (start, end). If we sort this list by start time and iterate over it. Then:

if : means that the ith range is disjoint from any range uptil i-1. So, add it to a new group.
if : means that the ith range is overlapping/intersecting with some of the range(s) in 1..i-1.

Note: is the max value of end time from 1 to i-1.

I've added rest of the explanation in the form of comments, in the code itself.

Code:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

//a struct representing a range
struct range {
    double st, ed;
};

//just a shorthand :p
using prp = pair<range, int>;


/*
* Comparator that sorts by the start time of range.
* If start times are equal, then end time is used to sort.
*/
inline bool sort_by_start(const prp &a, const prp &b) {
    if (a.first.st == b.first.st) return a.first.ed  < b.first.ed;
    return a.first.st < b.first.st;
}

int main() {

    //your vector
    const vector<vector<double>> v2d = { { 1, 0.5 }, { 2, 0.5 }, { 2.25, 0.5 }, { 2.6, 0.3 },
        {3.3, 0.5 }, { 3, 0.5 }, { 3.1, 0.5 }, { 4, 0.6 }
    };

    //a vector of ranges
    //each element is pair of (range, position) where position is the
    //original index of range in v2d
    vector<prp> rng(v2d.size());

    //a vector of vector of ints that will hold the groups
    vector<vector<int>> idx;

    int i, j;
    //building ranges. end time = start time + length
    //position is stored, so that it can be used later.
    for (i = 0; i < (int) v2d.size(); ++i) {
        rng[i] = {{v2d[i][0], v2d[i][1] + v2d[i][0]}, i};
    }

    //sorting by start time
    sort(rng.begin(), rng.end(), sort_by_start);

    //starting of first group
    idx.push_back(vector<int>());
    idx.back().push_back(rng[0].second);
    double edv = rng[0].first.ed;

    for (i = 1; i < (int)rng.size(); ++i) {

        //if next start time is greater than the largest
        //end time encountered so far (maintained using edv)
        //it means the next group is starting, so push an empty vector
        if (edv < rng[i].first.st)
            idx.push_back(vector<int>());

        //edv maintains the largest end time encountered so far.
        edv = max(edv, rng[i].first.ed);
        //we want to push the current range into the last active group.
        //why last? because they are all sorted by start-time.
        idx.back().push_back(rng[i].second);
    }


    //displaying
    for (i = 0; i < (int)idx.size(); ++i) {
        for (j = 0 ; j < (int)idx[i].size(); ++j) {
            cout << idx[i][j] + 1 << ' ';
        }
        cout << '\n';
    }
    return 0;
}

Result:

score 0 · Answer 2 · answered Mar 30 '18 at 17:00

Done!

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<vector<int>> group_digit(vector<vector<int>> component)
{
    class interval_intersectionQ
    {
    public:
        bool operator()(vector<vector<int>> sub_group, vector<int> vec)
        {
            vector<int> continuous_line;
            for (vector<int> i : sub_group)
            {
                continuous_line.push_back(i[1]);
                continuous_line.push_back(i[1] + i[2]);
            }
            pair<vector<int>::iterator, vector<int>::iterator> interval = minmax_element(continuous_line.begin(), continuous_line.end());
            if (*interval.first <= vec[1] && vec[1] <= *interval.second || 
                *interval.first <= vec[1] + vec[2] && vec[1] + vec[2] <= *interval.second || 
                vec[1] <= *interval.first && *interval.first <= vec[1] + vec[2] || 
                vec[1] <= *interval.second && *interval.second <= vec[1] + vec[2])
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    };
    vector<vector<int>> origin = component;
    vector<vector<vector<int>>> group;
    while (!origin.empty())
    {
        group.push_back(vector<vector<int>>());
        group[group.size() - 1].push_back(origin[origin.size() - 1]);
        origin.pop_back();
        for (int i = 0; i < origin.size(); i++)
        {
            if (interval_intersectionQ()(group[group.size() - 1], origin[i]))
            {
                group[group.size() - 1].push_back(origin[i]);
                origin.erase(origin.begin() + i);
                i = -1;
            }
        }
    }
    vector<vector<int>> one_digit(group.size());
    for (int i = 0; i<group.size(); i++)
    {
        for (vector<int> j : group[i])
        {
            one_digit[i].push_back(j[0]);
        }
    }
    return one_digit;
}


int main()
{
    vector<vector<int>> origin = { { 1, 10, 5 },{ 2, 20, 5 },{ 3, 22, 5 },
    { 4, 26, 3 },{ 5, 33, 5 },{ 6, 30,5 },{ 7, 31, 5 },{ 8, 40, 6 } };
    vector<vector<int>> one_digit = group_digit(origin);
    for (vector<int> i : one_digit)
    {
        for (int j : i)
        {
            cout << j << "  ";
        }
        cout << endl;
    }
    return 0;
}

How to group sub-vector by intersect or not in C++

2 Answers2

Code:

Result: