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 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.