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

A polygon clipping algorithm

In this document is described how to clip two 2-D polygons and into the sets , , and A AND B.

Introduction

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.

Weiler-Atherton

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.

Binary space partition

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 new algorithm

The framework puts some constraints on the types of polygons used. These constraints are:

The polygons are clockwise oriented.
The polygons do not have holes.
The polygons should not be self-intersecting.

Note that concave polygons are allowed. If we have polygons which do not meet these constraints they must be decomposed into polygons which do.

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:

1

Intersect the two polygons. This will lead to the same polygons, with the difference that the intersection points with the other polygon are added as vertices.

2

Label all the (new) edge from both polygons into Inside, Shared, or Outside. The labeling is done according to the following rules:

Shared: If both vertices on this edge are vertices of the other polygon, and these vertices of the other polygon are connected, than this edge is Shared.
Inside: If not Shared, then if the middle of this edge is inside the other polygon, then this edge is Inside;
Outside: If not Shared and not Inside, then this edge is Outside.

3

Find all polygons which are formed by the clipping. This is done by searching for all clockwise oriented polygons. This search is started at all vertices in both polygons, in two directions. Multiple inclusion of the same polygon is prohibited by checking that each edge is only included once for every direction.

4

Classify the polygons found in the previous step into the three sets. This is done with the next rules: If there is an edge in the polygon originating from polygon

, with labeling Outside, than it is not in

. Similar, if there is an edge in the polygon originating from polygon

, with labeling Outside, than it is not in

. This leads to one of the three classes.

We have a special case if at step 1 no intersections are found. In this case, we can have three different situations:

Polygon is inside . This is the case when any vertex of is inside , which easily can be tested. If is inside , we arbitrarily split in two polygons, with somewhere on the split. We have to do this, because we do not want polygons with holes.
Polygon is inside A. Similar handled to the case above.
The polygons and are disjunct.

About this document ...

The command line arguments were:
latex2html -split 0 -reuse -no_navigation appendices.tex.

The translation was initiated by [email protected] on Tue Jul 12 14:10:37 MET DST 1994