Personal Navigation And Portable Devices Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Personal navigation has become increasingly popular nowadays. There are different portable devices as well as many map-making tools available online. There are various methods by which we can route a path between the origin and source destination, such maps are called Route Maps. Such maps are cluttered with extraneous information. Schematized maps provide a simple solution to this problem. The development of schematizing application onto mobile devices helps the user to navigate with ease to the destination location in a simpler manner without losing the essence of navigation and provide him with proper directions. The study suggests the design of Schematic Maps on to the Mobile. The study identified the algorithm for these activities, as well as the design aspects that could provide useful information to the user using schematized maps on a mobile based platform

The maps we use are designed to be very precise with respect to the distance and the orientation of the line or route, but they are drawn to the scale of a standard scale. However there is an another very important class of geographical maps of uniform scale that is sacrificed for readability. The most famous is the ¿½Metro Rail Subway Map of London¿½. The outline of this map was introduced by Harry Beck in 1931. Today the Schematic Style is widely used but not supported by mapping tools. The objective of this project is to help others in the production of schematic maps.

The simplification of form depictments as a geographic map-whether the abstract information of

irrelevant detail to reduce the user cognitive load the map, or to simplify information, when a smaller scale map is derived from a detailed map. To derive such a schematic map with reduced shape information from a detailed spatial data, techniques for reducing spatial accuracy of shape aspects to abstract from the exact course of linear entities or the detailed shape of areal geographic objects is required. These schematized maps rather provide a user with the necessary information he requires keeping into consideration the human cognition and simplifying the route. Such maps help to ease the interpretation of information by process of cartographic abstraction and shape simplification.

Today the schematic style is widely used, but not well-supported by map-making tools. The purpose of this project is to aid others in producing schematic maps.

1.2 Schematization Algorithm

The schematization algorithms have been modified to a great extent to simplify the maps to maximum extent. Never presented a solution to solve the problem of schematizing maps where he used the concept of simplifying the line segments parallel to the one having a given orientations. This method was not automated and also it also did not support the route throughout as it missed many of the vertices. Thomas Barkowsky help automate the whole process of schematization; drawing the maps for the purpose of drawing general schematic maps and metro maps. The Discrete Curve Evolution theory was used to achieve simplification in polygonal lines. The algorithm preserved the topological features of the input map it doesn¿½t restrict the possible edge directions nor increase station distances to enhance readability. The algorithm is more suitable for simplifying maps rather schematizing public transport maps. Several other algorithms were subsequently given by Avelar and Muller, Cabello and Kreveld to design the schematic maps for paths.Many other algorithms were introduced to route the metro maps. Stott and Rodgers, Klau and Mutzel are some other few to be named. The algorithms that have been used in our project are: Djikstra¿½s Algorithm, Discrete Curve Evolution, Douglas Peucker Algorithm.

1.3 Android Operating System:

Android OS can be found on a large scale these days on many of the cell phones and tablets. It is an open source software stack-computer software available in source code form and it¿½s a set of software subsystems/components delivering a fully functional solution. The android OS consists of the following: operating system, middle ware and a few key applications. The mobile OS of android is based on a modified Linux Kernel.


The schematization of maps mainly involves the development of a schematization algorithm. Various implementations of Discrete Curve Evolution Theory, Douglas Peucker algorithm and Djikstra¿½s algorithm have been used over the years in various ways to develop schematization algorithms. Harry C Beck in 1931 made a schematic map. An electrical engineer he based the design of the London tube map on basis of circuit diagram. The map locally distorted the scale and shape of the tube route but preserved the overall topology of the tube network. Thomas Barkowsky et. al (2001) presented the Discrete Curve algorithm for simplifying geometric shapes. It involves the stepwise elimination of kinks that are least relevant to shape of polygonal curve in simplification. Agrawala and Stolte

(2001) used iterative improvement optimization in case of simulated annealing produce sketch route maps for vehicular navigation. Cabello (2001) present a combinatorial algorithm for schematization of road networks. Avelar(2002) presents an algorithm for automatic generation of schematic maps from traditional vector bus route networks pre-generalized using Douglas Peucker algorithm.

The android operating system is an open software. This helps us to develop and use application on various cell phones. Moreover Android delivers a complete set of software for mobile devices: an operating system, middleware and key mobile applications. The Android SDK includes a mobile device emulator -- a virtual mobile device that runs on to the computer. The emulator allows prototyping, development, and testing of Android applications without using a physical device.

The Android emulator mimics all of the hardware and software features of a typical mobile device, except that it cannot receive or place actual phone calls. It provides a variety of navigation and control keys, where one can "press" using the mouse or keyboard to generate events for the application. It also provides a screen in which the application is displayed, together with any other Android applications that are running. The emulator also includes a variety of debug capabilities, such as a console from which one can log the kernel output, simulate application interrupts (such as arriving SMS messages or phone calls), and simulate latency effects and dropouts on the data channel.


Software industry keenly relies on testing to ensure quality and reliability of the product.

The following flow diagram has been used in order to extract the points as well as obtain the points that can be used in order to obtain the schematizing maps.

Explanation of the flow diagram:

The source and destination points are kept as fixed points as they provide the outline for the schematized path. These points are taken from the google maps. Now using one of the schematization algorithm in this case the douglas peucker algorithm the given set of relevant points are given as inputs. These relevant points give us a new set of points. These set of new points help us in order to form the schematized maps.

The above fig. gives us a simplified route using the Douglas Peucker Algorithm.

Now we derive the test case for the given schematization algorithm. The test case helps us to determine whether or not the software system or the application works properly or not. In this case we are developing an application; hence it helps us to determine the utility of the application.

Purpose: A geographically accurate map is converted into a schematized map keeping into consideration the utility of the schematized map for the intended audience.

Pre-requisites: The manager of the transport company assigns the source location and the destination location in accordance to where the goods need to be transported the truck driver is handed the map with the locations(gas station, food joints) which might be helpful for him during his journey.

Test Data: The source location and the destination location¿½s latitude are entered into the system, by following the Douglas-Peucker algorithm the distance between these two is sorted out. The readability of the user is taken into consideration.

Steps: 1. Enter start location and destination location.

2. The route is sketched on the Google map in order to locate the points.

3. The Douglas Peucker algorithm helps to sort these points on basis of their relevance into fixed, movable and removable points.

4. The fixed points and the movable points are taken into consideration and the schematized map is produced.

5. The production of the schematized map takes place in the android environment.

Software Engineering Methodology:

The Software engineering methodology is used to structure, plan and control the process of a given information system. This may involve the pre-definition of specific deliverables and artifacts that are created and completed by a team to develop or maintain an application.

Extreme programming is one of the several popular Agile processes. The flow in the extreme programming is as shown in figure 1. It has proved to be successful to a great extent in many companies worldwide. It stresses customer satisfaction; it empowers the developers to respond to changing customer requirements. The below given diagram helps us in order to understand the step by step evolvement of the planning and feedback steps that are involved in the extreme programming.

Scenario of extreme programming

Team Software Process(TSP) provides us with a disciplined context for engineering projects. The principle of TSP is that engineering teams can do extraordinary work, only if they are properly formed. Suitable training, staffing of skilled members enhance the efficiency of the output work. The main objective of TSP is to build and guide such teams.

The TSP helps to enhance the performance of large scale software projects that largely depend on the performance of a team or an individual. This helps us to produce and obtain direct measurable results,quicker return on investments also providing a more flexible,tactical approach to improvement.

TSP has been used by many organizations such as Microsoft,FujiFilm,HitachiSoft,Softtek,Toshiba,Adobe,EDS,Oracle,Intuit.



The solutions to find an optimal route between two points on a road have been extensively studied and many results have been published so far in this context. The fastest algorithms have been found that can find an optimal route inroad networks between two extreme ends of a continent within milliseconds (Djikstra¿½s Algorithm). However its difficult to find a visualized route between these paths on a single paper. These routes provide an overview of the route but at the same time it distracts the essence of the route required for navigation. For example there are many streets or highways which the user doesn¿½t need to know about when driving; he also doesn¿½t need to know the every change in direction that might be of least importance.

In this paper we present a general idea to reduce the extraneous information to as little as possible while still maintaining the route and providing the useful information for the user¿½s orientation using schematized maps on a mobile based platform. Schematization algorithms have been developed over the years in order to schematize maps. The schematizing maps till date have found implementation in only map making tools used on a computer platform. This project gives an implementation of the schematizing maps on mobile based platform.


In this project we will be using the combination of Extreme programming and TSP to develop the schematizing software on the android based Operating system to be used on a mobile platform.


In our project we are implementing the various algorithms in various cycles and providing them to the customer to suit his necessities. We also look into the changes that can be made that might help in increasing the efficiency of our software. We implement the Agile methodology of Extreme Programming and Team Software Process (TSP) to reap the maximum out of them and help them to develop our software. Test Driven Development was done implementing the Djikstra¿½s Shortest Path Algorithm. The roles amongst the team members and worksheets were made as per the TSP.


The software environment used is MOTODEV. It is an Eclipse-based IDE. MOTODEV being easy-to-access, internet-enabled and open environment helped to gain unlimited access to the android platform to develop applications. MOTODEV provides helped us gain information, easily accessible, tools and documentation, community support, and go to market resources¿½to get started, develop, and distribute Android applications. Being an open source it will help us to gain feedback from customers. Android is a software stack for mobile devices that includes an operating system, middleware and key applications. The Android SDK provided the tools and APIs necessary to develop our software using the Java programming language.

Android is a flexible software platform. It¿½s designed to deliver a personalized and customizable user experience on mobile devices. This is a great advantage over the other platforms which might not support a flash player.


5.1Djikstra¿½s Algorithm

5.2 Douglas Peucker Algorithm

The purpose of the schematizing algorithm is to give a 'curve' composed of line segments and consequently find a curve similar with lesser points. The algorithm must define a difference based on the distance between the original curve and the curve that has been simplified. The resultant curve obtained is a simplified subset of points that have been previously defined by the original curve. This algorithm cuts down the number of points in a curve to the one that is by a series of points previously defined. The initial form of the algorithm was put forward in 1972 by Urs Ramer. A revised version of the algorithm was later introduced in 1973 by David Douglas and Thomas Peucker.

The algorithm continuously divides the line. At the start we make available all the points between the first (source) and last point (destination). The Douglas Peucker algorithm accordingly marks the first (source) and last point (destination) to be kept. It denotes that the point furthest away from the line segment and with the source and destination points as end points (this point is furthest away on the curve from the approximating line segment between the given two end points). If the obtained point is closer than e to the line segment then any points not presently marked to keep can be removed without the smoothed curve being worse than e.

If the obtained point is furthest away from the line segment is greater than e from the approximation then obtained point is not removed. The algorithm repeatedly calls itself with the first point and the worst point and then with the worst point and the last point (which includes marking the worst point being marked as kept).When the recursion is completed a new output curve can be generated consisting of all (and only) those points that have been marked as kept. Refer appendix.

Application of the Douglas-Peuker line simplification to a set of line features results in a new set of line features in which each feature is represented by a subset of its original vertices. The number of vertices removed during the process (i.e. the level of simplification) depends both on the complexity of the input data, and a user-defined parameter referred to as the weed tolerance. In general, the higher the value of this tolerance, the greater the number of vertices removed.



The schematization algorithms have been found since a longtime. There is constant development of new algorithms with more accurate information. In this project we look forward to implement the algorithms on a mobile device. Even though there are several existing devices such as GPS, this mobile enabled application helps us to maintain the essence of travelling without having extraneous information. And as of today most people have a tendency to get all their information on their cell phones or PDA¿½s this application will help to navigate easily. Even people who are not well versed with map reading can be able to reach their desired destination without any problems. The Douglas Peucker algorithm is mainly implemented taking into consideration the human cognition for this project. Research indicated that it is by-far the most reliable algorithm with respect to human cognition.