| Home | Bookmarks | Papers | Blog |
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 algorithm is based on it's description
in the book :
Franco P. Preparata, Michael Ian Shamos ,
"Computational geometry" (Second printing), Springer-Verlag, 1985.