Home Bookmarks Papers Blog

Rectangle Cover Problem

Applet By : Kheifets Irit

The problem is to determine whether input rectangles cover a given rectangle or not.

The algorithm in general:
1. user inserts rectangles
2. creation of elementary intervals on basis of input rectangles
3. creation of segment tree
4. creation of events list in order to perform swiping
5. scanning the events list by getting intervals in/out of segment tree according to events list content
6. segment's tree root count is checked after each finished event and according to it's value the algorithm determines whether
    the  rectangle is covered or  not.
 How to use the applet:
 - in order to insert input you should push "insert input" button and then draw rectangles in the left side of applet's window
 - when you finish inserting input you should push "stop" button
 - if you decide during the insertion of input that you would like to restart inserting input you should push "restart" button
   and in order to start inserting input again you should push "insert input" button
 - after pushing "stop" button you have to choose between "run"  button and "step" button
    -"run" button will run the algorithm on the input until it reaches a decision withought possibility of  interference by the user
      after the desition is reached you can see the content of segment tree at each node
      you can see the content of  a node in segment tree by pushing on an appropriate button in the tree
    -"step" button allows you to run the algorithm step by step so that you may check the contents of  the segment tree at each
     stage by pushing the appropriate buttons in the tree
   -if the decision of the algorithm is that the rectangle is covered then you will see a "happy face" otherwise a "sad face"
   -in order to come back to menu you should push the restart button
Note: the input rectangles are opened at right side.
The Applet

 The source of the program

 The algorithm is based on it's description in the book :
Franco P. Preparata, Michael Ian Shamos , "Computational geometry" (Second printing), Springer-Verlag, 1985.