This applet will make a Trapezoidal map from the line segments that are on the
plane and also finds the trapezoid where inserted query point is in. It also
shows that (because this is a incremental algorithm) it is possible to do
queries while you are inserting points!
- Insert line segments by
clicking left mouse button. You can choose already added vertex as a start
point or as an end point by clicking it. Your line segments can’t
- Select the input order of the
segments by checking “Rand. Order”- check box to
use random order insertion and use “Fast”- check box to insert the points in fast speed.
Use "Insert manually"- check box to manually insert one segment at time.
- Press “Build Map”- button.
If you haven't selected the "manual mode" algorithm will proceed
automatically to the end. If you are in manual mode you have to press "Next
Step"- button to insert next segment. Between insertions, you can change
the insertion speed. You can also do queries while inserting segments in
manual mode (look at instructions 4 and 5).
- Press “Query Point”- button
and select the point what you want to locate. Use “Show the path”- check
box to select whether or not you would like to print the route of the
- Press “Find”- button to find
the point. The result is show in the text field showing the name of the
found trapezoid and its upper left, lower left, lower right and upper
black: last inserted segment (when inserting segments)
or already deled segments
green: presents either already
inserted segments (when inserting segments) or segments that are not yet
inserted (while building)
red: the next segments that will
cyan: the segments that is
inserted at that time or was inserted
the trapezoids areas that are intersected by the inserted segment (while
Here is the