wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> rectangle overlapping
        
(Message started by: cuckoo on Aug 7^th, 2007, 5:47am)

Title: rectangle overlapping
Post by cuckoo on Aug 7^th, 2007, 5:47am

I come across the following problem on other bbs, it seems related to some mechanism of windows. I am a bit confused, can somebody give some advice? Thank you!

problem:
Given a diagram which contains rectangles of different sizes that may overlap with each other and rectangles may be hidden. Discuss the data structures to use to support this funcionality: When a rectangle is clicked, it should come into view on top of others, if it is hidden already. The overall aim is to reduce the amount of repainting to be done everytime the user clicks on a rectangle.

Title: Re: rectangle overlapping
Post by sk on Aug 14^th, 2007, 8:22pm

Have a list of windows, with each window having rectangle co-ordinates and another list which will have all the overlapping windows with other windows.

these are better illustrated with the help of code
struct window
{
int left,top,right,bottom;
struct window *IntersectingWindows;
boolean minimized;
}

when u create a window, scroll thru the list to see if there are any overalppings. if so calculate the intersecting rectangles and update both the overlapping windows. this will be done in O(n). so every new window will have O(n) to search thru entire list.

the list is maintained as a queue, ordered by their creation time. If u click on any window, then u search thru the list and make that node as the head of the node and paint only the intersecting rectangles if minimized == false;

this is better than painting the entire window. u can also split the intersecting windows further, if there are multiple intersections, but it will get costly to search through.

the list will ensure that even if u click on a point which is common to multiple rectangles, only the latest window will be displayed.

Title: Re: rectangle overlapping
Post by sumantbhardvaj on Aug 16^th, 2007, 11:20pm

As far as i got from your explanation, you are making a list of windows where each window will have a seperate list of windows overlapping with it. So whenever we make a add a new window we update the both the overlapping windows.

but i could not understand this part ..

Quote:

If u click on any window, then u search thru the list and make that node as the head of the node and paint only the intersecting rectangles if minimized == false;

What is the minimized variable doing there ?? and why to make that node the head ?? plz explain..

Title: Re: rectangle overlapping
Post by gotit on Aug 19^th, 2007, 6:59am

I assume that there is someway to differentiate the rectangles e.g by assigning numbers to them.
Create a hash table in which each entry corresponds to a rectangle and is identified by the rectangle number.An entry corresponding to rect i contains the following information:

i) the color of rectangle i
ii) a list in which each entry contains info about a overlap e.g. if rect j ovelaps rect i, then their will be an entry in the list corresponding to rect j. This info will contain the rect number that overlaps rect i (j in this case)and the portion of rect i that it overlaps.Likewise there will be an entry corresponding to all such overlaps.

When you click on rectangle i, the following steps are taken.

i) Traverse the list corresponding to rectangle i. For an entry corresponding to rectangle j in this list, goto the list for j and insert an entry corresponding to rect i(bcoz now rect j will be covered by rectangle i). Do this for all entries in the list of rect i.

ii) When the list for rect i has been completely traversed,delete the list completely.(An empty list for a rectangle means that it is not overlapped by any other rectangle).

Title: Re: rectangle overlapping
Post by sk on Sep 2^nd, 2007, 3:59pm

minimized..is a flag to check if it minimized. e.g. if the rectangle co-ordinates are 10,10,20,20 and u click on any point within this, then it should be displayed only if the rectangle is not minimized.

Title: Re: rectangle overlapping
Post by sk on Sep 2^nd, 2007, 4:01pm

and u make it the head, because the most recent one is always at the head. that is how u determine, the window focus hierarchy.
given a point, it can belong to any window, but hwich window are u going to highlight. the most recent one.