Browse Prior Art Database

Technique to Fill A Polygon With Rectangles

IP.com Disclosure Number: IPCOM000088760D
Original Publication Date: 1977-Jul-01
Included in the Prior Art Database: 2005-Mar-04
Document File: 5 page(s) / 95K

Publishing Venue

IBM

Related People

Appel, A: AUTHOR [+2]

Abstract

A technique is described for breaking a given polygon, consisting of horizontal or vertical lines, into a set of rectangles. These rectangles can then be generated by mask drawing machines for masks which are assemblies of polygons of varied complexity.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 55% of the total text.

Page 1 of 5

Technique to Fill A Polygon With Rectangles

A technique is described for breaking a given polygon, consisting of horizontal or vertical lines, into a set of rectangles.

These rectangles can then be generated by mask drawing machines for masks which are assemblies of polygons of varied complexity.

A simple mask is illustrated in Fig. 1. This mask consists of the six polygons illustrated in Fig. 2, which contain only horizontal or vertical lines and are the most common shapes used for this purpose.

An electron-beam vector scan machine is used to construct these masks by drawing rectangles. It is convenient for mask designers to draw and manipulate polygons; however, it is essential that the polygons be broken up into rectangles. The fewer the number of rectangles the more efficient the entire mask production process is, both in computer-aided design, computer time and actual physical fabrication. Since large number of polygons and rectangles have to be processed, an optimal solution, that is, the mathematical optimum, may be less valuable than the solution which consumes the least total computer processing time. The general solution to partitioning polygons into rectangles where the number of rectangles is the minimum is a large mathematical problem, and it is not known if it has been solved. The technique to be described finds an optimal solution for the shapes (Fig. 3) that are most commonly used in mask design. Since the most common shapes are those shown in Fig. 2 and since the technique to be described arrives at an optimal solution for these shapes in little computer time, this technique, while not general, is sufficient for mask processing. The rectangle partitioning technique is as follows:

1. Read in the series of points which, connected together, form the polygon of interest (Fig. 4).

2. Scan this list of point coordinates and form a table of unique values of X and Y.

For example, for the shape in Fig. 4:

X LIST: 4, 9, 7, 2 over

Y LIST: 6, 4, 1, 3.

3. Sort the table of unique values of X and Y. e.g.,:

SORTED X LIST: 2, 4, 7, 9

SORTED Y LIST: 1, 3, 4, 6.

4. Construct an imaginary grid where the grid lines are horizontal or vertical lines whose constant X or constant Y values are the unique values of X or Y (Fig.
5).

5. Assign each element of this grid to an array IS (NX, NY) where NX is the number of unique values of X minus 1 and NY is the number of unique values of Y minus 1 (Fig. 5). For our example: NX = 3 and NY = 3.

1

Page 2 of 5

6. Test the midpoint of each grid box (Figs. 6 and 7) to see if this point falls within the original polygon. If it falls inside the polygon, reset the corresponding IS element to 1.

7. At this stage we have a set of rectangles which form the original polygon, that is tho...