vendredi 31 juillet 2020

Reduce time taken in Line Sweep for vertical and horizontal line segments

I have used std::set to implement line sweep algorithm for vertical and horizontal lines. But the final range search on the lower bound and uppper bound of 'status' set takes a lot of time. Is there some way to avoid this? I chose std::set because it is based on balanced BST and insertion, deletion and search take logn time. Is there a better data structure to implement this?


// before this I initialize the events set with segments with increasing x co-ordinates. The segment struct has 2 points variable and 1 type variable for identifying vertical segment(1), horizontal segment starting(0) and ending(2).

for(auto iter = events.begin(); iter != events.end(); iter++)
    {
        segment temp = *iter;

        if(temp.type == 0)
            status.insert(temp.p1);
        else if(temp.type == 2)
            status.erase(temp.p2);
        else
        {    
            auto lower = status.lower_bound(std::make_pair(temp.p1.x, temp.p1.y));
            auto upper = status.upper_bound(std::make_pair(temp.p2.x, temp.p2.y));
            
            // Can the no of elements in the interval be found without this for loop
            for(;lower != upper; lower++)
            {
                count++;
            }
        }
    }

Aucun commentaire:

Enregistrer un commentaire