A Knowledge Based System for Minimum Rectangle Nesting

Editors

Juan D. Velásquez; Sebastián A. Ríos; Robert J. Howlett; Lakhmi C. Jain

Document Type

Chapter

Publication Date

2009

Publication Title

Knowledge-Based and Intelligent Information and Engineering Systems

Publisher

Springer Berlin Heidelberg

First page number:

103

Last page number:

111

Abstract

Nesting algorithms deal with the optimal placement of shapes in specified regions subject to specified constraints. In this paper, a complex algorithm for solving two-dimensional nesting problem is proposed. Arbitrary geometric shapes are first quantized into a binary form. These binary representations are subsequently processed by operators which nest the shapes in a rectangle of minimum area. After nesting is completed, the binary representations are converted back to the original geometric form. Investigations have shown that the nesting effect is driven by quantization accuracy. Therefore, better accuracy is possible given more computing time. However, the proposed knowledge based system can significantly reduce the time of nesting, by intelligently pairing shapes, based on prior knowledge of their form.

Keywords

Algorithms; Binary quantization; Computer algorithms; Expert systems (Computer science); Forms; Binary; Geometric quantization; Knowledge based system; Nesting

Disciplines

Computer and Systems Architecture | Computer Engineering | Electrical and Computer Engineering | Engineering

Language

English

Permissions

Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.

UNLV article access

Search your library

Share

COinS