Browse Prior Art Database

Rectangle Overlap Test and Partitioning Technique

IP.com Disclosure Number: IPCOM000085346D
Original Publication Date: 1976-Mar-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 3 page(s) / 61K

Publishing Venue

IBM

Related People

Appel, A: AUTHOR [+3]

Abstract

A common problem in computer graphics is to determine when two polygons overlap, for example: hidden line elimination, picture shading and raster plotting.

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

Page 1 of 3

Rectangle Overlap Test and Partitioning Technique

A common problem in computer graphics is to determine when two polygons overlap, for example: hidden line elimination, picture shading and raster plotting.

A similar problem has arisen in the automatic design and analysis of circuits for computers. The physical design of a circuit involves the placement of varied regions which constitute circuit elements. These regions are usually polygons consisting of horizontal or vertical lines, such as shown in Fig. 1. It is necessary to find regions of overlap and to break complex regions into small rectangles. These rectangles can then be compared to other rectangles on other layers.

A fast reliable method for finding rectangle to rectangle overlap and decomposition will be described. For example, as shown in Fig. 2, if R1 overlaps R2 the six rectangles R1, R2,R3,R4,R5,R6 are needed, as shown in Fig. 3. Also, it must be known that R1,R2,R3 are on layer 1 and that R4,R5,R6 are on layer 2. Also it must be known when no overlap occurs.

The following is a fast technique to accomplish this.

1. Rectangles will be described by the lower left

corner coordinates and the upper right corner

coordinates, as shown in Fig. 4. Two rectangles

are given by four numbers, IX1, IY1, IX3, IY3,

as shown in Fig. 5. The other coordinates

can be derived. Typically:

IX2 = IX1,

IY2 = IY3,

IX4 = IX3,

IY4 = IY1.

Therefore, the complete rectangle can easily be drawn.

2. The two given rectangles can alwa...