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 a 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
Shape simplification of the map-like depictments to either abstract information from irrelevant detail to reduce a map user's cognitive load, or to simplify information when a map of a smaller scale is derived from a detailed reference 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. Neyer 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.
BACKGROUND AND RELATED WORK:
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.
3. SOFTWARE ENGINEERING FOR SCEMATIZING MAPS:
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:
Enter start location and destination location.
The route is sketched on the Google map in order to locate the points.
The Douglas Peucker algorithm helps to sort these points on basis of their relevance into fixed, movable and removable points.
The fixed points and the movable points are taken into consideration and the schematized map is produced.
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.
XP-feedback.gif 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.
Figure 1. FLOW IN EXTREME PROGRAMMING
APPROACH AND UNIQUENESS
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.
SOFTWARE DESIGN
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.
SOFTWARE METHODOLOGY
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.
SOFTWARE ENVIORNMENT
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.
ALGORITHM
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 similar curve with fewer points. The algorithm needs to define 'dissimilar' based on the maximum distance between the original curve and the simplified curve. The simplified curve consists of a subset of the points that have been previously defined by the original curve. (Douglas Peucker Algorithm) This algorithm reduces the number of points in a curve that is approximated by a series of points. The initial form of the algorithm was independently suggested in 1972 by Urs Ramer and 1973 by David Douglas and Thomas Peucker.
The algorithm recursively divides the line. Initially we provide all the points between the first and last point. The algorithm automatically marks the first and last point to be kept. It denotes the point that is furthest from the line segment with the first and last points as end points (this point is obviously furthest on the curve from the approximating line segment between the end points). If the point is closer than ε to the line segment then any points not currently marked to keep can be discarded without the smoothed curve being worse than ε.
If the point furthest from the line segment is greater than ε from the approximation then that point must be kept. The algorithm recursively 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.
5.3 Discrete Curve Evolution:
DISCUSSION
CONCLUSION
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.
