Journal of Remote Sensing Technology
Journal of Remote Sensing Technology(JRST)
Frequency: Annually
Simplification of Polygonal Terrain Elevations for Construction of Reduced Visibility Graphs and UAV Path Planning
This work proposes an algorithm to simplify polygonal models of digital terrain elevations. The objective of this simplification is the cost decrease of the construction of reduced visibility graphs for Unmanned Aerial Vehicle (UAV) path planning. Given the original polygonal model O of the terrain elevations and O’(t), the simplification of O after the iteration t-1, the algorithm uses invisibility areas between convex vertices as a metric for elimination of the polygon vertices. At each iteration, for each pair of consecutive convex vertices of O’(t), the algorithm calculates the invisibility area between those vertices, based on the original model O. If this calculated area added to the total invisibility area is less than a specified limit, then the vertices between the two consecutives vertices are eliminated from O’(t). The algorithm repeats the process while the area limit is not reached. In UAV path planning context, the proposed algorithm solves two problems that occur with the application of various polygonal simplification methods. Results obtained from the application of the proposed algorithm and analyses of these results are described in this work.
Keywords:UAV path planning; visibility graph; reduced visibility graph; digital elevation model; polygonal simplification
Author: Felipe Leonardo Lôbo Medeiros


  1. A. Tsourdos, B. A. White, and M. Shanmugavel, Cooperative Path Planning of Unmanned Aerial Vehicles, 1st ed., Ed. West Sussex, United Kingdom: John Wiley & Sons Press, 2011.
  2. F. L. L. Medeiros and J. D. S. Silva, “Computational modeling for automatic path planning based on evaluations of the effects of impacts of UAVs on the ground,” Journal of Intelligent and Robotic Systems, vol. 61(1), pp. 181-202, Jan. 2011.
  3. B. Zhang, W. Liu, Z. Mao, J. Liu and L. Shen, “Cooperative and Geometric Learning Algorithm (CGLA) for path planning of UAVs with limited information,” Automatica, vol. 50(3), pp. 809-820, Mar. 2014.
  4. S. M. LaValle, “Rapidly-exploring random trees: a new tool for path planning,” Iowa State University, Ames, IA, Computer Science Department Tech. Rep. 98-11, pp. 4, 1998.
  5. J. J. Kuffner and S. M. LaValle, “RRT-connect: an efficient approach to single-query path planning,” in Proc. IEEE International Conference on Robotics and Automation, 2000, pp. 995-1001.
  6. S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning,” International Journal of Robotics Research, vol. 30(7), pp. 846-894, Jun. 2011.
  7. J. H. Holland, Adaptation in natural and artificial systems, 1st ed., Ed. Ann Arbor, USA: University of Michigan Press, 1975.
  8. E. W. Dijkstra, “A note on two problems in connection with graphs,” Numerische Mathematik, vol. 1(1), pp. 269-271, 1959.
  9. P. E. Hart, N. J. Nilsson and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE Transactions on Systems Science and Cybernetics, vol. 4(2), pp. 100-107, Jul. 1968.
  10. H. S. M. Coxeter, Regular polytopes, New York, USA: Dover Publications, 1973.
  11. N. J. Nilsson, “A mobile automaton: an application of artificial intelligence techniques,” in: Proc. ACM International Joint Conference on Artificial Intelligence, 1969, pp. 509-520.
  12. G. Voronoi, “Nouvelles applications des paramètres continus à la théorie dês formes quadratiques,” Journal für die Reine und Angewandte Mathematik, 134, pp. 198-287, Jan. 1908.
  13. J. C. Latombe, Robot Motion Planning, 1st ed., Ed. New York, USA: Kluwer Academic Publishers, 1991.
  14. C. Goerzen, Z. Kong and B. Mettler, “A survey of motion planning algorithms from the perspective of autonomous UAV guidance,” Journal of Intelligent and Robotic Systems, vol. 57(1), pp. 65-100, Jan. 2010.
  15. Y. Kuwata and J. P. How, “Stable trajectory design for highly constrained environments using receding horizon control,” in: Proc. IEEE American Control Conference, 2004, pp. 902-907.
  16. M. De Berg, M. Van Kreveld, M. Overmars and O. Schwarzkopf, Computational Geometry: Algorithms and Applications, 2nd ed., Ed. Berlin, Germany: Springer-Verlag, 2000.
  17. W. Eddy, “A new convex hull algorithm for planar sets,” ACM Transactions on Mathematical Software, vol. 3(4), pp. 398–403, Dec. 1977.
  18. M. I. Shamos, “Computational geometry,” Ph.D. thesis, Yale University, New Haven, USA, May 1978.
  19. R. L. Graham, “An efficient algorithm for determining the convex hull of a finite planar set,” Information Processing Letters, vol. 1(4), pp. 132-133, Jun. 1972.
  20. R. A. Jarvis, “On the identification of the convex hull of a finite set of points in the plane,” Information Processing Letters, vol. 2(1), pp. 18–21, Mar. 1973.
  21. W. R. Tobler, “An experiment in the computer generalization of maps,” Univ. of Michigan, Ann Arbor, MI, Office of Naval Research geography Branch Tech. Rep. 1, 1964.
  22. T. Lang, “Rules for robot draughtsmen,” The Geographical Magazine, vol. 42(1), pp. 50-51, 1969.
  23. U. Ramer, “An iterative procedure for the polygonal approximation of plane curves,” Computer Graphics and Image Processing, vol. 1(3), pp. 244-256, Nov. 1972.
  24. D. H. Douglas and T. K. Peucker, “Algorithms for the reduction of the number of points required to represent a line or its caricature,” The International Journal for Geographic Information and Geovisualization, vol. 10(2), pp. 112-122, Dec. 1973.
  25. K. Reumann, and A. P. M. Witkam, “Optimizing curve segmentation in computer graphics,” in: Proc. International Computing Symposium, 1973, pp. 467-472.
  26. H. Opheim, “Smoothing a digitized curve by data reduction methods,” in: Proc. Eurographics, 1981, pp. 127-135.
  27. M. Visvalingam and J. D. Whyatt, “Line generalization by repeated elimination of points,” Cartographic Journal, vol. 30(1), pp. 46-51, 1993.
  28. G. F. Jenks, “Lines, computers and human frailties,” Annals of the Association of American Geographers, vol. 71(1), pp. 1-10, Mar. 1981.
  29. Z. Zhao and A. Saalfeld, “Linear-time sleeve-fitting polyline simplification algorithms,” in: Proc. Auto-Carto XIII, 1997, pp. 214-223.
  30. T. Kanaya, Y. Teshima, K. Kobori and K. Nishio, “A topology-preserving polygonal simplification using vertex clustering,” in: Proc. 3rd International Conference on Computer Graphics and Interactive Techniques, 2005, pp. 117-120.
  31. Z. Tang, J. Zhu, F. He, L. Feng, G. Yang and G. Han, “Adaptive polygon simplification basing on Delaunay triangulation and its application in high speed PCBs and IC packages simulation,” in: Proc. IEEE International Conference on Microwave Technology & Computational Electromagnetics (ICMTCE), 2011, pp. 253-256.
  32. W. Park and K. Yu, “Hybrid line simplification for cartographic generalization,” Elsevier Pattern Recognition Letters, vol. 32(9), pp. 1267-1273, Jul. 2011.
  33. O. Aichholzer, T. Hackl, M. Korman, A. Pilz and B. Vogtenhuber, “Geodesic-preserving polygon simplification,” Algorithms and Computation, Lecture Notes in Computer Science, vol. 8283, pp 11-21, Sep. 2013.
  34. F. L. L. Medeiros and J. D. S. Silva, “A Dijkstra algorithm for fixed-wing UAV motion planning based on terrain elevation,” Lecture Notes in Computer Science, vol. 6404, pp. 213-222, Oct. 2010.
  35. E. P. Anderson, R. W. Beard and T. W. McLain, “Real-time dynamic trajectory smoothing for unmanned air vehicles,” IEEE Transactions on Control Systems Technology, vol.13(3), pp. 471–477, May. 2005.