This document is out of date, describing the status of the end of 1993. On 7 July 1995 a paper describing the algorithm is submitted to ACM Transactions on Graphics
In this document is described how to clip two 2-D polygons and into the sets , , and A AND B.
Why is there need for another algorithm for clipping polygons? With a glance at the subject this seems a well studied part of computer graphics. But there is a difference in the usage of the result: in computer graphics the problem is to determine to which set a certain point belongs; in this research we need to have the sets themselves. This means that an algorithm which decides for a given point that is inside , but not in is sufficient for the general computer graphics approach, but not for the set division problem itself, which we need.
There already exist two algorithms which do produce the sets which we need; we will discuss the Weiler-Atherton and the binary space partition method.
The Weiler-Atherton algorithm [section 15.7.2]Foley,[appendix A]Hilhorst starts with the intersection of the two polygons. Then all edges of the polygons are doubled, which give an outer and an inner edge for the polygons. Using complex rules these outer and inner edges are combined into polygons; also do these complex rules specify in which of the three sets these newly produced polygons fall.
Space bipartition [section 15.5.2]Foley is based on the notion that a polygon can be seen as a couple of lines which specify half spaces, combined with boolean equations which combine these half spaces into the polygons. Clipping polygons can be expressed as boolean expressions of the polygons. Although the clipping itself is easy using this approach, the back projection from the boolean equations to the polygons is very difficult.
More information on Binary space partitioning can be found in the BSP FAQ.
The framework puts some constraints on the types of polygons used. These constraints are:
We propose an algorithm which is very similar to Weiler-Atherton. The major difference lies in the way the intersected polygons are combined back into polygons. The algorithm exists of the following steps:
This document was generated using the LaTeX2HTML translator Version 0.5.3 (Wed Jan 26 1994) Copyright © 1993, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 -reuse -no_navigation appendices.tex.
The translation was initiated by firstname.lastname@example.org on Tue Jul 12 14:10:37 MET DST 1994