In graphics data management, intermediary shape representations such as minimal rectangles and minimal spheres are useful to accelerate such basic geometrical operations as range retrieval. However, when the shapes of the data are complicated or the time for the intersection checks is dominant, another intermediary representation which can reduce the number of intersection checks is desired. The authors propose a new method using 'bound dots' which locate on the contacts of the entity and its minimal rectangle. According to the results of theoretical evaluations and simulation experiments, this method can be found to drastically reduce the number of required intersection checks, compared with the ordinary method using minimal rectangles.
展开▼