Data structures and knowledge representation for automated name placement
This thesis contains the result of an investigation into the design and implementation of a computer-assisted system to deal with the particular problem of point name placement on EMR Canadian topographic maps. Software was written to correlate the names database, National Geographic Names Data Base, to the features database, National Topographic Data Base. This software was tested on the names and features of one 1:250,000 map sheet, NTS21G. This test showed that of 309 point names in the map sheet area, 169 (55%) were matched to identifiable features. Of these 169 matches, only 20 were found to be placed on the map sheet. Sixteen names of villages were found on the map, but no matching feature was found in the features database. A novel object based quadtree spatial data structure was designed, tested and implemented. A prototype name placement system called NAPLES was designed, and a portion of it was implemented. This prototype makes use of the quadtree structure to detect interference and overlap of names with features, grid lines, and other names.