Browse Prior Art Database

Technique to Fill a Complex Polygon With Rectangles

IP.com Disclosure Number: IPCOM000089845D
Original Publication Date: 1977-Dec-01
Included in the Prior Art Database: 2005-Mar-05
Document File: 4 page(s) / 62K

Publishing Venue

IBM

Related People

Appel, A: AUTHOR [+2]

Abstract

A common problem in computer graphics and mask design is to fill a complex polygon, which may contain numerous concave corners or holes, with simpler figures, usually rectangles. The technique herein described is designed to fill a complex polygon consisting of horizontal and vertical lines with the minimum number of rectangles.

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 56% of the total text.

Page 1 of 4

Technique to Fill a Complex Polygon With Rectangles

A common problem in computer graphics and mask design is to fill a complex polygon, which may contain numerous concave corners or holes, with simpler figures, usually rectangles. The technique herein described is designed to fill a complex polygon consisting of horizontal and vertical lines with the minimum number of rectangles.

An economical way of describing a complex polygon is by subtracting small rectangles from a large rectangle. For example, as shown in Fig. 1, the desired resultant polygon is rectangle A minus rectangles B, C and D.

All the rectangles can be described by the coordinates of their lower left corner and upper right corner, respectively.

A technique for filling a complex polygon with rectangles is as follows:

1. Read in a list of rectangle descriptors, consisting of the lower left and upper right corner coordinates. A typical set, where the large background rectangle is given first, is: TABLE

RECT. # XLL YLL XUR YUR 1 1. 1. 8. 8. 2 2. 2. 4. 5. 3 4. 3. 6. 6. 4 1. 6. 6. 8.

2. Form tables of unique values of X-coordinates and unique values of Y- coordinates from the input data. Sort this table in ascending values. Typically for the input data of the above table: Sorted X-coordinates: 1., 2., 4., 6., 8. Sorted Y- coordinates: 1., 2., 3., 5., 6., 8.

3. Construct a grid wherein the grid coordinates have the values of the sorted X and Y values, as determined in step 2. A typical grid is shown in Fig. 2 for the data in the table.

Henceforth, each grid box can be addressed by the horizontal and vertical count of box positions from the origin. A typical grid box is shown in Fig. 3, where I and J are the box counts for the horizontal and vertical directions, respectively. Assign to each grid box a variable G(I,J), which is used to indicate whether it is filled or empty. When G(I,J)=1, the box is filled; when G(I,J)=0, the box is empty. Initialize all elements of the array G to 1.

4. Skipping the first input rectangle, test the midpoint of each grid box to determine if it falls inside any of the input rectangles. Set the corresponding G(I,J) to 0 if the midpoint falls inside any rectangle except the first. A typical result corresponding to the data in the table is shown in Fig. 4.

5. At this point, the complex polygon has been filled with rectangles which are those grid boxes with a G(...