The disk-hiding project
 
[ news ]
Arriving soon...
[ top ]
 
[ info ]
The disk-hiding project is a students-project based on the course Effiziente Algorithmen by Günter Rote - in summer 2006 (Freie Universität Berlin).

Its goal is a computer program, written in JAVA, to find and visualize the largest disk d in a polygon p according to the following points:

  • d lies entirely in p.
  • p can be folded (without folding d) so that d is completely hidden.
  • There is no disk d' that would be bigger than d and passing the first two points.
We also want to find the egde (egdes) at which the polygon has to be folded to hide the largest disk d.

We solve this problem the following way:

The center of the disk we want to find lies on one of the segments of the polygon's Medial Axis.

The Medial Axis can be imagined as the sum of all points that lie in the polygon and have the same distance to at least 2 polygon-segments.

Or in other words: It is a graph consisting of line- and curve-segments that are connected to each other by the nodes of the Medial Axis. Every point on a segment of the Medial Axis is equidistant to at least 2 polygon-segments. Every node of the Medial Axis is equidistant to at least 3 polygon-segments.

If we've found the Medial Axis, we use its segments to find the largest disk and the folding-edge and solve the disk-hiding problem.

The disk-finding algorithm depends on the number of folds permitted. The current roadmap plans the support for the one-fold case. For that we process every pair of segments {si;sj} of the Medial Axis and return the pair of largest disks {di;dj} with

  • di.radius == dj.radius
  • si.contains(di.center)
  • sj.contains(dj.center)
  • There is no disk dn bigger than di
Finally, we chose one of the two largest disks to be the to-be-hidden disk and create the folding-edge using the centers of the two largest disks.

[ top ]
 
[ screenshots ]

[ top ]
 
[ download ]
To start the program, you need a JAVA Runtime Environment (JRE) - Version 1.5 or higher - installed on your computer. If you don't have one, you can download it from http://java.sun.com.

To start the jar, type java -jar dhp_0_7.jar in your command shell.

The disk-hiding project V 0.7
[ dhp_0_7.jar ] : startable JAR (07.08.2006)
[ dhp_0_7src.jar ] : sources (07.08.2006)
[ JavaDoc ] : JavaDoc pages for all the sources (07.08.2006)
 
Documentation note: The documentation isn't finished yet. There will be an update from time to time. The final PDF will be released after version 1.0 of the project has been finished.
The disk-hiding project - documentation
[ dhp_documentation.pdf ] : PDF (07.08.2006)
[ top ]
 
[ roadmap ]
V 0.7
Features:
  • Draw and move a polygon, move single polygon-point
  • Find and show chains and bisectors
  • Find and show Medial Axis for convex polygons
V 0.8
New features:
  • Find and show largest disk in convex polygons
V 0.9
New features:
  • Find and show Medial Axis in simple (convex or concave) polygons
  • Find and show largest disk in simple (convex or concave) polygons
V 1.0
New features:
  • Full support of the one-fold case
  • Find and show the folding-edge to fold the polygon at
  • Visualize polygon-folding to hide the largest disk
[ top ]
 
[ credits & contact ]
The disk-hiding project is designed and written by Bettina Selig, Tilman Walther and Ingo Mohr.

All icons are taken from the Eclipse application framework, downloadable from www.eclipse.org.

The disk-hiding project is developed using Eclipse 3.1 and 3.2. (see www.eclipse.org).

If you encounter any bugs or have suggestions (or critics) regarding the project, please send me an e-mail under mohr@inf.fu-berlin.de.

Best regards,
Ingo

[ top ]