Weiler-Atherton Clipping Applet
Background
The Weiler-Atherton clipping algorithm is a general purpose 2D clipping algorithm. While most clipping algorithms are optimized for a rectangular clipping region, the Wieler-Atherton algorithm can use simple polygons for both the subject of the clipping as well as the actual clipping region itself. The algorithm has two general phases. In the first phase, all of the edges of both polygons are examined to find intersections. These intersections are inserted into point lists along with all of the points from the respective polygons. In the second phase, these lists are traversed, and the resultant clipped polygons are returned.
This tool was designed to support two activities - delivering a lecture on the Weiler-Atherton algorithm and self-guided exploration of the algorithm. As a lecturing tool, the goal is to reduce the burden of creating and walking through examples. Using this tool, a professor can create new examples on the fly and quickly walk through the steps, letting the tool manage the order of operations and data structure bookkeeping. As an exploration tool, a user can use the tool to walk through various examples to see how the algorithm behaves under different conditions. My experience with students learning this algorithm is that while they grasp the general concept, they can be thrown by many of the actual details, which are rarely adequately explained.
The Applet
The applet is quite straightforward to use. Polygons can be drawn by clicking in the main drawing region and then the algorithm can be stepped through using the forward and back buttons. If the Shift button is held down, the buttons will allow you to jump immediately to the start or the end of the current phase of the algorithm. A more detailed description of the algorithm and the use of the visualization tool is available from within the application.
If you have any questions about this visualization or just want to relate your experiences using it, please don't hesitate to contact me. My username is cpa - just append it to @vt.edu to get my email address. If you are interested in making modifications (or are just curious about how the applet works), the source code is available through the OpenAlgoViz project. The tool is written in Jython, an implementation of Python written in Java.
The applet: The Weiler-Atherton clipping applet
The Weiler-Atherton Clipping Applet was written by Christopher Andrews during Spring 2008 as a semester project in a course taught by Cliff Shaffer.
Distributed by the
Virginia Tech Algorithm Visualization Research Group.
This work is available for your use, under conditions of the
Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License.
Sourcecode for the applet is available under
Gnu Public License Version 3.0.