Importing Data from Shapefiles and Pathfinding along Generated Nodes

Victor Brestoiu

Abstract


The Shapefile format is a particular standard for storing GIS (Geographic Information System) data, designed and developed by the Environmental Systems Research Institute (ESRI). The purpose of this project was to extract the binary data describing the City of Lethbridge from ESRI Shapefiles, and then to demonstrate an ability to utilize and modify this data. The utilization component centered on pathfinding and visually drawing the data, while the modification component involved the creation of a new, human-readable file type which contained the processed Shapefile data. These goals were accomplished by converting the Shapefile data into custom ‘Node’ objects in C++ code. These nodes form the basis for further development, as more attributes can easily be added to them as needed. The implemented pathfinding is a matter of picking a starting and ending node, and travelling across their adjacent nodes until a shortest path is found, a search algorithm called A* (read: A Star). Although further work is necessary for a robust product, this platform is already highly modular and is freely available open source.

Le format Shapefile est un standard particulier pour le stockage des données du système d’information géographique (SIG), conçu et développé par l’Institut de Recherche des Systèmes Environnementaux (ESRI). Le but de ce project était d’extraire les données binaires qui décrivent la ville the Lethbridge des Shapefiles ESRI, et de démontrer que ces données peuvent être utilisées et modifiées. Le composant d’utilisation était centré sur la navigation et la visualization des données, tandis que le composant de modification a demandé la création d’un nouveau format lisible aux humains qui contient les données Shapefile traitées. Ces buts ont été accomplies en convertissant l’information Shapefile en objets ‘nœud’ personnalisés dans le langage de programmation C++. Ces nœuds forment la base pour les développements plus approfondis, car plus d’attributs peuvent être facilement ajoutés aux nœuds lorsque nécessaire. Le système de navigation implémentée est alors une question de choisir un nœud de départ et de terminaison, puis voyager à travers leurs nœuds adjacents jusqu’à la découverte de la route la plus courte. Ce procès informatique est l’algorithme de recherche A* (lu : A Star). Quoi qu’encore plus de travail soient nécessaire pour le développement d’un produit able, cette plateforme est déjà très modulaire et disponible à l’open-source. 

 

Keywords


Transit; Optimization; C++; Node; Visualization

Full Text:

PDF

References


ESRI. ESRI Shape le Technical Description [PDF]. ESRI - White Paper. https://www.esri.com/ library/whitepapers/pdfs/shape le.pdf (accessed November 20, 2015).

Transportation Economics Committee. Transportation Bene t-Cost Analysis. Transportation Bene t-Cost Analysis, http://bca. transportationeconomics.org/ (accessed Nov 20, 2015).

Bulitko, V.; Björnsson, Y.; Sturtevant, N. R.; Lawrence, R. Real-Time Heuristic Search For Path nding in Video Games. Arti cial Intelligence for Computer Games. 2011, 1–30.

Buro, M.; Churchill, D. AI Magazine. September 22, 2012, pp. 1–3.

Bollob s Béla. Modern Graph Theory; Springer: New York, 1998.

Pohl, I. Heuristic Search Viewed as Path Finding in a Graph. Arti cial Intelligence. 1970, 1, 193–204.

Khantanapoka, K.; Chinnasarn, K. Path nding Of 2D & 3D Game Real-Time Strategy with Depth Direction A* Algorithm for Multi-Layer. 2009 Eighth International Symposium on Natural Language Processing. 2009.

Chiang, M. (2011). A* optimality proof, cycle checking. Vancouver: University of British Columbia.

Kahan, W. Lecture Notes on the Status of IEEE 754 1997.

Blum, C.; Li, X. Swarm Intelligence In Optimization. Natural Computing Series Swarm Intelligence. 2008, 43–85.




DOI: https://doi.org/10.13034/jsst.v10i1.126

Refbacks

  • There are currently no refbacks.


Copyright (c) 2017 Journal of Student Science and Technology