JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Union of Rectangle | Reply
Firstly, Thanks for the nice article.

In the article:

>>In fact the inner line sweep can be replaced by some clever binary >>tree manipulation to reduce the overall time to O(N log N),

I want to know the NlogN implementation. Can anyway please refer me to any book or any site or can any one give any sample code or describe me how to do it?
Re: Union of Rectangle (response to post by dragoon) | Reply
There is an old but very good book:
Preparata, Shamos "Computational Geometry An Introduction".
Re: Union of Rectangle (response to post by dragoon) | Reply
I'm trying to implement this using a segment tree. My insert operation looks like this:

int T[4*100001],total_y = 0;
 
void insert(int node, int a, int b, int y1, int y2, bool found){
    if(!(b<y1 || a>y2)){
        if(a>=y1 && b<=y2){
            ++T[node];
            if(!found) total_y += b-a;
        }else{
            insert(2*node+1,a,(a+b)>>1,y1,y2,found || (T[node]>0));
            insert(2*node+2,((a+b)>>1)+1,b,y1,y2,found || (T[node]>0));
        }
    }
}


However I have no idea about how to implete the delete operation efficiently, any idea?
RSS