Point Location
This book has, for the most part, been written in Europe. More precisely, it has been written very close to a point at longitude 5°60′ east and latitude 52°30′ north. Where that is? You can find that out yourself from a map of Europe: using the scales on
- PDF / 274,386 Bytes
- 26 Pages / 547.087 x 685.984 pts Page_size
- 17 Downloads / 171 Views
Point Location Knowing Where You Are
This book has, for the most part, been written in Europe. More precisely, it has been written very close to a point at longitude 5◦ 6 east and latitude 52◦ 3 north. Where that is? You can find that out yourself from a map of Europe: using the scales on the sides of the map, you will find that the point with the coordinates stated above is located in a little country named “the Netherlands”. In this way you would have answered a point location query: Given a map and a query point q specified by its coordinates, find the region of the map containing q. A map, of course, is nothing more than a subdivision of the plane into regions, a planar subdivision, as defined in Chapter 2. 5◦ 6
52◦ 3
Figure 6.1 Point location in a map
Point location queries arise in various settings. Suppose that you are sailing on a sea with sand banks and dangerous currents in various parts of it. To be able to navigate safely, you will have to know the current at your present position. Fortunately there are maps that indicate the kind of current in the various parts of the sea. To use such a map, you will have to do the following. First, you must determine your position. Until not so long ago, you would have to rely for this
121
Chapter 6 POINT LOCATION
on the stars or the sun, and a good chronometer. Nowadays it is much easier to determine your position: there are little boxes on the market that compute your position for you, using information from various satellites. Once you have determined the coordinates of your position, you will have to locate the point on the map showing the currents, or to find the region of the sea you are presently in. One step further would be to automate this last step: store the map electronically, and let the computer do the point location for you. It could then display the current—or any other information for which you have a thematic map in electronic form—of the region you are in continuously. In this situation we have a set of presumably rather detailed thematic maps and we want to answer point location queries frequently, to update the displayed information while the ship is moving. This means that we will want to preprocess the maps, and to store them in a data structure that makes it possible to answer point location queries fast. Point location problems arise on a quite different scale as well. Assume that we want to implement an interactive geographic information system that displays a map on a screen. By clicking with the mouse on a country, the user can retrieve information about that country. While the mouse is moved the system should display the name of the country underneath the mouse pointer somewhere on the screen. Every time the mouse is moved, the system has to recompute which name to display. Clearly this is a point location problem in the map displayed on the screen, with the mouse position as the query point. These queries occur with high frequency—after all, we want to update the screen information in real time—and therefore have to be answered fas
Data Loading...
