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