Logo Search packages:      
Sourcecode: inkscape version File versions

std::vector< std::vector< unsigned > > Geom::sweep_bounds ( std::vector< Rect >  rs,
Dim2  d 
)

Make a list of pairs of self intersections in a list of Rects.

Parameters:
rs,: vector of Rect.
d,: dimension to sweep along
[(A = rs[i], B = rs[j]) for i,J in enumerate(pairs) for j in J] then A.left <= B.left

Definition at line 17 of file sweep.cpp.

                                                                         {
    std::vector<Event> events; events.reserve(rs.size()*2);
    std::vector<std::vector<unsigned> > pairs(rs.size());

    for(unsigned i = 0; i < rs.size(); i++) {
        events.push_back(Event(rs[i][d][0], i, false));
        events.push_back(Event(rs[i][d][1], i, true));
    }
    std::sort(events.begin(), events.end());

    std::vector<unsigned> open;
    for(unsigned i = 0; i < events.size(); i++) {
        unsigned ix = events[i].ix;
        if(events[i].closing) {
            std::vector<unsigned>::iterator iter = std::find(open.begin(), open.end(), ix);
            //if(iter != open.end())
            open.erase(iter);
        } else {
            for(unsigned j = 0; j < open.size(); j++) {
                unsigned jx = open[j];
                if(rs[jx][1-d].intersects(rs[ix][1-d])) {
                    pairs[jx].push_back(ix);
                }
            }
            open.push_back(ix);
        }
    }
    return pairs;
}


Generated by  Doxygen 1.6.0   Back to index