Reducing graphic conflict in scale reduced maps using a genetic algorithm

Effective map generalisation involves careful examination of the interactions between all mapsymbols. These interactions may give rise to obvious graphic conflicts of proximity andoverlap. They may also determine whether important messages, regarding the structure andform of the mapped features, are effectively communicated (for example, in the alignment ofbuildings, parallelism between neighbouring rivers and roads, and the clustering of woods andlakes). Graphic conflict can be addressed by a combination of possible actions such aselimination, displacement, amalgamation and boundary simplification, combined withappropriate techniques for evaluating the quality of the result. However, the application of anindividual operator may have an effect on a map symbol that was not previously in conflict,resulting in propagation of conflict within the map space. A partial solution to this problem isfor objects to be moved after scaling so that they remain distinct, visual entities. The researchpresented here, which is related to previous work [1] [2], describes a procedure that makes useof the displacement of multiple map objects in order to resolve graphic conflict.The solution presented here is a combinatorial problem the size of which depends upon thenumber of objects represented and the position of each object within an (x, y) co-ordinate space.Given that it is undesirable to displace an object too far from its original position, it is necessaryto constrain its movement to within a short distance, which reduces the co-ordinate spaceconsidered for each object. Here, each of n discrete polygonal objects is assigned a continuousspace of v co-ordinates (x, y pairs) into which they can possibly move. This results in vnpossible distinct map configurations; the assumption being that some of these configurationswill contain less conflict than the original. Finding an acceptable configuration by means of anexhaustive search is, however, not practical for realistic values of n and v giving rise to the needfor a heuristic search approach. The next section provides an introduction to the heuristicprocedure, the Genetic Algorithm, selected by the authors