>>  Research >>  Campus

 Navigator

Filtering takes place by means of geometric calculation, rather than graph computation. At this point the second map with a transparent layer is used to visually outline the algorithm.

The goal of the algorithm is to find a certain number of descriptions that most accurately pin-point the selected location. Initially, this number is set to 4. Upon clicking a point on the map, the algorithm first finds out whether the point is inside a building. If this is the case, the observation is recorded in an array, and the number of missing descriptions drops to 3. If the point was not in a building, but rather in the perimeter (see above) of the building, then this observation is recorded, and the number of missing descriptions drops to 3 as well. There cannot be an instance, in which both cases occur.

Now that the obvious cases have been taken care of, the algorithm proceeds to the next stage of finding the next best descriptions. It starts out by constructing a circle of radius 1 around the selected coordinate. If the circle intersects with any buildings, the observation is recorded in an array. Should such an observation occur, the number of missing descriptions is decremented. The algorithm proceeds with incrementing the radius, constructing circles, and intersecting them with buildings, until it has found enough matches to satisfy the missing descriptions. At this point, it is not yet clear, what direction the buildings have in respect to the initial coordinate.

In the next step, the algorithm scans through the list of intersections (at most 4), and uses the function BestDir to extract the best matching direction, one of North, South, East, West, Northeast, Northwest, Southeast, or Southwest. Because we started out looking for adjacent buildings by constructing a circle, the distribution of matching objects will be relatively even. If it is not, for example, if the algorithm found two buildings in the North, the next step will decide on which of the matches are to be kept. Obviously, the closer buildings will serve much better for the purpose of spatial relations, which is why they are kept and the rest is thrown out.

We may note that if a distribution of adjacent buildings is somewhat even, we will be able to extract more of the four descriptions, whereas a skewed distribution, like the one described above, returns fewer descriptions. This is usually the case for points closer to the border of the map. In order to make even those descriptions descriptive, accumulated directions, such as Northwest help in removing some of the ambiguity.