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 Tool

The tool 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 can be found in the URL of this page - just append it to @vt.edu. If you are interested in making modifications (or are just curious about how the applet works), the source code is included below. The tool is written in Jython, an implementation of Python written in Java. I'm releasing the source under the Creative Commons attribution-share alike license, which means that you are welcome to use and modify the code in any way you like provided it is attributed to me and any sharing you do is under the same license.

The applet: The Weiler-Atherton clipping applet

The source: clipping.tgz