An Enhancement of the Ramer - Douglas - Peucker Algorithm applied in map path simplification Jhomar A. Janapin and Denise O. Lumangaya. 6

ABSTRACT: The Ramer-Douglas-Peuker algorithm belongs to the polyline simplification algorithms, which main process is to reduce the number of points in a polyline and at the same time retaining its essential characteristics to keep its overall shape as much as possible. The researchers carefully studied and analyzed the algorithm, what it is about, what its purpose is, and how it basically works. Given a polyline, the algorithm works by first, selecting the initial point on the line, called the anchor, and the last point, defined as floater. These two pints are automatically kept to be part of the simplified polyline. A straight line, or the approximated line, is drawn to connect these two points and the perpendicular distances from this line segment to all the intervening vertices are calculated. Next, the computed distances of the vertices are then compared to a user-defined tolerance or epsilon. Points with distances that are lower than the value of the epsilon can be discarded and not to be selected as part of the simplified output. On the the other hand, if a specific point has a perpendicular distance greater than the tolerance, it is kept and selected as a new floating point. A new line segment is generated, defined by the anchor point and the new floating point. The offsets or the distances of vertices are recalculated and the line is repeatedly subdivided into polylines until the tolerance is met. When the set tolerance is achieved, the anchor is moved to the most recently selected floater. The algorithm recursively calls itself until the anchor point reaches the last point of the line. When the process is completed, a simplified polyline is generated consisting of all vertices selected and kept and is connected by a straight line. The researchers encountered three problems during the study. The first one is that the algorithm produces intersections. The objective for this problem is to be able to produce a more simplified polyline be removing the intersection in the output. As a solution, the researchers added a function that will detect intersections in the input and will eliminate them from the output by completely removing the point of intersection before the simplification process is executed. The second problem is the lack of the algorithm to deal with equidistant vertices from the approximated line. Having two or more vertices with the same distance (equidistant) from the initial approximated line, assuming that those vertices have the maximum distance and exceed the tolerance, the algorithm can produce multiple outputs depending on which of those equidistant vertices it chooses to add the simplification. To solve this problem, the researches added a function that detects the occurrence of equidistant points with the maximum distance and, if there had been any, outputs all possible solutions. The last problem is the algorithm's recursive property. Since the algorithm uses recursion, it is very prone to cause a stack overflow. The researchers converted the algorithm into a non-recursive, iterative algorithm as a solution. As a result, the newly enhanced algorithm barely produces intersections in the outputs, provides and displays all possible simplifications for an input polyline, if there are more than one, and is now safe from causing stack overflows. Since the Ramer-Douglas-Peucker Algorithm can be applied in various applications such as cartography and visual displays of geographic maps using Geographic Information Systems (GIS), which provide users the most up-to-date geodata and geoprocessing, the researchers decided to apply the enhanced algorithm into a Map Path Simplification Application, where in the system is connected to Bing Maps. Its main use is to find a route from one address to another, provide detailed directions for that specific route, and simplify it by eliminating some of the roads and landmarks provided in the current directions, leaving only the major ones. The researches highly recommend the developed system mainly for people who often rely on maps to know how to get from one place to another, programmers and developers who are interested in related topics about this study, and for future researchers.;Undergraduate Thesis (BS in Computer Studies major in Computer Science) - Pamantasan ng Lungsod ng Maynila, 2016 56

5

5