The Applet

Your Browser doesn't support applets!

 

Instructions:

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!

  1. 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 intersect.
  2. 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.
  3. 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).
  4. 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 search.
  5. 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 right neighbors.

Colors:
    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 be inserted
    cyan: the segments that is inserted at that time or was inserted
    yellow: shows the trapezoids areas that are intersected by the inserted segment (while inserting segments).

 

Here is the source code !