Although it may appear odd or even inefficient, the drunkard’s walk algorithm is, overall, a very fast technique for determining a regional location. There is, however, one alternative which, on first consideration, sometimes appears more efficient: Search the coordinate list for the coordinate pair closest to the starting point, then look for a border between the two points.
The reasons for this second step are simple but are best illustrated by an example. Consider the states of Pennsylvania and New Jersey and assume that the coordinate pairs for each are located at, approximately, Altoona (Pennsylvania) and East Brunswick (New Jersey), placing each location roughly at the center of the state.
A mouse click in the region of Philadelphia (Pennsylvania) would not, however, select the Altoona coordinates as nearest because the East Brunswick coordinates in New Jersey are considerably closer.
Of course, searching for a border between the initial point and the closest target would identify the problem and allow another search for the next closest coordinates (and so on) to proceed. But the search for a border is almost as time-consuming as a simple drunkard’s walk and is more difficult to program reliably.
Now suppose that the located coordinate set is correct—that it lies in the same state or region as the mouse click—but that a straight line between the origin and the coordinate point must cross two borders. Sound unlikely? It isn’t. For example, look back at Figure 30.5, where the state of Maryland (at the bottom of the map) is virtually split in two by the Chesapeake Bay. At the same time, Long Island and the mainland portion of the state of New York are technically all one region but, physically, are two separate areas on the map. In this instance, neither of the algorithms discussed—the drunkard’s walk or the closest points with border-crossing tests—is adequate.
The solution for both the cases of discontinuous or extremely convoluted areas is to provide more than one coordinate point. In the MapDemo demo, the USMAP02 provides two coordinate points to identify New York: one on Long Island and one on the mainland.
For Maryland, a second point located across the Chesapeake Bay would simplify searching and would also prevent an error that is present in the current version: Selecting a point across Chesapeake Bay is very likely to locate Delaware, not Maryland.
It would also be possible to provide a larger number of coordinate point targets in each area and, granted, this should ensure very fast searches. The only drawback would be the effort of building tables of points and ensuring that there were no errors in the result. The trade-off in speed—which is minimal from the user’s viewpoint—however hardly seems worth the effort.
Another consideration that may be applicable to your own applications is how to identify areas without having them visible on the displayed image. For example, in the case of the United States map, you might wish to display a topographic or meteorological map of the country without delineating the states, which would mean no borders. As mentioned earlier in the chapter, using a hidden color map—a second map image the same size as the first that does not appear on the screen—would allow you to still be able to identify the states. You would create this second map in a memory context. Then, when the user clicks to select a point on the displayed bitmap, the search would be executed from the corresponding point on the hidden bitmap.
In this chapter, we’ve looked at several methods for working with interactive, complex bitmaps. The MapDemo demo, including on the CD accompanying this book, demonstrates two methods for mapping mouse events to complex bitmap regions. You can experiment with these and the other methods mentioned here to see how they suit the needs of your applications.
In the next chapter, we will look how graphics simulations work and methods for developing your own simulation applications.