Proposal for an intermediary shape representation using dots on minimal rectangles
✍ Scribed by Yoshitomo Yaginuma; Masao Sakauchi
- Book ID
- 104591605
- Publisher
- John Wiley and Sons
- Year
- 1993
- Tongue
- English
- Weight
- 970 KB
- Volume
- 24
- Category
- Article
- ISSN
- 0882-1666
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
In handling the graphic data of a finite size, the minimal rectangle, which is the minimal rectangle surrounding the graphic data, or the minimal sphere, which is the minimal sphere surrounding the data, often is employed as the intermediary representation of the data to speed‐up the retrieval and manipulation of the graphic data. However, when most of the retrieval time is occupied by the check of the intersection rather than by the tracing of the data structure, as in the case of complex data or data placed on the external memory with a lower speed, a more efficient intermediary representationof the graphic data is required. This can reduce the number of intersection checks and speed‐up the retrieval, compared to the method based on the minimal rectangle or the minimal sphere.
From such a viewpoint, this paper proposes an intermediary representation of the graphic data using dots on the minimal rectangle as one such intermediary representation of the data. Theoretical as well as experimental evaluations are presented. It is seen as a result of the theoretical calculation and simulation experiment that compared to the method based on the minimal rectangle, the proposed method can reduce drastically the number of intersection checks which helps to reduce the actual retrieval time. In the case of straight‐line data, for example, of length less than the edge length of the retrieval area, the number of intersection checks can be reduced to one‐fourth that of the method based on the minimal rectangle, even in the worst case.