An international conference connecting people
in CAD research, education and business
Bookmark and Share
Copyright (C) CAD Solutions, LLC. All rights reserved.
Proceedings of CAD'14, 2014, 20-22
Removing Rectangle Containment from Area NURBS Generated Shapes

Les A. Piegl, University of South Florida
Parikshit Kulkarni, Synopsys, Inc.
Khairan D. Rajab, Najran University

Abstract. Given a set of axis-aligned rectangles R0,...Rn in the plane, for each query rectangle Rq we are looking for a set of rectangles Rk,...,Rl  so that Ri is contained in Rq, i=k,...,l. That is, we are looking for all rectangles that are contained inside Rq. In order to serve certain applications such as VLSI design and graphical queries, we are also looking for a set of rectangles so that Rq is contained in Ri. That is, all rectangles are sought so that they enclose the query rectangle Rq. The algorithm presented herein will remove both contained and enclosed rectangles simultaneously. This problem arises in applications where rectangles are used to describe shapes. One way to generate such a set of rectangles is via region growing: select a guiding curve such as the medial axis, then for each discretized point on the medial axis grow a rectangle until it hits the boundary, i.e. until it cannot be grown any further without leaving the boundary or creating a skewed rectangle. Unfortunately, region growing can produce rectangles that are contained in one another. Since our main application is to generate area NURBS from these rectangles, containment is not allowed to produce meaningful shapes.

Keywords. Rectangle containment, area NURBS, shape modeling

DOI: 10.14733/cadconfP.2014.20-22