bef raster graphics format unified color technologies.

illustrates a binary search tree which can be used to determine between which pairs of successive chains in figure 13 a given point lies. The algorithm described by Preparata and Lee is based on organizing the line segments of the region boundaries into monotone chains.įigure 14. The worst algorithm to use in solving this problem is the simplest one: search through all regions and determine the first region in which the given point lies. The point in region problem is given a point, determine which region it is in. Because a complete review of these algorithms would be quite lengthy, in the next few paragraphs we give the reader a feel for them by describing only one of them, an algorithm to solve the point in region problem published by Lee and Preparata (1977). Each finds some way to use the order in a data point set to increase the search efficiency.Ī bibliography of papers discussing and describing these fast geometric search algorithms for vector format data is given at the end of this chapter. This research has shown that the typical brute force searching algorithms for vector format data are not the most efficient. This point of view which admits the possibility of data sets executing quicker in vector format is possible because of the recent advances made in the field of computational geometry. Rather it should be the worry of the system itself. The thesis of this chapter is that the data format question and its associated algorithm should not be the worry of a user of a spatial information system. Which algorithm will execute quicker depends on the characteristics of the data set being operated on. However, it is not necessarily the case that the simpler algorithm for raster format data will execute faster than the corresponding algorithm for vector format data because raster data typically has a much higher data volume. Raster format data has an advantage over vector format data in that the algorithms to determine in what region a pixel lies, to determine the boundary of a given region or to do polygon overlay, are simpler algorithms than the corresponding algorithms for vector format data. Haralick, in Map Data Processing, 1980 IV RASTER FORMAT VS.

Bef raster graphics format unified color technologies.