Search Target In Polygon

Search Target In Polygon

To reopen the STIP windows push:
(If you see no button here, your browser does not completely support JAVA 1.1.
In this case either enable it or try this URL again with the appletviewer from the JDK1.1.x for your Operating System.)

What is STIP ?

STIP is the abbreviation of "Search Target In a Polygon" and is the simulation of a robot who uses his visual system to find an unknown target in an unknown room with a polygonal ground plan and insurmountable walls. STIP allows a broad variety of human interaction, ranging from pure calculation of several values up to competing with the robot in a 3D-environment.

STIP was entirely written in JAVA 1.1 by Nicole Heckenkemper as a "Diplomarbeit" for the "Lehrgebiet Praktische Informatik VI" at the "FernUniversität Hagen" and it's main purposes are the visualisation and teaching of the course "Algorithmische Geometrie" and the realization of an experimental environment for this problem.

STIP has numerous parameters which can be optimized to fit the users needs.

) Please send comments to:

For a short introduction into the theory of this work, click here .

Usage

Since STIP has three major windows with different intentions, here will follow a short description of them. The three windows are:

The Robot Window (which is at the same time the polygon editor)
The Human Window (for individual investigations about search algorithms)
The 3D-Window for the user (a visual help)

You can click here on any of the listed features to jump there directly:

Robot Window

Mouse Usage
Menubar

"File"
"Show"
"User-Mode"
"Options"
"Help"

Statusline
Resultline
Canvas
Buttons

Human Window and 3D Window

Mouse Usage
Navigation
Menubar

"Options"
"Help"

Statusline and Resultline
Canvas
Buttons

Robot Window

Mouse usage

Press left mouse button to select a point or to set a new polygon point.
All points are inserted at the green segment which indicates the aperture of the polygon.
Selecting a point moves the aperture.
Press middle mouse button to set startpoint and targetpoint.
Press right mouse button to remove any point.
Drag mouse with left button pressed to move any point.
Moves aperture.
Drag mouse with middle button pressed to move any point.
Does not move aperture.

Description of the Menubar of the Robot window

File-Menu

Back to the Contents.

Save: Save polygon points, startpoint and targetpoint in a file.
Load: Load polygon points, startpoint and targetpoint from a file.
Close: Close the robot window.
Print Frame: Print the complete window.
Print Canvas: Print the canvas only.

Important hint!

An applet which is loaded over the network cannot ordinarily read or write files on the host that is executing it.
It is also not allowed to initiate a print job.
Depending on the used browser it may be possible to enable these features, which is mostly the case.

Show-Menu

Back to the Contents.

robot: Toggle button to enable or disable wether the robot is shown at runtime, or not.
vis(p) at ... : Let you select when the visibility polygon shall be displayed, if at all.
path at ... : Same as before, but for the path which the robot takes through the polygon.
partial map at ... : Same as before, but for the partial map.
tangent segments: This allows the user to see at runtime how tangent segments are used in STIP.

User Mode-Menu

Back to the Contents.

Strategy: Simulation of the STIP search strategy. The robot searches for the target.
Strategy immediate: Same as "Strategy" but the search automatically starts after any change.
Strategy immediate drag: like "Strategy immediate". The search starts during dragging a point.
Human: Try yourself to find the target and develop your own search strategy.
Optional 3D Window.
Human vs. Strategy: Competition between human and robot.
Optional 3D Window for the human available. Who has the better strategy?
Find out by comparing the factors in the resultline.

Options-Menu

Back to the Contents.

Buffered Display or direct display.
Sleep: Sleeptime in ms after a repaint()-call. Slows the display on fast machines.
Display Stepwidth: Update display every Display Stepwidth pixel.
Searchdepth Factor: Factor to increase the maximum searchdepth each round.

Help-Menu

Back to the Contents.

Help: Display the helptext for the Robot Window.
About: Display some informations about STIP.

Statusline

Back to the Contents.

Errors, as well as other status messages are displayed in the statusline below the menubar.

Resultline

Back to the Contents.

The following fields are displayed in the resultline below the statusline:

Path: the length of the path, the robot took to reach the target, in pixels
SP: the length of the shortest path from startpoint to the targetpoint
n: the number of corners of the polygon
r: the number of reflex corners of the polygon
Factor: the with which you have to multiply the length of the shortest path, to get the length of the path, the robot needed
n-Factor: equals the factor, divided by the number of corners, n
r-Factor: equals the factor, divided by the number of reflex corners, r

Canvas

Back to the Contents.

In the canvas, below the resultline can be displayed:

The polygonpoints (red dots)
The polygonsegments (dark blue lines)
The rubberline [polygon aperture](green line)
The startpoint (red dot)
The targetpoint (yellow dot)
The robot (moving red dot)
The path the robot went so far (thin black line)
The visibility polygon (green area)
The partial map (blue areas)
The shortest path tree [SPT](thin red lines)
The shortest path (thick red lines)
The tangent segments (yellow lines)

Description of the Buttons

Back to the Contents.

START: Start the search algorithm or opens the Human Window, depending on the actual user-mode.
RAND S&T: The program chooses a random startpoint and targetpoint.
PAUSE: Pause the search algorithm.
CONT: Continue with the search algorithm.
ABORT: Abort the search.
CLEAR: Clear the canvas completely.
HIDE PATH: Hide the path the robot went (only for "Strategy immediate (drag)").
SHOW/HIDE SP: Show/hide the shortest path between start and target.
SHOW/HIDE SPT: Show/hide the shortest path tree, STIP uses, for the current polygon.
SHOW/HIDE TS: Show/hide all tangent segments for the current polygon.

Hint
The TS, SPT and the shortest path can only be displayed when they have been computed already and are valid.
They can easily be invalidated by moving any point.

Human Window and 3D Window

Try for yourself to find the target!

Mouse usage

Back to the Contents.

Click with any mouse button on a point inside the current visibility polygon (green area) to indicate where the robot shall go to (Human Window only).

Navigation in the 3D Window

Back to the Contents.

Alternatively you can navigate with the following keys (3D Window):

   UP arrow key => go ahead
 DOWN arrow key => go backwards
 LEFT arrow key => turn left
RIGHT arrow key => turn right

The 3D Window shows the user a virtual sight through the polygon from the place where the robot currently is, in the direction the robot currently moves.
In the beginning the view is from the startpoint "up" in the 2D-canvas.

When the user selects with the mouse a new point where the robot shall go to, and the selected direction lies in a very different direction than the one before, the sight in the 3D Window will slowly turn around and when the new angle is reached, the robot will start on its way.

The "sky" in the robot window is blue and the "ground" is olive. The polygonsegments are grey "walls". Walls which are closer to the robot will appear brighter.

The search can not be paused (no need for that) in this window, only aborted.

Description of the Menubar of the Human Window:

Options-Menu

Back to the Contents.

Display Stepwidth: Update display every Display Stepwidth pixel.

Help-Menu

Back to the Contents.

Help: Display the helptext for the Human Window.

Statusline and Resultline in the Human Window:

Back to the Contents.

The statusline and the resultline are the same as in the Robot Window

Please read the explanations there.

Canvas in the Human Window:

Back to the Contents.

The canvas in the Human Window is mostly the same as in the Robot Window, but has some exceptions:

The polygon can not be edited here.
The polygonsegments are displayed only as far as they are either currently visible, or have already been visible at any time.
"Open" areas, which have not been seen yet, are parted from the rest with grey lines.
The visibility polygon and the partial map are permanently displayed.
The targetpoint is displayed only as soon as it is contained in the visibility polygon.
The shortest path tree can not be activated.
The tangent segments can not be activated.

For a more common explanation of the parts of the canvas of the Human Window click here.

Description of the Buttons

Back to the Contents.

START: Restart the search. Only in "Human" mode enabled.
SHOW/HIDE SP: Show or hide the shortest path to the target.
OPEN/CLOSE 3D WINDOW: Open or close the 3D Window.
ABORT: Abort the search.

For a short introduction into the theory behind this work, click here. Back to the Contents.

) Please send comments to: