Browse Prior Art Database

Method of Preparing a Set of Graphical Shapes for Quick Searching Based on Physical Proximity

IP.com Disclosure Number: IPCOM000040171D
Original Publication Date: 1987-Oct-01
Included in the Prior Art Database: 2005-Feb-02
Document File: 2 page(s) / 54K

Publishing Venue

IBM

Related People

DeCamp, WF: AUTHOR [+2]

Abstract

Efficient proximity searching is achieved by an array approach to shape classification based on a computed center point and radius for each shape. Thus, given any one shape, its nearest neighbors can be found very quickly. An array is allocated with the number of dimensions matching the number of shape dimensions, i.e., a two-dimensional array for a two- dimensional shape. Each element of the array is an address of one or (Image Omitted) more shapes. This address could be a disk address, a main memory address, or an array index. Optimal size of each dimension is computed from total size of the design, but at some fraction of the granularity. Thus, each element represents a physical area. As the program flowchart (Fig.

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

Page 1 of 2

Method of Preparing a Set of Graphical Shapes for Quick Searching Based on Physical Proximity

Efficient proximity searching is achieved by an array approach to shape classification based on a computed center point and radius for each shape. Thus, given any one shape, its nearest neighbors can be found very quickly. An array is allocated with the number of dimensions matching the number of shape dimensions, i.e., a two-dimensional array for a two- dimensional shape. Each element of the array is an address of one or

(Image Omitted)

more shapes. This address could be a disk address, a main memory address, or an array index. Optimal size of each dimension is computed from total size of the design, but at some fraction of the granularity. Thus, each element represents a physical area. As the program flowchart (Fig. 1) shows, all shapes are read 2 and the center point and "radius", or half width, of each shape are computed 4. Also, total design perimeter, a rectangle enclosing all shapes in the design, is created. An average is taken of the radius values and used to determine a "critical" radius value 6. This value is important as it can significantly affect the algorithm performance. Dimensions of the array are calculated 8 based on the total number of shapes and the aspect ratio of the design perimeter. The ratio of design units to array indices is computed 10 and stored for use during the searching process. The next shape 12 is then addressed. The critical radius value is part of a mechanism for handling very large shapes. If a shape covers a significant fraction of a design, it would normally cause every shape search to cov...