Documentacion

PROYECTO FIN DE CARRERA

DESARROLLO DE UN SISTEMAINTELIGENTE GPS-RASTER PARA

UNA PDA

AUTOR: Manuel Guillermo Lago Rodríguez

MADRID, Junio 2006

UNIVERSIDAD PONTIFICIA COMILLASESCUELA TÉCNICA SUPERIOR DE INGENIERÍA (ICAI)

INGENIERO EN INFORMÁTICA

Desarrollo de un Sistema Inteligente GPS-Raster para una PDA

Resumen

Este proyecto consiste en el desarrollo de una aplicación que sea capaz

de tomando un archivo de imagen cualquiera de un mapa de carreteras,

independientemente del formato de imagen de archivo y del modo en el que

estén representadas las vías de circulación en él, proporcionar servicios de

calculo de rutas e interacción con un dispositivo GPS al mismo nivel que daría

un mapa comercial especialmente desarrollado con este propósito. De este

modo, será una herramienta que podrá proveer a usuarios que quieran hacer

uso de sus sistemas de navegación en zonas que o bien no disponen de

mapas adecuados para sus necesidades o bien que directamente aún no han

sido mapeadas por las compañías que desarrollan este tipo de mapas.

Esta aplicación va a desarrollarse íntegramente sobre una plataforma

PDA, pues es en este tipo de plataforma donde se hace uso de los sistemas de

navegación GPS y donde la posibilidad de trazar una ruta sobre mapas de

carreteras puede ser realmente útil. La idea es permitir que el usuario solo

tenga que descargar la imagen a su PDA desde cualquier fuente, y tras un

pequeño proceso de análisis y pretratado sea capaz de emplear el mapa como

si hubiese sido especialmente desarrollado con ese propósito.

Para conseguir esto, es necesario que la aplicación sea capaz de ver las

vías de circulación contra el fondo, diferenciarlas de otros elementos similares

como ríos o líneas de coordenadas, analizar sus características para obtener

I


su trazado, su longitud e identificar el tipo de vía al que pertenece, para así

poder calcular tanto rutas mínimas como rutas óptimas de acuerdo con un

formato definido por el usuario.

Para poder analizar la imagen a nivel que eso requiere, a su vez, es

necesario que esta se encuentre en un formato vectorial que además sea

fácilmente legible por la aplicación. Por tanto, antes del análisis será necesario

realizar una transformación de la imagen a un formato vectorial que además

deberá ser abierto para poder acceder de modo directo a los datos del mapa de

carreteras

Como resultado del análisis realizado sobre la imagen vectorial, la

aplicación habrá reconocido los distintos tipos de carreteras presentes en el

mapa y tendrá todos los datos necesarios para calcular rutas sobre el mapa.

Para realizar el cálculo de rutas en sí, se creará un Grafo de Rutas que

recogerá todos los datos relativos al mapa de carreteras, sobre el que se

implantará un algoritmo de búsqueda heurística. Mediante estas dos

herramientas, la aplicación podrá calcular la ruta de mínimo recorrido entre dos

puntos cualesquiera que el usuario indique sobre mapa de carreteras.

La aplicación podrá interactuar con el dispositivo GPS integrado en la

PDA durante la realización de cualquiera de sus tareas. Así, podrá definirse el

punto de origen o destino como la localización actual del dispositivo GPS, y por

supuesto también indicar al usuario cual es su posición actual en el mapa.

II


Para poder interactuar con el GPS, el usuario podrá, con gesto tan

simple como indicar las coordenadas geográficas reales de tres puntos sobre la

superficie del mapa, definir completamente la colocación del mapa sobre la

superficie de la Tierra. La aplicación calculará desde esos tres puntos la

localización, orientación y escala del mapa.

Todos los datos relativos tanto al Grafo de Rutas como al

posicionamiento del mapa permanecerán guardados de modo que el mismo

mapa pueda ser empleado de nuevo sin necesidad de repetir el proceso de

generación del grafo y de posicionamiento del mapa.

III


Abstract

The purpose of this project is the development of an application capable

of taking an image file of a roadmap, independently of its file format and the way

the roads are represented within it, provide with route calculation and interaction

with a GPS device at the same level a commercial map especially prepared for

this purpose. This way, it will become a tool capable of providing users who

wish to make use of their navigation systems on areas that either do not have

maps adequated for their necessities or simply have not been maped yet by the

companies who make this kind of maps.

This application will be entirely developed on a PDA platform, as this kind

of platform is where the use of GPS navigation systems and the possibility of

determining over a roadmap may be truly useful. The idea is allow for the user

to only have to download the image on his PDA from any source, and after a

short process of analysis be capable of employing the map as if it had been

specially developed with this purpose.

In order to achieve this, is necessary for the application to distinguish the

roads form the background, difference then form similar elements like rivers or

coordinate lines, analyse their characteristics in order to obtain their path, length

and identify the kind of road it belongs to, and so be able of calculating minimal

routes as well as optimal routes according to a format defined by the user.

IV


In order to analyse the image to this level it is required for the image to

be in a vectorial format that is also easily readable by the application. As such,

before the analysis it will be needed to realize a conversion of the image into a

vectorial format that is also open in order to access directly to the roadmap

data.

As a result of the analysis conducted on the application will had

recognized the different kinds of roads present on the map and will have all the

data required to calculate routes on the map.

To realize the route calculation itself, a Route Graph containing all the

data relative to the roadmap will be created. On this graph an heuristic search

algorithm will be implemented. Using these two tools, it will be possible to

calculate the minimum longitude route between whichever two points indicated

by the user on the roadmap.

During the realization of its functionalities, the application will be capable

of interacting with the GPS device integrated on the PDA. This way, it will be

possible to define the starting and ending point as the current location of the

GPS device, and of course also indicate to the user its current location on the

roadmap.

In order to interact with the GPS, the user will be able to, with a gesture

as simple as indicating the geographic coordinates of three points on the map

surface, completely define the location of the map on Earth’s surface. The

V


application will calculate form this three points the location, orientation and

scale of the map.

All data related to both the Route Graph and the location of the map will

be stored so the same map may be used again without having to repeat the

graph generation and map location processes.

VI


La elaboración de este proyecto no

habría sido posible sin la inestimable ayuda de

José Ángel Olivas Varela y Miguel Ángel Sanz Bobi.

Muchas gracias familia, profesores y amigos por vuestro apoyo.

A todos vosotros os lo dedico.

VII


Índice

VIII


Capitulo 1 - Introducción y Planteamiento 1

1.1. Necesidad del Proyecto 3

Capitulo 2. Objetivos 5

Capitulo 3 - Requisitos de la aplicación 8

Capitulo 4 - Estado del Arte 10

4.1. GPS (Global Positioning System) 11

4.2. Modelo Geográfico 15

4.2.1. La Tierra 15

4.2.2. Meridianos y Paralelos 15

4.3. Proyección Mercator 18

4.4. Búsqueda Heurística 20

4.4.1. Algoritmo A* 22

4.4.2. Funcionamiento de A* 25

4.5. Tecnologías 34

4.5.1. PDA (Personal Digital Assistant) 34

4.5.2. SVG (Scalable Vector Graphics) 36

4.5.3. AutoTrace 38

4.5.4. BMP 40

IX


4.5.5. XML (Extensible Markup Language) 41

4.5.6. Microsoft Visual Studio .NET 43

4.5.7. C# 44

Capitulo 5 - Desarrollo del Sistema GPS 45

5.1. Decisiones de Diseño 46

5.2. Diseño de la Aplicación 49

5.2.1. División en módulos 50

5.2.2. DFD Módulo Vectorizador 51

5.2.3. DFD Módulo Enrutador 52

5.2.4. DS Proceso de Vectorización 53

5.3. Grafo de Rutas 54

5. 4. Módulo Vectorizador 57

5.4.1. Tratamiento de la imagen 59

5.4.1.1. Identificación de carreteras 59

5.4.1.2. Tratamiento en fases de la imagen 60

5.4.1.2.1 Pretratado 61

5.4.1.2.2. Vectorización Mediante Autotrace 62

5.4.1.2.3. Digitalización 67

5.4.1.2.4. Abstracción del Mapa a Grafo 68

X


5.4.1.2.5. Refinado 68

Aproximación de nodos 69

Conexión de nodos 71

Eliminación de Elementos Redundantes 73

Parámetros de Refinado 75

5.4.2. Editor de Grafo 78

5.4.3. Generación del documento XML 83

5.5. Módulo Enrutador 84

5.5.1. Lectura del fichero XML 84

5.5.2. Calculo de Rutas Mínimas 85

Representación de la ruta calculada 86

5.5.3. Posicionamiento 88

5.5.3.1. Localización 89

5.5.3.2. Orientación 90

5.5.3.3. Escala 92

5.5.3.4 Empleo de un Modelo de Tierra Plana 93

5.5.3.4.1. Dos puntos frente a tres puntos 94

5.5.3.4.2. Parámetros de conversión 95

Grado de Longitud 95

XI


Ratio de Kilómetros a Píxeles 97

Matriz de Conversión de Coordenadas 97

5.5.4. Conversión de coordenadas 99

5.5.4.1. Aplanamiento de la Tierra 99

5.5.4.2. Cambio de Escala 101

5.5.4.3. Cambio de Ejes Coordenados 101

5.5.5. Fallo a Mayor escala 103

Imprecisión propia del mapa 109

5.6. Limitaciones de la aplicación 111

5.6.1. Generación del Grafo de Rutas 111

5.6.1.1. Influencia del formato 111

5.6.1.2. Abstracción al grafo 113

Elementos que no son carreteras 113

Perdida de carreteras 114

Cúmulos de Nodos 115

Fallo de Conexión 116

5.6.1.3. Refinado 118

5.6.2. Uso de la proyección Mercator 121

5.6.2.1. Imprecisión por deformación 121

XII


5.6.2.2. Mapas inutilizables 123

Capitulo 6 - Evaluación del proyecto 128

6.1. Generación del Grafo de Rutas 129

6.2. Calcular Ruta de Mínimo Recorrido 132

6.3. Posicionamiento y Conversión de Coordenadas 134

Capitulo 7 - Conclusiones 136

7. 1. Cumplimiento de los Objetivos 141

7.2. Cumplimiento de los Requisitos 146

Capitulo 8 - Planificación y Presupuesto 149

8.1. Planificación del Proyecto 150

8.2. Presupuesto del Proyecto 152

Capitulo 9 - Bibliografía 154

Apéndice - Uso de la aplicación 156

A.1. Módulo de Vectorización 157

A1.2. Módulo Enrutador 171

XIII


Capitulo 1 - Introducción y Planteamiento

1


El propósito de este proyecto es el desarrollo de un sistema, orientado a

su implantación en un formato PDA, que, tomando un mapa en un formato de

imagen simple, como un mapa de bits, se capaz de convertirlo en un mapa

que pueda ser directamente empleado por un dispositivo GPS. Con este mapa,

se podrán determinar rutas, distancias y tiempos entre puntos mediante

técnicas de búsqueda heurística. Para realizar el proceso de conversión del

mapa, el sistema lo convertirá a un formato vectorial para poder tratar sus

características directamente y determinará su escala y su posición global

mediante la definición de varios puntos de referencia.

2


1.1. Necesidad del Proyecto

Los sistemas de navegación GPS actuales requieren para su

funcionamiento el uso de mapas especialmente desarrollados para este

propósito, que además sean compatibles con el sistema de ubicación

geográfica del propio del GPS. Este hecho conlleva múltiples limitaciones en el

uso de estos dispositivos. Estos mapas frecuentemente pueden no cubrir las

necesidades de un usuario en un momento determinado, ya sea porque no

abarcan con suficiente precisión el área que interesa al usuario, porque no

están adecuadamente actualizados o sencillamente porque no existe ningún

mapa de esa área. En ocasiones el usuario ni siquiera tendrá la posibilidad de

adquirir el mapa que necesita al no tener acceso al sistema de distribución que

la compañía desarrolladora emplee.

Sin embargo, es prácticamente seguro que el usuario podrá tener a su

alcance un mapa normal (es decir, no preparado para su uso por un dispositivo

GPS) que satisfaga sus necesidades en un mayor grado, pero se verá obligado

adquirir un mapa especialmente desarrollado para su uso por su sistema GPS,

que además de sufrir los problemas anteriormente mencionados será

redundante con el que ya tenía.

Aunque actualmente la cobertura proporcionada por el sistema GPS es

global, significando que en cualquier punto del planeta es posible emplear un

dispositivo GPS para calcular las coordenadas de una posición, para poder

3


trazar itinerarios sobre un mapa y calcular rutas mínimas es necesario que el

mapa disponga de una inteligencia adicional. Esta inteligencia está contenida

en una base de datos adjunta al mapa que reúne todos los datos necesarios

para que el mapa conozca donde se encuentran las vías de circulación, y

conozca sus características físicas como su trazado, las conexiones que tenga

con otras carreteras y su longitud.

Tradicionalmente crear estos mapas preparados para GPS requiere

trazar manualmente las vías sobre el mapa para que sus características sean

comprendidas por el sistema. Este por lo general es un proceso

considerablemente lento y caro, e implica que ninguna de las compañías

dedicadas a esta tarea va a trazar mapas a los que no crea vaya a dar salida.

El resultado es que la mayor parte del mundo no dispone de mapas preparado

para el uso de sistemas de autorouting que represente sus vías con suficiente

precisión, completitud y actualidad.

Resolver este problema es el principal propósito de este proyecto. El

usuario debe ser capaz de poder aprovechar su dispositivo GPS con cualquier

mapa que ya posea, a pesar de que no haya sido especialmente desarrollado

para ello, y además de poder añadir un nuevo mapa a su navegador en

cualquier momento según aparezca la necesidad, y de poder utilizar estos

mapas como si hubieran sido preparados para la navegación GPS.

4


Capitulo 2. Objetivos

5


La aplicación podrá tomar un archivo de imagen en cualquier formato y

será capaz de crear un Grafo de Rutas a partir únicamente de la imagen, de

modo que en él se detallen las distancias, trazado de la vía y rutas entre los

puntos significativos del mapa, y las coordenadas geográficas de esos puntos.

El proceso de vectorización de la imagen deberá ser capaz de

diferenciar los tipos de vía presentes en el mapa. Así mismo, deberá diferenciar

estas de otros elementos del mapa que puedan causar confusión, como ríos y

otros elementos geográficos.

El usuario podrá posicionar el mapa en el sistema de coordenadas de

latitud y longitud utilizado por el GPS simplemente definiendo las coordenadas

de varios puntos en el mapa. A partir de esto, el dispositivo calculará todos los

parámetros que pueda necesitar para realizar un cambio de coordenadas entre

los sistemas empleados por la aplicación, y a partir de esos datos, calcular la

localización del mapa, su orientación y su escala. Conociendo esto, podrá

calcular la longitud de los tramos de vías de circulación, de las rutas calculadas

por el sistema y las coordenadas actuales del usuario sobre el mapa. Este

proceso solo necesitará ser realizado una vez, y el mapa recordara los

resultados para futuras ejecuciones.

El sistema podrá asignar pesos a los tipos de vía presentes en el mapa

identificados durante el análisis del mapa, de modo que favorezca algunos,

como las autopistas, sobre otros al calcular el recorrido óptimo. El usuario

6


podrá definir estos pesos a voluntad, o utilizar algún esquema de pesos

predeterminado.

Partiendo de estos datos, el sistema podrá calcular la ruta de mínima

distancia entre dos puntos cualesquiera del mapa, no solo los definidos como

puntos significativos durante el proceso de análisis, y a continuación podrá

mostrar esta ruta directamente sobre el mapa, e indicara al usuario su longitud

total.

7


Capitulo 3 - Requisitos de la aplicación

8


El sistema deberá estar implantado completamente sobre una

plataforma Pocket PC, y ser capaz de interactuar con el receptor GPS de ésta

durante la realización de sus funcionalidades. Esto se requiere para así poder

dar al usuario la capacidad de trabajar de modo inmediato con cualquier mapa

de carretera que se introduzca a la aplicación.

La herramienta deberá estar orientada a un usuario al que no se le

supone ningún conocimiento sobre informática, funcionamiento de dispositivos

GPS, sistemas de navegación o tratamiento de imagen. Por ello, su interfaz

deberá ser intuitiva, sencilla y autoexplicativa, y el uso de la aplicación deberá

ser extremadamente sencillo, manteniendo todos los procesos de tratamiento

de la imagen y de interacción con el dispositivo GPS transparentes al usuario.

9


Capitulo 4 - Estado del Arte

10


4.1. GPS (Global Positioning System)

El Sistema de Posicionamiento Global, más conocido como GPS (Global

Positioning System) es el único sistema de navegación por satélite que

actualmente proporciona una cobertura completa a nivel global. Dispone de

una constelación en la que siempre hay al menos 24 satélites activos, que

transmiten señales de radio precisamente temporizadas que permiten a los

receptores GPS calcular con exactitud su latitud, longitud y altitud. Mediante

estos datos los dispositivos receptores actuales también son capaces de

calcular su velocidad y orientación. En todo momento, en cualquier punto de la

superficie de la Tierra, sea de día o de noche y bajo cualquier clima, un

dispositivo GPS es capaz de ver al menos los cuatro satélites que necesita

para hacer ese cálculo y conocer tanto la distancia que los separa de ellos

como su posición orbital actual. De este modo, obtiene el radio (la distancia al

satélite) y el centro (la posición orbital del satélite) de cuatro esferas cuyo punto

de intersección es precisamente la localización actual, definida por su latitud,

longitud y altitud del punto actual.

Puede parecer lógico que se requiriera únicamente tres satélites, puesto

que el propósito del GPS es determinar la posición del dispositivo en un

sistema tridimensional, que únicamente requeriría de tres esferas para ser

definido. La cuarta esfera es necesaria para introducir la variable tiempo en el

sistema. El retardo de las señales de los satélites puede variar enormemente

11


por el estado de las capas elevadas de la atmósfera, por las condiciones

climáticas y por la altura de los satélites sobre el horizonte. El cuarto satélite

permite determinar el retardo de las señales recibidas por cada satélite de

forma lo suficientemente exacta como para permitir que el dispositivo pueda

calcular su posición de modo fiable.

La medición exacta del tiempo es una característica fundamental en el

funcionamiento de los satélites GPS, puesto que las distancias a los satélites

que se utilizan se calculan como el tiempo que ha tardado en recorrerlas una

onda de radio, que viaja a la velocidad de la luz. Eso significa que un reloj que

calculara el tiempo con precisión de milésimas de segundo, fallaría en su

estimación por 300 km. Por ello, los satélites utilizan relojes atómicos de

extrema precisión. Es interesante notar que debido a que los relojes de los

satélites están sometidos tanto a la relatividad general como a la espacial, el

tiempo avanza ligeramente más rápido en ellos que en la Tierra.

Concretamente, los relojes de los satélites van aproximadamente 38

microsegundos al día más rápido que los relojes en la Tierra. Pero si los

dispositivos de recepción tuvieran relojes de ese nivel, costarían millones de

euros y nadie podría acceder a ellos. Para reparar la imprecisión producida por

el más limitado reloj del receptor es para lo que existe la señal del cuarto

satélite.

Recientemente, los campos en los que se aplican los dispositivos GPS

han dejado de estar limitados a su uso por parte de fuerzas militares, tareas de

12


salvamento y navegación profesional. Tras su introducción en dispositivos

portátiles de navegación disponibles al público general, aparecieron programas

de creación de itinerarios que eran capaces de generar rutas mínimas sobre un

PC que podían a continuación ser importadas a un dispositivo GPS. Debido al

éxito de este planteamiento, poco después empezaron a aparecer coches

equipados de serie con sistemas de navegación GPS integrados, y programas

de cálculo de rutas que funcionaban en tiempo real directamente sobre los

dispositivos de navegación GPS, el denominado autorouting.

El empleo de autorouting por parte de los dispositivos GPS requiere de

una completa base de datos de las vías de circulación de la zona recorrida

aparte del mapa de carreteras en sí. Esta base de datos debe incluir el trazado

de las carreteras, su longitud, sus conexiones con otras carreteras, etcétera.

Debido a estos requisitos, que hacen del proceso de creación de mapas de

preparados para autorouting un proceso lento y costoso, y del hecho de que la

tecnología es aún considerablemente nueva, las áreas del mundo que

disponen actualmente de mapas de carreteras con estas características, con

una base de datos como la descrita adjunta y con un mínimo de fidelidad a la

realidad y de exactitud se limitan a Estados Unidos, Canadá, Europa

Occidental y Australia. No es de sorprender, por tanto, la aparición de múltiples

comunidades de usuarios de GPS en otros países que se han dedicado a crear

sus propios mapas de navegación en su tiempo libre. Desgraciadamente, estos

grupos de usuarios están considerablemente limitados de modo evidente al no

disponer de los recursos a los que tiene acceso una compañía profesional.

13


Esto hace que la cobertura proporcionada en otros países por mapas creados

por estas comunidades sea bastante limitada.

14


4.2. Modelo Geográfico.

4.2.1. La Tierra

La Tierra como planeta no es una esfera perfecta, sino un esferoide

ligeramente achatado en los polos. Así, su radio mayor, en el ecuador es

6378.137 km, y en los polos de 6356,752 km. Para este proyecto se ha

considerado, no obstante, a la tierra como una esfera perfecta de radio

constante 6372 km puesto que la deformación producida por esta aproximación

es despreciable.

4.2.2. Meridianos y Paralelos

Las coordenadas geográficas que tradicionalmente se utilizan en la

navegación para determinar puntos sobre la superficie terrestre, y que también

son las utilizadas por los dispositivos GPS se denominan Latitud y Longitud.

La latitud es el ángulo que la recta que une el punto observado y el

centro de la tierra mantiene con el plano ecuatorial. Tradicionalmente se le da a

la latitud de los puntos situados en el Hemisferio Norte un valor positivo y a los

situados en el Hemisferio Sur un valor negativo. De este modo, la latitud varía

desde 90º en el Polo Norte, a 0º en cualquier punto situado en el Ecuador, a

-90º en el Polo Sur. Siguiendo este convenio, latitud aumenta conforme se

avanza hacia el Norte y se reduce conforme se avanza hacia el Sur. Este

15


convenio se ha introducido en el proyecto puesto que simplifica

considerablemente el funcionamiento matemático de la aplicación.

La longitud es el ángulo que la recta perpendicular al eje de rotación de

la Tierra que pasa por el punto observado mantiene con el semiplano definido

por el eje de rotación de la Tierra y por la localización del antiguo observatorio

astronómico ubicado en Greenwich, uno de los barrios de Londres. De modo

similar a la latitud, existe un convenio que define la longitud en puntos situados

al Este de este punto, también denominados conjuntamente como Hemisferio

Este, como positiva, mientras que los puntos situados al Oeste del semiplano, o

Hemisferio Oeste, como negativos. Siguiendo este convenio, la longitud varía

desde -180º, para los puntos situados en el semiplano opuesto a Greenwich, 0º

en el propio semiplano y +180º en el mismo punto en el que se empezó. Este

convenio también se ha adoptado en el proyecto, por razones análogas a las

del caso de la latitud.

Un paralelo es una línea ficticia trazada sobre la superficie de la Tierra

por la intersección de un plano perpendicular al eje de rotación con la Tierra.

En un paralelo, la latitud se mantiene constante, y sobre él se mide la longitud.

La longitud de la circunferencia definida por un paralelo varía desde 40075 km

en el Ecuador hasta 0 km en los polos. Por esto, la longitud de los grados de

longitud varía conforme la latitud del punto observado.

Un meridiano es una línea ficticia trazada sobre la superficie de la Tierra

por la intersección de un semiplano que parta del eje de rotación de la Tierra y

16


la superficie de la Tierra. Como tal, es una semicircunferencia. En un

meridiano, la longitud se mantiene constante y sobre él se puede medir la

latitud. Un antimeridiano es el meridiano situado en el punto opuesto del

planeta y que cierra la circunferencia definida por un meridiano. Puesto que la

longitud de la semicircunferencia definida por un meridiano es constante

independientemente de la longitud, la longitud de los grados de latitud es

constante. No obstante, no hay que olvidar que esto es solo porque se está

trabajando sobre una representación teórica de la Tierra como una esfera

perfecta. En realidad, al ser un esferoide, la longitud de los grados de latitud

varía según la latitud desde 110,57 en el Ecuador hasta 111,70 a la altura de

los polos. Es interesante notar que aún tomando la Tierra como un esferoide, la

longitud de los grados de latitud sigue siendo independiente de la longitud a la

que se encuentre el punto observado.

17


4.3. Proyección Mercator

Debido al hecho de que la Tierra es una esfera, es imposible representar

su superficie sobre un plano de forma fidedigna. A lo largo de la historia han

surgido múltiples sistemas de proyección para representar tratar de representar

la Tierra sobre un plano de un modo útil. La proyección Mercator es un sistema

de proyección cartográfico ideado en 1569 por el cartógrafo holandés Gerardus

Mercator.

En este sistema de proyección se emplea como superficie de proyección

un cilindro cuyo eje central es coincidente con el eje de rotación de la Tierra.

Los sistemas de proyección cilíndrica inevitablemente introducen una

deformación en dirección Este-Oeste alejándose del Ecuador en un ratio cuyo

valor es la secante de la latitud con respecto a la escala en el Ecuador. La

característica que diferencia a la proyección Mercator de otros sistemas de

proyección cilíndrica como el de Miller o el de plate careé es la introducción de

una deformación en la misma proporción en sentido Norte-Sur. El resultado que

hacer esto conlleva es que las distancias que separan los paralelos y los

meridianos se mantienen constantes en el mapa. Además, los ángulos

representados sobre el mapa son iguales que los presentes en la superficie de

la Tierra. Como resultado de esto, las líneas de orientación constante, es decir,

las líneas que avanzan sin cambiar de rumbo moviéndose por la superficie de

la Tierra son igualmente rectas sobre el mapa, independientemente de la

18


longitud o latitud a la que se encuentre el punto observado. Este es el motivo

por el cuál pese a que proyección Mercator, con más de 400 años de

antigüedad, y que exagera de modo descomunal las áreas de las regiones

situadas a elevadas latitudes sigue siendo una de las proyecciones más

empleadas hoy en día.

No obstante, la proyección Mercator no ha sido seleccionada como

proyección para la representación del modelo de Tierra desarrollado en el

proyecto por estos motivos sino por su extrema simplicidad de cálculo. Puesto

que se espera que a la escala a la que se vaya a emplear el mapa la curvatura

de la Tierra sea poco apreciable, la deformación que las diferentes

proyecciones introducen pasa a un segundo plano, siendo el principal motivo

para la selección de un sistema de proyección su sencillez desde un punto de

vista matemático. Por esto es por lo que se ha seleccionado la proyección

Mercator para realizar las conversiones de coordenadas.

19


4.4. Búsqueda Heurística

El razonamiento puede entenderse como la búsqueda de una solución

en una base de conocimientos. Según esta filosofía existen varios algoritmos

de inteligencia artificial cuyo funcionamiento se basa en la búsqueda de la

solución óptima a través de una estructura como un grafo o un árbol generados

a partir de la base de conocimiento. Estos algoritmos se denominan algoritmos

de búsqueda heurística.

La búsqueda de soluciones óptimas a través de grafos no se limita al

campo de la inteligencia artificial, sino que es un problema clásico para el que

se han desarrollado multitud de algoritmos de búsqueda, muchos de los cuales

no tienen ningún tipo de inteligencia. Los algoritmos de búsqueda heurística se

diferencian de estos en el empleo de una cierta cantidad de conocimiento

durante el proceso de búsqueda. Este conocimiento ayuda al algoritmo a

escoger un camino hacia la solución, aunque puede que el camino no lleve a la

solución óptima. Al emplear un algoritmo de búsqueda heurística se está

sacrificando la exahustividad propia de un algoritmo de búsqueda por fuerza

bruta a cambio de obtener una solución para un problema de forma más

eficiente que con los algoritmos tradicionales.

En el caso de este problema, se ha recurrido al uso de un algoritmo de

búsqueda heurística debido a que la base de conocimiento sobre la que se está

trabajando, que no es otra que el propio mapa de carreteras que se está

20


analizando, ya tiene una estructura propia de un grafo; Es decir, se compone

de una serie de puntos significativos, como cruces, ciudades, etcétera, que

están conectados entre sí por una serie de caminos, las vías de circulación,

definidos por unos ciertos pesos, sus longitudes en kilómetros.

El problema a resolver también es de los clásicos que se suele resolver

mediante algoritmos de búsqueda, tanto en el caso de los normales como en el

de los algoritmos de búsqueda heurística: La búsqueda del camino de mínimo

peso entre dos puntos definidos de un grafo, desde el punto donde se inicia la

búsqueda hasta un punto meta donde concluye la búsqueda. En el caso de un

grafo generado a partir de un mapa de carreteras, encontrar el camino de

mínimo peso supone encontrar la ruta de mínimo recorrido a través del mapa

de carreteras representado por el grafo.

21


4.4.1. Algoritmo A*

De entre los diferentes algoritmos de búsqueda heurística existentes, se

ha seleccionado para el cálculo de la ruta de mínimo recorrido el algoritmo de

búsqueda heurística A* para el cálculo de la ruta de mínimo recorrido sobre el

grafo generado a partir del mapa de carreteras.

Entre los diferentes algoritmos de búsqueda existen dos métodos

básicos para encontrar la solución óptima. La búsqueda en profundidad explora

una rama del árbol de soluciones, o un posible camino desde el punto de vista

del grafo, hasta que encuentra la solución o llega al final. Emplear un algoritmo

basados en profundidad aseguraría llegar hasta el destino, pero no el que se

hiciera por el camino más corto. La búsqueda en anchura expande todos los

nodos desde el origen, hasta que de estos resulta en el nodo solución. La

búsqueda en anchura asegura encontrar el camino con menos saltos hasta el

destino, pero este no tiene porque ser el óptimo. Además, su complejidad y

tiempo de ejecución son exponenciales respecto al número de nodos del grafo.

Con la complejidad que se espera tenga el grafo generado por encontrar la

solución óptima, este método se vuelve del todo inaplicable.

Para el cálculo de las rutas mínimas, el programa no va a hacer uso de

ninguno de estos dos métodos elementales. El algoritmo que se empleará es

un método de búsqueda del primer mejor. Éste tipo de algoritmos combina las

ventajas de los algoritmos basados en profundidad y en anchura siguiendo un

22


único camino, pero cambiando de ruta en cualquier momento, cuando aparezca

una ruta alternativa que resulte más prometedora que la actual. Para decidir si

se va a cambiar de ruta, estos algoritmos hacen uso de un cierto conocimiento,

con lo que añaden una inteligencia al proceso de búsqueda, lo que los hace

algoritmos de búsqueda heurística.

Más exactamente, se va a emplear uno de los algoritmos denominados

Branch-and-Bound, un perfeccionamiento de los algoritmos de Búsqueda del

Primer Mejor que añaden a los cálculos para la decisión del camino hacia el

destino el coste acumulado de lo recorrido hasta el momento. Como resultado,

no sólo localizan la solución, sino que además lo hacen a través del camino

óptimo hacia ella. Puesto que el propósito para el que se están usando estos

algoritmos es precisamente el de localizar el camino de mínimo peso, es decir,

recorrido, hasta el nodo destino, este tipo de algoritmos resulta perfecto para la

tarea.

El algoritmo A* es uno de los algoritmos de Branch-and-Bound. Este

algoritmo mejora el modelo básico Brach-and-Bound incorporando una función

de mérito que se calcula como la combinación del coste incurrido hasta el nodo

actual más una función de estimación heurística que predice cual es el coste

desde los diferentes nodos vecinos hacia la meta. Esta función de mérito se

emplea para decidir hacia que nodo vecino se va a expandir la ruta a

continuación, lo que implica incurrir en un coste operacional superior pero al

mismo tiempo permite encaminar la búsqueda directamente en la dirección de

23


la meta optima. Esta función de estimación heurística introduce una cierta

cantidad de inteligencia y conocimiento en el propio algoritmo de selección de

caminos. El nivel en el que la solución calculada por el algoritmo será óptima y

el tiempo que se tardará en alcanzarla dependen directamente de la calidad de

la función heurística, por tanto su selección es un punto fundamental en el

desarrollo del algoritmo.

En este proyecto se ha implementado como función de estimación

heurística la distancia en línea recta que separa el nodo que esta siendo

evaluado para expandir la ruta en su dirección y el nodo destino. En lo que esto

resulta es que el algoritmo considera que, en una situación en la que los

caminos hacia los nodos sean equivalentes, el sistema va a optar por el nodo

vecino más cercano al destino. En otras palabras, el algoritmo actúa llevado

por el conocimiento de que avanzando en la dirección en la que se encuentra el

destino es como más probablemente vaya a encontrar la ruta de longitud

mínima. Esto no debe llevar a pensar que en caso de que alcanzar el destino

requiera en algún momento alejarse de él o en él que el camino más directo no

sea el más corto el algoritmo se va a ver visto en problemas. Sin duda tardará

más al tener que probar antes los caminos que van hacia el destino, pero

seguirá obteniendo la ruta óptima. En la mayoría de los casos, no obstante,

especialmente en los que pueden presentarse en el trazado de rutas sobre

mapas concerniente a este sistema, seguirá siendo más rápido que cualquiera

de los otros algoritmos de búsqueda heurística. Por esta superioridad en la

aplicación a este campo, y puesto que la función de búsqueda que se ha

24


empleado es directamente deducible, y fácil de implementar y calcular, es por

lo que se ha decidido emplear este algoritmo para el cálculo de las rutas

mínimas.

4.4.2. Funcionamiento de A*

Tomando como ejemplo de Grafo de Rutas este mapa de Rumania:

25


En el que la distancia en línea recta desde cada una de las ciudades

(nodos) representadas en el mapa hasta Bucarest (nodo destino) es:

Arad 366 Mehadia 241Bucarest 0 Neamt 234Craiovra 160 Oradea 380Dobreta 242 Pitesti 100Efoire 161 Rimnicu Vilcea 193Fagaras 176 Sibiu 253Giurgiu 77 Timisoara 329Hirsova 151 Urziceni 80Iasi 226 Vaslui 199Lugoj 244 Zerind 374

Se va a emplear el algoritmo A* con la misma implantación que se

emplea en el cálculo de rutas mínimas en la aplicación, empleando la misma

función heurística, para calcular la ruta de mínimo recorrido entre Arad y

Bucarest

26


En Arad, la función de evaluación, calculada como suma entre el peso

de la ruta acumulada hasta este momento y el valor de la función de evaluación

en ese punto tiene el valor de:

Arad: 366 = 366+0

Tras la expansión de Arad, los valores de las funciones de evaluación

pasan de cada uno de sus vecinos hacia los que se expande son:

Sibiu: 393 = 140+253

Timisoara: 447 = 118+329

Zerind: 449 = 75+374

27


De las diferentes rutas disponibles, avanzar hacia Sibiu es la que tiene el

mínimo valor en su función de evaluación. Por tanto, se expande la ruta en esa

dirección.

28


Ahora se expande el nodo de Sibiu, y se calculan las funciones de

evaluación respectivas. Las rutas que se pueden expandir desde Sibiu no solo

se comparan entre sí, sino también con las que antes se calcularon desde Arad

Timisoara: 447 = 118+329

Zerind: 449 = 75+374

Arad: 646 = 280+366

Fagaras: 415 = 239+176

Oradea: 671 = 291+380

Rimnicu Vilcea: 413 = 220+193

Esta vez, la dirección de expansión seleccionada es Rimnicu Vilcea

29


Expandiendo Rimnicu Vilcea:

Timisoara: 447 = 118+329

Zerind: 449 = 75+374

Arad: 646 = 280+366

Fagaras: 415 = 239+176

Oradea: 671 = 291+380

Craiova: 526 = 366+160

Pitesti: 417=317+100

Sibiu: 553 = 300+253

En este caso, la ruta no se expande en ninguna de las direcciones que

han surgido de expandir Rimnicu Vilcea, sino que el algoritmo da “un paso

atrás” y selecciona la ruta que llevaba a Fagaras para su expansión

30


Expandiendo Fagaras:

Timisoara: 447 = 118+329

Zerind: 449 = 75+374

Arad: 646 = 280+366

Oradea: 671 = 291+380

Craiova: 526 = 366+160

Pitesti: 417=317+100

Sibiu: 553 = 300+253

Bucarest: 450 = 450+0

Sibiu: 591 = 338+253

En esta tanda de expansión de rutas, se producen dos eventos

destacables. Primero, Sibiu aparece otra vez. Esta segunda aparición se debe

a en este momento se han descubierto dos rutas distintas, y ambas llevan a

Sibiu desde Arad, siguiendo diferentes caminos de diferentes longitudes. El

segundo evento es que Bucarest, el destino, aparece entre los posibles

destinos de la expansión. No obstante, el valor que lleva hasta ella no es el

mínimo, y por tanto no se expande la ruta en esa dirección. En su lugar la ruta

se expande hacia Pitesti. Existe la posibilidad de que a través de Pitesti se

encuentre un camino hacia Bucarest que sea más corto.

31


Tras la expansión de Pitesti:

Timisoara: 447 = 118+329

Zerind: 449 = 75+374

Arad: 646 = 280+366

Fagaras: 415 = 239+176

Oradea: 671 = 291+380

Craiova: 526 = 366+160

Sibiu: 553 = 300+253

Bucarest: 450 = 450+0

Sibiu: 591 = 338+253

Bucarest: 418 = 418+0

Craiova: 615 = 455+160

Rimnicu Vilcea: 607 = 414+193

32


Nuevamente aparece una ruta hacia Bucarest entre las posibles. Su

función de evaluación es en efecto menor que la que se había calculado antes,

de hecho es la menor de todas las que se habían calculado. Eso significa que

la ruta se expande en esa dirección y que se ha llegado al destino. Por tanto, el

algoritmo se detiene y la ruta mínima queda como:

33


4.5. Tecnologías

4.5.1. PDA (Personal Digital Assistant)

Las PDA (Personal Digital Assistant) han evolucionado desde su origen

como simples organizadores electrónicos a dispositivos extremadamente

completos, que pueden perfectamente describirse como ordenadores de

bolsillo. Actualmente, el rango de funciones que es habitual encontrar en una

PDA engloba una agenda, organizador, calculadora, acceso a Internet

mediante wireless, sincronización con una base de datos, grabación de sonido,

y envió de mensajes a móviles. Es así mismo cada vez más frecuente la

inclusión de dispositivos receptores GPS, lo cual les ha otorgado todo un nuevo

rango de funcionalidades, incluyendo localización global, navegación GPS y

uso de sistemas de autorouting.

Como ya se ha mencionado, el propósito del proyecto desarrollar una

aplicación que sea capaz de funcionar sobre una plataforma PDA típica con

capacidades GPS. Entre las diferentes arquitecturas de PDA existentes en el

mercado se ha seleccionado para este desarrollo la plataforma de Microsoft

Pocket PC. Esto es debido a que es posiblemente la plataforma PDA

actualmente más extendida, gracias especialmente al uso de Windows Mobile

como su sistema operativo. Windows Mobile fue desarrollado por Microsoft a

partir de Windows CE, el sistema operativo Windows para microordenadores y

sistemas integrados. Windows CE no es una versión recortada del Windows de

34


escritorio sino que emplea un kernel propio. El emplear Windows Mobile provee

al Pocket PC de múltiples funciones de interacción con los sistemas Windows

de escritorio y con otras herramientas de Microsoft como Outlook y el paquete

Office.

Entre las diferentes versiones de Pocket PC se ha empleado para el

desarrollo de la aplicación Pocket PC 2002, aunque esto es únicamente a su

compatibilidad con las herramientas de desarrollo que se han utilizado en el

proyecto. La aplicación a desarrollar es compatible con cualquier versión de la

plataforma Pocket PC, y puede ser portada a cualquiera de las otras versiones

de la plataforma de modo inmediato.

35


4.5.2. SVG (Scalable Vector Graphics)

Para poder ejecutar un análisis y tratamiento de imagen al nivel que el

sistema desarrollado requiere para la realización de sus funciones, es

necesario estar trabajando con una representación vectorial de la imagen

analizada.

Las imágenes representadas en un formato digital pueden estar en dos

formatos básicos, de los cuales derivan todos los demás formatos existentes.

Los formatos ráster, guardan la imagen como una superficie de píxeles,

almacenando el color y la posición de cada píxel de la imagen. Esto produce

una fidelidad perfecta con la imagen original, pero resulta en archivos de gran

tamaño. Además, debido a la falta de “inteligencia” del archivo, es imposible

extraer datos de los que representa por programas de análisis de imagen sin

emplear un gran número de cálculos.

El formato vectorial, por otra parte, guarda datos que describen lo que la

imagen representa. Es decir, almacena las coordenadas, ángulos, dimensiones

y colores de los elementos representados en la imagen. Esto puede lleva a una

perdida de características particularmente complejas de la imagen, pero resulta

mucho más manejable desde un punto de vista computacional. Así, los gráficos

vectoriales se emplean para convertir diseños gráficos a programas de CAD, o

reconocimiento de texto en imágenes. El sistema que se está desarrollando

36


también se ve beneficiado por las posibilidades de análisis directo de la imagen

que proporciona el formato vectorial.

De entre el gran rango de formatos vectoriales existentes se ha

seleccionado para el desarrollo del proyecto el estándar SVG (Scalable Vector

Graphics). SVG es un estándar desarrollado por el World Wide Web

Consortium, responsable de algunos de los más importantes estándares del

mundo de la informática, incluyendo HTML y XML.

El principal motivo de la selección de SVG como formato de imagen

vectorial del proyecto es el hecho de que, internamente, es en realidad un

documento XML con un cierto formato. Esto permite al sistema acceder

directamente a los datos de la imagen a través de simples funciones de

interacción con XML.

En un principio pensaba emplearse la implementación SVGBasic, una

versión del formato especialmente pensada para su uso en sistemas

empotrados y dispositivos portables, como es el caso de la plataforma PDA. No

obstante, debido a la división del sistema desarrollado en dos módulos, los

archivos SVG nunca llegan ser empleados sobre la plataforma PDA.

37


4.5.3. AutoTrace

Para poder trabajar sobre una imagen de un mapa de carreteras es que

esa imagen se trate de imagen vectorial, y en formato SVG, que es el formato

que el sistema esta desarrollado para reconocer. Pero el propósito del proyecto

es permitir al usuario emplear como mapa de carreteras base cualquier

imagen, no sólo una que ya se encuentre en el formato adecuado, lo cual no

ocurrirá frecuentemente. De hecho, es lógico esperar que el usuario dispondrá

de la imagen del mapa en un formato ráster. Es por ello necesario convertir la

imagen del mapa de carreteras que se está analizando al formato empleado

por el sistema antes de empezar el propio análisis.

Para ello es necesario un elemento, comúnmente denominado como

motor de vectorización, que realice esta conversión. Se ha considerado que el

desarrollo de un motor de vectorización propio queda fuera del alcance del

proyecto, de hecho un desarrollo de este calibre podría ser considerado en sí

mismo como un proyecto de fin de carrera entero. Por ello, se ha optado por

adoptar en el proyecto un motor de vectorización ya desarrollado. Para esta

tarea se ha seleccionado el proyecto AutoTrace.

AutoTrace es un el resultado de un proyecto desarrollado con el

propósito de crear un motor de vectorización libremente disponible con

capacidades similares a las de aplicaciones comerciales como CorelTrace y

Adobe Streamline. De hecho, es ya superior en múltiples aspectos. Autotrace

38


es además, gratuito, tiene código abierto y es multiplataforma. Se distribuye

bajo la licencia GNU GPL. Autotrace fue seleccionado al ser un programa

gratuito, con un funcionamiento lo suficientemente eficaz y eficiente para los

requisitos del proyecto y que tenía soporte para la generación de ficheros SVG

como salida directa.

39


4.5.4. BMP

Windows Bitmap es sin duda el formato de imagen ráster más popular y

simple que existe. Su nombre no debe llevar a la confusión de que este formato

es empleado únicamente sobre sistemas Windows. Es por esto por lo que se

ha decido unificar los formatos de entrada del programa como BMP, siendo

esta la entrada que se le proporciona al Módulo Enrutador como archivo a

analizar y la que se pasa al motor de vectorización AutoTrace, agilizando así el

análisis del mapa sin necesidad de conversiones de tipo previas a un formato

interno único.

No cabe duda de que el usuario va a poder convertir a este formato

cualquier mapa que pueda poseer en cualquier otro formato de imagen, pues

básicamente todos los programas de tratamiento de imagen, incluyendo los

gratuitos como Gimp y Paint, que se encuentra en todo ordenador con un

sistema operativo Windows, permiten esta simple conversión. Además, BMP es

el principal formato producido por los equipos de escaneo de imágenes,

método que se espera sea uno de los principales para la generación de

imágenes de mapa que vayan a ser empleadas por el sistema.

40


4.5.5. XML (Extensible Markup Language)

XML (Extensible Markup Language) es uno de los más importantes

estándares del mundo informático. Fue desarrollado por el World Wide Web

Consortium, al igual que el formato de imagen vectorial que fue seleccionado

para ser empleado por el proyecto, SVG. El propósito con el cual fue

desarrollado el XML era el ser un lenguaje de etiquetas generalista que se

empleara para desarrollar lenguajes de etiquetas especializados. Seguir este

estándar facilitaría la interacción entre programas originalmente incompatibles,

y el compartimiento de información, especialmente a través de Internet.

Siguiendo esta filosofía, el sistema desarrollado hace un uso extensivo

de XML, recurriendo a él cada vez que tiene que manejar o escribir datos a o

desde fuentes externas.

Debido a que SVG es internamente un documento XML como ya se ha

descrito, toda la interacción de la aplicación con la imagen una vez vectorizada

se hace a través de XML. También se ha empleado XML para codificar los

datos del Grafo de Rutas en el documento que el Módulo Vectorizador prepara

para transmitir al Módulo Enrutador. Este último también codifica los datos

relativos al posicionamiento del mapa una vez este ha sido calculado por parte

del Módulo Enrutador, almacenando los resultados en el mismo Documento del

Grafo de Rutas. Por último, todos los datos relativos a la configuración de la

aplicación y a las opciones seleccionadas por el usuario que deban

41


permanecer cuando el sistema cuando la aplicación no esta funcionando se

guardan en un archivo de configuración que también esta codificado en XML.

42


4.5.6. Microsoft Visual Studio .NET

La plataforma de desarrollo central para la programación del proyecto

que se ha seleccionado es Microsoft Visual Studio .NET 2003. Se ha decidido

emplear este entorno en particular debido a que fue utilizado para la realización

de diversas prácticas durante la carrera. Aprender a utilizar un nuevo entorno

de programación hubiera robado tiempo al desarrollo principal del proyecto y

hubiese sido considerablemente costoso puesto que el entorno .NET 2003 ya

se poseía antes del inicio del desarrollo de proyecto. Por último, el propio .NET

proporciona un entorno de desarrollo para microordenadores y para la

plataforma Pocket PC 2002 y el sistema operativo Windows CE en particular.

Desde un punto de vista de la programación del sistema, el proyecto no

requiere de ningún requisito especial que fuerce el empleo de un entorno

alternativo. Por estos mismos motivos es por los que tampoco se ha empleado

la recientemente publicada última versión del entorno, Microsoft Visual Studio

2005.

43


4.5.7. C#

C# es un lenguaje orientado a objetos desarrollado por Microsoft a partir

de C++ como parte de su iniciativa .NET. Adopta conceptos de otros lenguajes,

principalmente Delphi, Visual Basic y Java, buscando principalmente crear un

lenguaje cuyo funcionamiento y requisitos fuesen simples.

C# se ha seleccionado como lenguaje de programación para el proyecto,

al igual que la plataforma de desarrollo .NET, por el hecho de la practica que

con él se ha obtenido durante la carrera, tanto directamente como de forma

sinérgica a través del trabajo con Java, lenguaje con el que comparte un

elevado número de similitudes. C# es así mismo posiblemente el lenguaje más

fiable, directo y estable de los presentados por el entorno .NET.

44


Capitulo 5 - Desarrollo del Sistema GPS

45


5.1. Decisiones de Diseño

Aunque el planteamiento inicial de la aplicación era que funcionara

enteramente sobre una plataforma Pocket PC, se ha decidido realizar el

proceso de tratamiento de imagen del mapa de forma independiente sobre

plataforma PC. Esto es principalmente debido a que el proceso de

vectorización es muy pesado y tiene elevados requisitos de memoria y una

gran cantidad de cálculos matemáticos considerablemente complejos con lo

que ejecutarlo sobre una plataforma tan limitada como un Pocket PC resulta del

todo imposible. Por este hecho precisamente es por lo que además ha sido

imposible obtener un motor de vectorización preparado para su funcionamiento

sobre Pocket PC.

Puesto que este proceso idealmente solo necesitará realizarse una vez

por cada mapa que vaya a emplear el usuario y no requiere de interacción con

el dispositivo GPS del Pocket PC, se ha decidido desarrollar un módulo para

plataforma PC que realizará el proceso de tratamiento de imagen y generación

del grafo y generará un documento XML del que el módulo enrutador extraerá

la información necesaria para trabajar. Puesto que el proceso de localización

del mapa en unas coordenadas geográficas determinadas requieren del uso del

dispositivo GPS, este proceso en particular sea realizado por el Pocket PC, y

sus datos serán insertados en el documento XML.

46


De este modo, la división en dos módulos de funcionamiento queda

como sigue. El módulo desarrollado para PC, denominado Módulo Vectorizador

engloba todas las tareas relacionadas con el tratamiento de la imagen. Eso

significa que será el único interactuará con el motor de vectorización AutoTrace

y con la versión vectorial del mapa, el archivo SVG. El Módulo Vectorizador

está enteramente orientado al desarrollo de un grafo de rutas correcto y fiable

que represente el mapa de carreteras, y esta diseñado para comprimir el

resultado de todo su trabajo en un único documento XML que es leído por el

otro módulo.

El segundo módulo, desarrollado para una plataforma Pocket PC se

denomina Módulo Enrutador. La única relación que tiene el Módulo

Vectorizador es el documento XML del que lee los datos relativos al Grafo de

Rutas. De este, el módulo debe extraer de ese archivo, y de la imagen original,

que también se introduce para que el usuario indique los puntos entre los que

requiere que se calculen las rutas mínimas, todos los datos necesarios para su

completo y correcto funcionamiento. El principal propósito del Módulo

Enrutador es el cálculo de las rutas que el usuario requiera. El Módulo

Enrutador, al estar incorporado en la PDA es así mismo el que interactúa con el

dispositivo GPS. Por ello, también es capaz de calcular la localización actual

del usuario y trazar rutas de y hacia su punto actual. Por eso mismo, también

se ha decidido incorporar la función de posicionamiento en este módulo. El

módulo es capaz, si el usuario lo desea, de guardar los datos relativos a la

localización en el mismo documento que el propio grafo de rutas para su

47


posterior utilización. Esta es la única modificación que este módulo puede

hacer sobre el documento.

48


5.2. Diseño de la Aplicación

Desde el punto de vista puramente de la arquitectura, el proyecto es

considerablemente simple. El peso del desarrollo recae sobre el desarrollo e

implantación de los algoritmos empleados por el sistema y sobre el uso de

diferentes técnicas de tratamiento de imágenes. Como resultado, la mayor

parte de los diagramas de diseño no aportan una cantidad de información

significativa sobre el proyecto.

Se incluyen a continuación los diagramas que se han considerado como

significativos en la aplicación. Los diagramas incluidos contienen una

representación externa de los dos módulos de los que se compone la

aplicación y de la relación existente entre ellos, y una representación interna de

su funcionamiento en forma de Diagramas de Flujo de Datos. Se incluye así

mismo el Diagrama de Secuencia del proceso de análisis de la imagen y

generación del Grafo de Rutas, pues éste es el proceso de mayor volumen y

más complejo de la aplicación.

49


5.2.1. División en módulos

50

PCMódulo Vectorizador

PDAMódulo Enrutador

Documento XML


5.2.2. Diagrama de Flujo de Datos del Módulo Vectorizador

51


5.2.3. Diagrama de Flujo de Datos del Módulo Enrutador

52


5.2.4. Diagrama de Secuencia del Proceso de Vectorización

53


54


5.3. Grafo de Rutas

Un grafo es una estructura abstracta central de la teoría de grafos que

representa una serie de relaciones entre elementos, y que se emplea en

multitud de algoritmos matemáticos. Suele representarse como un conjunto de

puntos denominados vértices o nodos conectados entre sí mediante una serie

de líneas denominadas aristas o arcos. Generalmente, se suele definir

matemáticamente como la combinación de dos conjuntos:

N es un conjunto de vértices o nodos

A N x N es un conjunto de pares de nodos llamados arcos o aristas

Dentro de esta definición, se define a un grafo como no dirigido si los

arcos son pares no dirigidos y grafo dirigido o dígrafo si lo son.

El Grafo de Rutas es el principal elemento del algoritmo de cálculo de

rutas mínimas. Se trata de un grafo no dirigido que representa una abstracción

del mapa de carreteras, reduciendo todos sus datos a únicamente aquellos que

resultan importantes en el proceso de cálculo de rutas. Está compuesto por una

serie de nodos que representan puntos que el algoritmo de generación ha

reconocido como significativos dentro del mapa de carreteras y por arcos que

representan las vías de circulación que los conectan. Los nodos están ubicados

sobre el plano del grafo, que coincide con el de la imagen del mapa en las

mismas coordenadas que los puntos que representan. Así, cuando el usuario

55


quiere calcular el recorrido entre dos puntos, el algoritmo de trazado de rutas

puede determinar el nodo cuyas coordenadas más se ajustan al del punto

requerido por el usuario. Los arcos como ya se ha dicho, representan

carreteras, pero como es natural en los arcos, son representados en el plano

del grafo como líneas rectas, por lo que normalmente no se ajustarán a la

carretera que representan, a menos que esa carretera sea también una línea

recta. No obstante, tanto la carretera como el arco empezarán y terminarán en

las mismas coordenadas.

Desde un punto de vista computacional, los datos asociados a los nodos

son sus coordenadas sobre el plano del grafo, y el conjunto de arcos que

pasan por ellos. Así mismo, mediante funciones asociados a ellos, los nodos

pueden identificar a sus nodos vecinos, de modo que se puede decir que estos

también son parte de los datos asociados a un nodo.

Los datos asociados a los arcos son su longitud y los nodos entre los

cuales está trazado. La longitud es la misma que la de la carretera a la que

representa, a pesar de que su trazado no coincida con ésta. En el caso de un

arco que haya sido generado como parte del proceso de refinado o por parte

del usuario mediante el editor de grafo, su longitud es la misma que la del

propio arco, es decir, la del segmento que une los dos puntos sobre los que

esta trazado. En el caso particular de dos arcos que hayan sido generados al

dividir un arco en dos mediante la herramienta del editor de grafo para añadir

nodos, la longitud de cada uno de los arcos resultantes es igual a un porcentaje

56


de la longitud total del arco del que provienen, de modo que la suma de sus

longitudes sigue siendo la misma que la del arco original.

Como ya se ha definido, el grafo de rutas es un grafo no dirigido. Esto

significa que las rutas que se pueden trazar pueden recorrer los arcos en

cualquier sentido, lo que a su vez implica que el algoritmo de trazado de rutas

considera que todas las carreteras son de doble sentido. Esto no es un

problema en el caso de carreteras fuera de vía de ciudad, pues ese suele ser el

caso. Al tratar mapas metropolitanos no obstante, esta limitación del grafo

provoca que sea poco útil para desplazamientos en coche. Un peatón, por otro

lado, podría seguir usando el mapa para calcular las rutas que requiera sin

problemas.

Se considero en un momento del desarrollo del proyecto el empleo de un

grafo dirigido para resolver este problema. No obstante, esta posibilidad se

descartó posteriormente por varios motivos. El principal de estos motivos es el

hecho de que el único modo para indicar a cada arco en que sentido discurría

la calle que representaba era haciendo que el propio usuario lo indicase.

Además de que insertar el sentido correspondiente a todos los arcos del grafo

es una tarea extremadamente pesada y lenta a la que definitivamente no se

quiere someter al usuario, si éste dispone de suficiente conocimiento sobre la

zona que esta mapeando como para poder indicar toda esta información, no se

puede decir que realmente necesite la herramienta.

57


5. 4. Módulo Vectorizador

El Módulo Vectorización es el primer módulo de los dos en los que se ha

dividido el proyecto. Realizando su funcionamiento normal, tomara un mapa en

un formato BMP, lo someterá a un proceso de análisis que resultará en la

creación de un Grafo de Rutas que contendrá toda la información

representativa para el cálculo de rutas sobre el mapa, refinará este grafo tanto

por si mismo mediante una serie de algoritmos automatizados, como mediante

acción directa y voluntaria del usuario, y codificará todo esta información en un

documento XML con un cierto formato propio que será leído por el otro módulo

para la realización de sus propias funciones.

El Módulo Vectorizador ha sido desarrollado para su uso sobre una

plataforma PC. Esto es debido a varios motivos que o bien justifican que las

tareas que va a realizar el módulo funcionarán mejor si se desarrolla sobre PC

o bien directamente impiden que se desarrolle para una plataforma PDA con

éxito. Primero, la realización de las tareas que se han asignado al Módulo de

Vectorización requiere interactuar con un motor de vectorización, un tipo de

aplicación que no existe en un formato portable. El desarrollo de un motor de

vectorización propio para su funcionamiento en combinación con el sistema es

una actividad que se ha considerado se encuentra fuera del alcance del

proyecto. Además, existen motivos lógicos por los que no existe una versión

para PDA de ningún motor de vectorización. La vectorización es un proceso

muy pesado que requiere de un número elevado de operaciones matemáticas

58


considerablemente complejas, resultando del todo inviable sobre una

plataforma tan limitada como una PDA.

Si bien este es un motivo por el cual no implantar la vectorización sobre

la PDA, existen otros motivos por los cuales implantar el módulo en una

plataforma PC. Es esperable que la generación del Grafo de Rutas de un

determinado mapa se realice únicamente una vez por cada mapa con el que se

quiera trabajar. Así mismo, es esperable que la principal vía a través de la cual

van a obtenerse los mapas que van a ser empleados para el cálculo de rutas

mínimas sea el propio PC del usuario, de modo que ya puede directamente, al

tiempo que obtiene los diferentes mapas que desea emplear, prepararlos para

su uso por parte del sistema de cálculo de rutas. Por último, la vectorización en

sí no requiere de ninguna interacción con el dispositivo GPS. Por todos estos

motivos parece evidente que este proceso debe ser realizado por parte del PC

que luego pasará sus resultados a la PDA.

59


5.4.1. Tratamiento de la imagen

El principal propósito del Módulo Vectorizador es analizar la imagen del

mapa para localizar las carreteras, calcular sus parámetros y generar el grafo

de rutas a emplear por parte del dispositivo GPS.

5.4.1.1. Identificación de carreteras

Se ha considerado que el método más eficaz para identificar las

carreteras, que en cuestiones de aspecto son extremadamente similares a

otros elementos geográficos que podían fácilmente inducir a confusión por

parte del algoritmo de conversión como ríos, líneas de coordenadas o texto de

gran tamaño era mediante la intervención por parte del usuario. Así, antes de

ejecutar la conversión, el usuario define que elementos son vías de circulación

en el mapa. Para identificarlas, se ha considerado que debido al modo en el

que se representan habitualmente las vías de circulación en los mapas de

carreteras, el mejor modo era por la identificación del color que se emplea para

dibujar cada uno de los tipos de vía. Así, lo único que tiene que hacer el

usuario señalar mediante un simple clic sobre las propias vías de circulación

los colores que se corresponden con los diferentes tipos de vías de circulación

presentes en el mapa y que el usuario desea que sean incluidas en el cálculo

del Grafo de Rutas.

60


5.4.1.2. Tratamiento en fases de la imagen

El proceso de tratamiento de imagen empleado para generar el grafo a

partir del mapa de carreteras proporcionado ha sido dividido en varias fases

para así simplificar la realización de pruebas sobre el código, la incorporación

de modificaciones y la expansión del algoritmo. El resultado de cada una de

estas fases es la entrada de la siguiente. Estas fases, están conceptualmente

diferenciadas, debido a que realizan tareas claramente distintas ya sea sobre

los datos de imagen original, la versión vectorizada de la imagen o el propio

Grafo de Rutas, pero son de todos modos continuas e inseparables. Cuando se

da al Módulo Vectorizador la orden de generación del Grafo de Rutas, se

ejecutan todas las fases de forma continua. Debido a esto, la ejecución de cada

una de las fases por separado resulta transparente a usuario.

Todas las fases trabajan bien sobre archivos temporales o bien sobre

variables internas del programa. De este modo, la imagen de mapa original

nunca se ve alterada.

61


5.4.1.2.1 Pretratado

Inicialmente la imagen recibe un proceso de pretratado orientado a

simplificar su manipulación por parte del motor de vectorización. Inicialmente se

reduce la imagen a una representación en blanco y negro en el que únicamente

se ven representados los colores que han sido definidos por el usuario como

pertenecientes a vías de circulación. Puesto que, debido normalmente a la falta

de calidad de la imagen, es frecuente que una forma cuyo color en un primer

momento era constante se haya visto convertido en una amalgama de

diferentes tonalidades con pequeñas variaciones entre sí, se consideran como

el mismo color aquellos que se encuentren dentro de una cierta similitud con un

color definido como vía. Esta similitud se determina como la diferencia entre los

valores de los diferentes bytes de colores, y la similitud mínima puede ser

definida por el usuario de a cuerdo a sus necesidades y la calidad de la

imagen. En sí, el sistema utiliza un sistema de colores de 32 bits, el

proporcionado por el propio objeto Color de las librerías de C#, aunque el byte

de Alpha no se emplea en absoluto, con la definición de color que realmente se

está empleando durante el pretratado es de 24 bits.

A la imagen en blanco y negro resultante del pretratado se le aplican a

continuación un filtro de sal y pimienta para eliminar el ruido que el tratamiento

pueda haber introducido y un filtro de bordes que realza las vías.

62


5.4.1.2.2. Vectorización Mediante Autotrace

Para realizar el proceso de convertir la imagen de su formato ráster BMP

al formato vectorial SVG, sobre el que se podrá trabajar de forma directa, se

emplea el motor de vectorización AutoTrace. Esto no significa, no obstante, que

no se tenga ningún control sobre el modo en que se realiza la conversión

debido a que el proceso se ejecute de forma externa al código de la aplicación.

Autotrace permite varios parámetros de configuración que determinarán el

modo en que se ejecutará la vectorización. Estos parámetros se han ajustado a

los valores que se ha determinado que producirán los mejores resultados

cuando sean aplicados sobre un mapa de carreteras habitual. No obstante,

pueden ser modificados a voluntad por el usuario. La aplicación recuerda los

valores introducidos y también es capaz de restaurar los valores

predeterminados.

Los parámetros de control del motor de vectorización AutoTrace están

recogidos en la siguiente tabla. Es importante notar que los valores que se

define aquí como predeterminados son los predeterminados que emplea el

Módulo Vectorizador, calculados tras probar el ajuste de múltiples de mapas de

carreteras, y no los valores predeterminados de Autotrace, que tienen un

propósito menos especializado para la conversión de cualquier tipo de imagen.

En la tabla también se define como los maneja el programa, es decir, si su

valor es directamente introducido por código o sí el usuario puede variarlo en

tiempo de ejecución.

63


Nombre Tratamiento ValorDescripción

Background Color Constante FFFFFF (Blanco)Define un color de la imagen como fondo, lo que implica que será

ignorado durante la vectorización. Puesto que después del pretratado es una

representación de las vías en negro sobre un fondo blanco cuyas

características no son importantes para el sistema, se define ese color como

fondo.Centerline Constante TrueNormalmente, AutoTrace almacena las características del mapa como

una serie de formas definidas por una línea de borde y el color que llena el

área que delimita. Al emplear esta opción, Autotrace representará los

elementos de la imagen como líneas de un determinado grosor y un

determinado color. Este modo es mucho más manejable por parte del sistema

puesto que el propósito de la digitalización es precisamente la extracción de

datos relativos a líneas.

Color Count Constante 1

64


Si se emplea este parámetro en la vectorización, AutoTrace reducirá el

número colores de la imagen al tratarla, simplificando así la salida que produce

y evitando la aparición de colores no deseados, como tonos de gris, en la

imagen al aplicar filtros. Puesto que el negro es el único color de la imagen

aparte del blanco, que como color de fondo es ignorado, la reducción de se

limita a un solo color.

Corner Threshold Variable 150Si en un determinado píxel, sus predecesores y sus sucesores forman

un ángulo menor que éste, entonces se considera como una esquina, en otro

caso se considera una curva. No obstante, si se encuentra dentro del radio de

píxeles de Corner Surround de otra esquina, entonces no se considera como

esquina propia sino como parte de otra esquina.Corner Surround Variable 4

Determina cuantos píxeles serán analizados en torno a uno punto

determinado para juzgar si ese punto es una esquina. Debido a esto, también

determina como de “grandes” son las esquinas.

Corner Always

Threshold

Variable 90

Si el ángulo presente en un píxel con potencial de ser esquina es menor

que el valor de este parámetro, entonces en ese píxel hay una esquina, a

pesar de que pueda encontrarse dentro del radio de Corner Surround de otra

esquina.Despeckle Level Variable 8

65


Autotrace tiene la capacidad de aplicar un filtro de realzado de bordes a

las imágenes que trata. Ésta es una funcionalidad que resulta particularmente

útil para conseguir un reconocimiento correcto de las vías de circulación. Este

parámetro regula el número de iteraciones que se aplicaran por parte del filtro

Despeckle Tightness Variable 3Este es otro parámetro de control empleado por el filtro de bordes. Su

valor se corresponde con el grosor del filtro, lo que modifica de que modo los

elementos cuya estructura de bordes tiene una menor o mayor complejidad se

ven más o menos realzados.

Error Threshold Variable 2Después de haber trazado las curvas representando las formas del

grafico, AutoTrace revisa la calidad de su aproximación. Si una curva está más

desviada respecto a la realidad que este valor, entonces es subdividida en dos

curvas que pueden representar mejor la realidad.Filter Iterations Variable 4

Esto define el número de veces que una línea es suavizada antes de

que AutoTrace intente ajustarle una curva.

Line Threshold Variable 1Cuando AutoTrace recorre las curvas que el proceso de ajuste a

generado si la diferencia de una de ellas con la línea recta definida por sus

extremos es menor del valor de este parámetro, entonces se trata de una

recta.Line Reversion

Threshold

Variable 0,01

66


Si una línea está más cerca de la recta de lo que define este parámetro,

siendo medido respecto al cuadrado de la longitud de la posible curva,

entonces la línea se mantendrá como una recta, aún en el caso de que sea

parte de un spline de mayor tamaño formado por curvas.Input Format Constante BMPDefine a cuál entre los distintos formatos de entrada que AutoTrace

admite pertenece la imagen. Puesto que se ha unificado la entrada a la

aplicación como BMP, éste es el valor que toma el parámetroOutput Format Constante SVG

Indica en cuál de los formatos de salida compatibles con AutoTrace se

quiere obtener la imagen vectorial. Como ya se ha definido, se trabaja con el

formato SVG, por tanto es ése el valor que se le da al parámetroTangent Surround Variable 3

Indica el radio en torno a un punto que se tendrá en cuenta para

calcular la tangente en ese punto.Remove Adjacent

Corners

Constante True

Al emplear esta opción, las esquinas que dispuestas una después de

otra se agruparán en una sola esquina. Este valor es necesario para

compensar por el efecto causado por el elevado Corner Always Threshold.

5.4.1.2.3. Digitalización

El archivo temporal SVG generado por el programa AutoTrace es

internamente un fichero XML. Gracias a esto es posible acceder directamente

su contenido para extraer los datos que definen las vías de circulación

representadas en el mapa. En el proceso de digitalización se recorre el

67


documento interno XML extrayendo los datos que describen la imagen de

mapa. Estos datos están expresados en varios tipos de estructuras. Puntos

significativos que están representados como un par de coordenadas,

segmentos, definidos por los puntos que son sus extremos, y curvas bézier

cúbicas que requieren de cuatro puntos para ser representadas. En esta fase

estos elementos se introducen en el programa en ejecución, convirtiéndolos en

variables en memoria para así poder manipularlos en las fases posteriores.

En esta fase además se calcula, a partir de los datos de los segmentos y

curvas, la longitud de las diferentes vías de circulación en píxeles, longitud que

luego será introducida como un dato más del Grafo de Rutas para así poder

emplearla para el cálculo de rutas mínimas. El resultado de esta fase es una

representación del mapa que internamente es una colección de líneas en que

se puede descomponer la imagen analizada y que se corresponden con las

vías de circulación del mapa.

68


5.4.1.2.4. Abstracción del Mapa a Grafo

A partir de los datos que obtenidos al analizar las curvas y rectas

calculadas en la anterior fase, se generan los arcos del grafo de rutas. Estos

arcos son una abstracción de las líneas del mapa, extrayendo de ellas los

datos que son realmente requeridos para la realización de las tareas del grafo.

Los datos que quedan almacenados en los arcos del grafo de rutas se limitan

entonces a las coordenadas de comienzo y fin de la línea y su longitud real.

Tomando como único dato las coordenadas de los extremos de estos arcos se

crean los nodos que suponen el otro componente de grafo.

5.4.1.2.5. Refinado

El grafo de rutas en bruto obtenido tras la abstracción del mapa de

carreteras no es directamente utilizable. Las imperfecciones del mapa,

generalmente causadas por la presencia de texto y la falta de calidad en la

imagen original, por la conversión al formato vectorial y las introducidas durante

la ejecución de las fases anteriores provocan la aparición de fallos en el grafo

de rutas. Para tratar estos problemas, se realiza sobre él una última fase de

refinado. Este refinado consiste fundamentalmente en la realización de tres

tareas:

69


Aproximación de nodos

La presencia de texto sobre las vías de circulación representadas en el

mapa y la presencia de manchas de color en la vía que caigan fuera de la

aproximación realizada durante la fase de pretratado habitualmente causan la

aparición en el grafo de cúmulos de nodos separados una distancia muy

reducida lo que los hace redundantes. Además frecuentemente el proceso no

habrá reconocido la existencia de vías que unan esos puntos y con ello no

habrán aparecido arcos representando las diferentes conexiones que debería

haber en el cúmulo. Otra posibilidad es que una línea que no estuviera definida

como una vía de circulación interrumpiera una que si lo fuera, lo que resulta en

un repentino corte en esa vía, dando lugar a dos nodos que casi están unos

encima del otro pero sobre los que no se reconoce que haya una vía que los

una. Una última posibilidad es que en un punto de interconexión entre varias

vías no sea correctamente reconocido y la interconexión no aparezca aunque

los nodos entre los que debería aparecer, sí.

Todos estos problemas suponen severos errores en el Grafo de Rutas

que a su vez causan fallos en el cálculo de las rutas mínimas. Este proceso

resuelve estos problemas y es por ello el principal proceso de la fase de

refinado. Lo que se hace es agrupar a los nodos que se encuentran separados

entre sí menos de una determinada distancia, y con ello sea factible la

posibilidad de considerarlos como realmente el mismo.

70


Un problema que surgió durante el desarrollo de este algoritmo de

aproximación fue que el programa reconocía como un único cúmulo de nodos

una superficie de demasiado tamaño, debido a que todos los nodos de ésta se

encontraban dentro de la distancia de aproximación de otro de los nodos del

cúmulo, aunque se encontrase a una gran distancia de todos los demás. Para

evitar que los cúmulos a agrupar crezcan demasiado, se controla que los

nuevos nodos que se añaden al cúmulo estén dentro de una cierta distancia al

centro de éste.

El cálculo del centro del grupo de nodos es un elemento importante del

proceso, pues también se emplea como la ubicación del nuevo nodo que se

crea como agrupación del cúmulo. La opción ideal sería el centro geométrico

del cúmulo, pero éste calculo ralentizaría enormemente el proceso, mientras

que la media es mucho más sencilla pero se ve enormemente influenciada por

las zonas más concentradas del cúmulo de nodos, desviando

considerablemente el centro. La solución por la que se ha optado es calcular la

media de tal modo que se ignoran los nodos que se encuentren a menos de

tres píxeles del otro nodo que si esté siendo considerado para el cálculo. El

cálculo de esta media ajustada es de hecho más rápido que la media normal y

el centro calculado no se ve tan influenciado por los grupos condensados de

nodos.

71


Conexión de nodos

En este proceso se establecen arcos entre aquellos nodos que, después

de haberse realizado la aproximación, se encuentran separados menos de una

cierta distancia, y no se encuentren aún conectados. La longitud de estos

nuevos arcos se calcula como la longitud lineal del arco. El propósito de eso es

resolver los fallos de conexión hayan aparecido por los mismos motivos que en

el proceso anterior, pero cuyos nodos no se encuentren tan cerca como para

ser considerados el mismo.

Es posible, en tiempo de ejecución alterar el orden en el que se ejecutan

estos dos procesos. Con el orden normal simplemente se recorre nuevamente

la lista de nodos conectando aquellos que sea pertinente. Esto produce un

efecto secundario poco deseado. Al ser agrupados los cúmulos de nodos,

particularmente en el caso de cúmulos grandes, puede ocurrir que dos nodos

incorrectamente desconectados que antes de la agrupación se encontraban lo

suficientemente próximos como para que un arco fuese trazado entre ellos, al

pasar por el proceso de agrupación y desplazarse hacia el centro de sus

respectivos cúmulos queden separados.

Para evitar este problema existe un orden alternativo. En él, la

interconexión de los nodos se hace dentro del mismo proceso que la

aproximación, creándose los nuevos arcos antes de que los cúmulos se reúnan

en nuevos nodos. Esto también tiene un problema, pues antes de que se

complete la aproximación de nodos el arco es considerablemente caótico y ello

72


implica que frecuentemente se creen arcos que no se corresponden con

conexiones reales. Además, al moverse los nodos de los extremos, la longitud

inicialmente calculada dejara de ser precisa, aunque se puede esperar que sea

por una franja muy pequeña. Es recomendable por ello no emplear este modo

en mapas que tiendan a generar una gran cantidad de cúmulos en el grafo, lo

que suele ocurrir con frecuencia en el caso de mapas de ciudad y menos en

mapas de carretera.

Para evitar comparaciones innecesarias y acelerar estos procesos, antes

de que se realicen estos dos procesos los nodos de grafo se ordenan según su

coordenada Y, y solamente se comparan con los vecinos cuya coordenada Y es

mayor y se mantiene dentro de la distancia de control, que dependerá del

proceso que se esté ejecutando. Si el nodo es admisible para comparación,

antes de iniciar el proceso para incorporarlo al cúmulo de nodos

correspondiente o trazar el un nuevo arco entre los nodos considerados, se

comparan las dimensiones X para ver si su diferencia se encuentra dentro de la

distancia establecida. Debido a este modo de hacer las cosas, no se están

comparando los nodos que estén dentro del círculo de cierto radio centrado en

el nodo estudiado, que sería lo normal, sino en un cuadrado de lado el doble de

la distancia analizada que cubriría ese círculo y estaría centrado en el mismo

nodo analizado.

73


Eliminación de datos redundantes

La ejecución de las diferentes fases y especialmente de los dos

procesos de refinado anteriores ha generado una considerable cantidad de

datos redundantes o inútiles en el grafo. Estos datos pueden llevar a confusión

durante el cálculo de rutas, aumentan innecesariamente la complejidad del

grafo lo que hace el proceso menos eficiente y ocuparían un espacio adicional

de sus datos ser codificados en el archivo XML que se crea para su uso por

parte del Módulo Enrutador. Puesto que este grafo va a ser empleado sobre

una plataforma considerablemente limitada, es importante eliminar todos los

elementos innecesarios. Así pues, esta última fase recorre el grafo localizando

y eliminando varios casos de elementos redundantes.

Bucles: Es decir, arcos que comienzan y terminan en el mismo nodo.

Debido al modo en que funciona A* no existe posibilidad de que se queden

atrapado en el bucle a menos que la longitud del arco sea cero, lo cual es

imposible por el modo en que se crea el grafo. Aún así, están introduciendo un

elemento adicional en el cálculo que lo ralentiza de modo sensible.

Arcos redundantes: Un arco resulta redundante cuando existe otro

distinto que conecta los mismos dos nodos. Esto aparentemente no causa

ningún tipo de problemas en el funcionamiento del algoritmo A*, pero cuando el

algoritmo se vea en la situación de tener que escoger entre uno de los dos

arcos para alcanzar a un determinado vecino, va a optar siempre por el más

corto, que lo más probable es que sea el incorrecto. Esto es debido a que el

74


trayecto largo habrá sido extraído de los datos relativos a una curva bezier

cuya longitud puede ser muy distinta de la que separe sus puntos, mientras que

el corto posiblemente sea el resultado de la generación de un arco durante la

segunda fase del refinado, cuya longitud es la separación entre sus extremos.

En el caso de que ambas rutas sean naturales sus longitudes serán muy

similares, y por ello no generarán tanto error independientemente de cual se

escoja.

Por ello, durante esta fase se eliminan los que resulten redundantes con

otros ya existentes, eliminando primero los más nuevos, que posiblemente

hayan sido generados durante el proceso de conexión de nodos, y que por esto

se encuentran al final de las listas de arcos de cada nodo. En caso de no ser

arcos creados posteriormente, como ya se ha explicado, no se estará

introduciendo un grado elevado de imprecisión.

Es interesante notar que en una versión anterior del sistema la limpieza

de este elemento y la de los bucles estaban separadas como procesos

distintos, pero luego se descubrió que los bucles también entraban en la

definición que este proceso hacía de arcos redundantes. Desde el punto de

vista de un nodo, un bucle se ve como dos arcos (cada uno de los dos

extremos del arco conectados al nodo) que llevan al mismo destino (es decir, el

propio nodo en el que aparece el bucle) Al eliminar “uno de los arcos” tanto del

nodo analizado como del destino, que era el mismo pero empleando la otra

75


conexión, el resultado era que ambas conexiones del bucle y el arco

problemático en sí se eliminaban con éxito y de forma transparente al método.

Nodos aislados: Nodos que no están conectados con ningún otro nodo.

Este tipo de nodos aparece cuando al agrupar un grupo de nodos éste no

resulta estar conectado con ningún otro elemento del grafo. Como resultado,

todos los arcos del nuevo nodo surgido del cúmulo son bucles, y después de

que se hayan limpiado durante los procesos anteriores el nodo se queda sin

ninguna conexión. El principal motivo por el que se eliminan estos elementos

es para evitar que el usuario intente calcular la ruta a o desde uno de estos

nodos aislados.

76


Parámetros de Refinado

Se ha mencionado durante la descripción de los procesos varías

distancias que controlan el rango hasta el que se agrupan y se conectan los

procesos. Estas distancias de control pueden ser reguladas en el momento de

realizar la generación del Grafo de Rutas.

Radio de Nodo: Este parámetro se usa durante el proceso de

aproximación de nodos. Dos nodos que se encuentren separados una distancia

menor que el valor de este parámetro se consideraran como el mismo. Esto

significa que ambos pertenecerán al mismo cúmulo de nodos que al final del

algoritmo se convertirá en uno solo. Es interesante mencionar que el radio no

se compara con la distancia que realmente separa los nodos, sino que se

compara consecutivamente con la diferencia entre sus ejes Y y X. Esto se hace

así porque antes de que se comience a realizar iteraciones comparando las

coordenadas de los nodos entre sí, la lista de nodos se ordena por su

coordenada Y. Cuando se realizan las iteraciones solo se sigue comparando el

nodo evaluado con sus vecinos si la diferencia en el eje Y es menor que el

Radio de Nodo antes de pasar al siguiente nodo. Con esto se consigue reducir

enormemente el número de iteraciones necesarias para realizar el proceso al

eliminar una gran cantidad de iteraciones innecesarias. Lo que también implica

es que cuando una iteración entra en la parte del algoritmo dedicada a

comprobar si ambos nodos deben estar presentes en el mismo cúmulo, la

distancia que les separa en y es valida como para aproximarlos, con lo que

77


únicamente hace falta comparar sus coordenadas X. Por esto es por lo que la

distancia entre los nodos se compara en ambas direcciones por separado, en

lugar de calcular la distancia real en línea recta entre esos elementos. El

resultado que esto implica es que el área en torno a la cual un nodo puede

considera a otro como parte del mismo cúmulo es un cuadrado, no un círculo.

Radio de Centro: Este parámetro también es empleado durante el

proceso de aproximación de nodos. Cuando se considera si un nuevo nodo va

a ser añadido a un cúmulo de nodos, se calcula la distancia que lo separa del

centro del cúmulo. En este caso la distancia que se evalúa es la distancia real,

es decir, la longitud del segmento que se puede trazar entre el nodo y el centro

del cúmulo.

En el caso de que ninguno de los dos nodos se encuentre en un cúmulo,

la comprobación no se realiza, pues ellos mismos son los centros respectivos

de sus cúmulos y ya se encuentran de por sí separados por la distancia del

Radio de Nodo, cuyo valor será menor que la de este nodo. En el caso de que

ambos pertenezcan a cúmulos, sus respectivos centros se comparan. Esto es

debido a que se podría entender cada uno de ellos esta añadiendo un único

nodo a su cúmulo; el que surge de realizar la aproximación sobre el nodo

vecino.

78


El propósito por el que esta segunda comparación se hace es para evitar

que los cúmulos crezcan hasta alcanzar unas dimensiones demasiado

elevadas debido a la aparición de zonas convertibles en cúmulos de gran

tamaño, con lo que se evita el llamado “efecto estrella” en el grafo. Ese

problema se denomina así debido a la aparición de nodos en el centro de áreas

vacías de los que sale un gran número de arcos conectándolos con nodos

situados en el borde del área vacía. Esto les da aspecto de estrellas. El origen

de estas áreas es causado por cúmulos de gran tamaño que al agruparse

vacían la zona en la que se encuentran de nodos estableciendo el nodo central

de la estrella. El origen de los arcos que le dan su aspecto característico es

como conexiones que los nodos del cúmulo tenían con nodos en el exterior del

cúmulo. Bajando el valor de este parámetro se elimina la presencia de estrellas

en el grafo creado.

Radio de Conexión: Este parámetro se emplea durante el proceso de

conexión de los nodos. Si la distancia que separa dos nodos es menor que el

valor de este parámetro, se creará un arco que los una. El valor de longitud de

los arcos así creados es igual a la propia longitud del arco. El modo en que se

comparan las coordenadas de los nodos es el mismo que en el caso del

proceso de aproximación de nodos, por lo que el área en torno al nodo

evaluado en la que se comprobará la existencia de otros nodos es igualmente

un cuadrado en lugar de un círculo.

79


5.4.2. Editor de Grafo

Los mapas distribuidos comercialmente por compañías especializadas

en la fabricación de mapas para GPS están completamente cerrados a

modificaciones. Esto implica un gran número de problemas para el usuario

final. Si no fuera por esta limitación, el usuario podría editar libremente el mapa

de navegación, corrigiendo errores que los creadores sufrieron al crear la

mapa, actualizándolo manualmente cuando se abrieran nuevas carreteras, o

incluyendo puntos significativos o nuevas rutas propias, como por ejemplo, si

descubriera un atajo campo a través que evidentemente no aparece en ningún

mapa pero que el usuario puede tomar con su todoterreno.

Para evitar esta limitación, el Módulo Vectorizador incluye una aplicación

de edición con la que el usuario puede modificar manualmente el Grafo de

Rutas, denominada el Editor de Grafo. Mediante este editor, el usuario puede,

de modo simple y solo con unos pocos clics, editar todas las características del

grafo. El editor incluye como herramientas:

5.4.2.1. Añadir Nodo

Crea un nodo en las coordenadas del punto en el que usuario haga clic.

Además, es posible emplear varios modos de atracción al añadir los nodos:

80


Sin atracción: Simplemente crea el nodo en las coordenadas que le

indique el usuario. Puesto que aún es un nodo nuevo, eso implica que caería

dentro de la definición de nodo aislado al no tener ningún arco conectado. Para

que el nodo sea útil, es necesario que el usuario trace arcos hacia él.

Arco Magnético: Determina el punto más cercano del arco más cercano

y allí es donde coloca el nuevo nodo. El arco, así mismo, queda dividido en

dos, cada uno de los cuales une el nuevo nodo con los extremos de arco

original.

Nodo Magnético: Determina el arco más cercano al punto donde el

usuario quiere añadir el nodo y a continuación el arco es “atraído” por el nodo.

El nodo se coloca en las coordenadas que indico el usuario indicó y el arco se

divide en dos, cada uno de los cuales une el nuevo nodo con los extremos de

arco original.

5.4.2.2. Mover Nodo

Cambia las coordenadas de un nodo seleccionado por el usuario a las

que éste defina. El efecto que esto produce es que le nodo se mueve sobre el

plano del grafo.

81


5.4.2.3. Eliminar Nodo

Borra el nodo indicado por el usuario. Al eliminar el nodo también se

elimina de modo automático todos los arcos asociados al nodo, puesto que su

existencia esta definida como la conexión de dos nodos. Por tanto, un arco sin

un extremo no puede existir.

5.4.2.4. Añadir Arco

Traza un nuevo arco que conecta dos nodos. Puesto que un arco existe

en tanto que existan los dos puntos entre los que esta trazado, no es posible

crear un nuevo arco sin que sus extremos ya existan. De modo que es

necesario crear los nodos antes que los arcos si se quiere dibujar una nueva

vía de circulación en el grafo. El valor de la longitud del nuevo arco es igual a la

longitud del propio arco, es decir, la del segmento que conecta sus nodos

extremo.

El editor comprueba que el nuevo arco no sea un bucle y que no exista

ya ningún arco que una los dos puntos, para evitar que el usuario añada

accidentalmente información redundante al grafo.

82


5.4.2.5. Modificar Arco

Permite alterar los parámetros que definen al arco seleccionado por el

usuario. No obstante, puesto que las coordenadas de sus extremos están

definidas por los nodos que une no puede modificarlas (para eso esta la

herramienta de Mover Nodo) el único parámetro que puede editarse es la

longitud del arco. Puesto que la escala del mapa es parte del posicionamiento y

ese es un proceso del Módulo Enrutador, la longitud no se puede definir en

kilómetros sino que se tiene que definir en píxeles.

5.4.2.6. Borrar Arco

Elimina el arco indicado por el usuario. Puesto que los nodos extremo

pueden seguir existiendo sin el arco que los une, no son eliminados junto con el

arco.

83


5.4.3. Generación del documento XML

Para que el grafo pueda ser empleado por el Módulo Enrutador y que la

ejecución de todos los procesos realizados por parte del Módulo Vectorizador

de un resultado útil, es necesario transmitir la información del grafo de rutas al

Módulo Enrutador. Se ha decidido hacer esto almacenado todos los datos del

Grafo de Rutas en un documento XML con al que se la ha dado cierto formato.

Del mismo modo que en la generación inicial del grafo se emplearon

únicamente los datos relativos a la disposición de los arcos y se dedujo la

disposición de los nodos del grafo a partir de ellos, en el fichero XML solo se

están almacenando datos relativos a los arcos. Concretamente, se está

codificando la longitud de cada arco y las coordenadas de cada uno de sus

extremos, que son las precisamente las coordenadas correspondientes a los

nodos a los que están conectados.

84


5.5. Módulo Enrutador

5.5.1. Lectura del fichero XML

Antes de poder trabajar con rutas sobre el mapa es necesario extraer los

datos del grafo de rutas del fichero XML generado por el Módulo Vectorizador,

y el archivo BMP original del mapa. Del archivo BMP no se va a extraer dato

alguno, puesto que toda la interacción con los datos de la imagen se ha

limitado al Módulo Enrutador. Únicamente se está importando para ser

empleado por la interfaz con el usuario. A fin de cuentas, el propósito del

usuario es que el sistema calcule rutas entre puntos determinados del mapa,

aunque realmente el algoritmo ignore al mapa y se limite a calcular rutas entre

coordenadas específicas del Grafo de Rutas.

Inicialmente se pensó en comprimir estos dos elementos en único

archivo, de modo que el Módulo Enrutador pudiera trabajar directamente

proporcionándole un único fichero. No obstante, esta aproximación impedía

que el usuario pudiera emplear diferentes mapas, por ejemplo uno de

carreteras y otro geográfico, sobre el mismo grafo, o diferentes grafos sobre el

mismo mapa, en caso de que hubiese generado varios grafos modificando los

valores de refinado. Además, puesto que el usuario ya tiene el mapa en un

archivo bitmap que puede perfectamente emplear con el Pocket PC, se estaría

insertando información redundante e innecesaria en el archivo generado por el

Módulo Enrutador al añadirle otra vez el mismo archivo bitmap.

85


5.5.2. Calculo de Rutas Mínimas

El principal propósito del Módulo Enrutador es el cálculo de la ruta de

mínima distancia entre dos puntos definidos por el usuario sobre el mapa. Para

ello, inicialmente determina cuáles son los nodos más próximos a los puntos

definido por el usuario, debido a que los algoritmos de búsqueda heurística solo

son capaces de determinar rutas entre los nodos del Grafo de Rutas. Una vez

determinados los nodos, se calcula la ruta de mínimo recorrido desde el grafo

de inicio hasta el de destino, aunque independientemente de cual de los dos

sea el origen y cual el destino, la ruta mínima calculada será siempre la misma

óptima. Para salvar la distancia que separa los puntos entre los que el usuario

deseaba calcular la ruta mínima y los nodos entre los cuales la ruta realmente

se ha calculado se añaden un par de tramos que conectan los nodos con los

puntos definidos por el usuario. Estos tramos se ven reflejados únicamente en

la presentación de la ruta mínima que el sistema ha calculado al usuario y en la

distancia total que se indica mide. A los nuevos tramos se les da como longitud

la que tienen en línea recta. Tanto la presencia de estos tramos como los

puntos que realmente haya marcado el usuario son totalmente transparentes

durante el manejo del grafo de rutas y el cálculo de la ruta mínima, que solo

trabaja con nodos.

86


Representación de la ruta calculada

Una vez el algoritmo ha calculado cual es la ruta de mínima longitud

entre los nodos origen y destino, debe presentársela al usuario para que este

pueda emplearla y con ello le dé utilidad al cálculo realizado. El proceso de

presentación dibuja sobre el mapa los dos puntos que el usuario definió como

extremos de la ruta, la conexión de estos puntos con los nodos más cercanos y

los arcos que componen la propia ruta, pero no representa ni los nodos origen

y destino ni los intermedios por los que pasa la ruta. Se decidió que mostrar los

arcos era suficiente para identificar el camino y de representarse los nodos

podía fácilmente confundir al usuario.

En las primeras versiones del sistema, este guardaba el trazado de las

carreteras que se correspondían con los arcos y eran éstos los que se

representaba sobre el mapa. Pero debido a los sistemas de refinado del grafo,

la relación de arco y carretera pasó a estar menos definida. Cuando la ruta se

representaba una ruta mínima sobre el mapa aparecían varios pequeños

huecos en el trazado resultante causados por la eliminación de nodos y el

único escenario en que los trazos se alineaban de un modo continuo era

cuando pertenecían al mismo spline. El resultado era confuso y desagradable a

la vista. De modo que se pasó a emplear los propios arcos para representar la

ruta, que aunque no se ajusten a las curvas de las vías de circulación tan bien

como los trazos, hacen su trabajo de representar la ruta mucho mejor, y siguen

87


siendo lo bastante específicos como para conocer la ruta a tomar sin

problemas.

La presentación de la ruta también indica cual es la longitud total de la

ruta calculada. Si el mapa ya ha sido posicionado, entonces conoce cual es la

ratio de píxeles a kilómetros, y con ello puede indicar la distancia total en

kilómetros. En caso contrario, indica la longitud de la ruta calculada en píxeles.

También existe la posibilidad de que no exista ninguna ruta que una los

dos puntos definidos por el usuario. En ese caso, la aplicación indicará ese

problema al usuario y volverá al estado de reposo.

88


5.5.3. Posicionamiento

Para poder interactuar con el módulo GPS en sus funciones, es

necesario realizar antes lo que se denomina posicionar el mapa. Esto consiste

en definir el punto del mundo que representa el mapa (localización), la cantidad

de superficie que cubre (escala) y el ángulo en el que esta respecto a la

dirección Norte (orientación). Para ello, el usuario deberá definir dos puntos,

denominados puntos de posicionamiento, sobre el mapa, e indicar cuales son

las coordenadas geográficas reales de esos puntos. Es posible definir “aquí”

como la localización de un punto, en tal caso el sistema tomará del GPS los

datos del punto en que se encuentra en ese momento.

La localización de los puntos sobre la imagen del mapa también es

significativa puesto que e punto medio en el segmento definido por los puntos

de posicionamiento es el denominado punto de localización del mapa, es decir,

donde se ha colocado la “chincheta” que fija el mapa en un lugar en el mundo,

y también es el punto por el que pasan el paralelo y el meridiano centrales. La

localización óptima para el punto de localización es el centro del mapa, así que

es una buena idea colocar los puntos de posicionamiento de acorde con esto,

especialmente si se está trabajando con un mapa a una escala elevada o

situado considerablemente lejos del Ecuador para reducir la imprecisión al

mínimo.

89


Definir incorrectamente los puntos de posicionamiento, al dar dos puntos

con las mismas coordenadas geográficas o geométricas, o incluso coincidiendo

en ambas daría lugar a fallos durante el cálculo de los parámetros de

conversión, al aparecer cálculos indeterminados y sistemas de ecuaciones

irresolubles. Por ello, aún antes de iniciar los cálculos para determinar el

posicionamiento se comprueba que no haya ningún problema con los puntos

proporcionados por el usuario, informándole en caso contrario para que

proporcione dos nuevos puntos.

5.5.3.1. Localización

La localización es uno de los parámetros que hace falta definir para

posicionar el mapa. Se define como la ubicación donde se sitúa el mapa, y

puede ser definida conociendo únicamente la longitud y latitud reales de un

punto dado del mapa, del cual así mismo se conoce las coordenadas en

píxeles sobre el propio mapa. Debido a la significancia de este punto se la ha

dado la denominación de punto de localización o punto central, aunque esto no

implica que necesariamente vaya a estar en el centro del mapa. No obstante,

cuanto más cerca se encuentre del centro del mapa, la deformación generada

por la proyección de la Tierra sobre el plano será menos pronunciada, y por ello

se producirá una menor imprecisión durante la conversión de coordenadas.

90


Durante el proceso de posicionamiento, el punto de localización se

determina como el centro del segmento que une los puntos de posicionamiento

dados por el usuario. El meridiano y el paralelo que pasan por el punto central

se denominan como el meridiano y paralelo centrales. Los puntos cubiertos por

el meridiano y paralelo centrales son los únicos en el mapa cuyas coordenadas

son absolutamente correctas, y la imprecisión generada por el aplanamiento de

la Tierra se incrementa conforme el punto observado se aleja de ellos. Este es

el motivo por el que el hecho de que el punto de localización este cerca del

centro del mapa reduce su imprecisión total.

5.5.3.2. Orientación

La orientación es otro de los parámetros que hace falta definir para

posicionar el mapa. Se define como el ángulo que existe entre una recta

dibujada sobre el mapa y la recta real que estaría representando sobre la

Tierra. También se puede definir como el ángulo existente entre la dirección

Norte real y la orientación del eje y-, es decir, la dirección vertical en sentido

hacia arriba del mapa.

Es importante destacar que debido al modo en que se calculan los

parámetros de conversión, el sistema es incapaz de trabajar con ángulos

mayores de +-90º, y dará lugar a resultados absurdos de emplearse un mapa

con esa orientación. Esto no es un problema real, puesto que en caso de que

91


este fenómeno se produciera implicaría que en el mapa el Norte está

apuntando hacia abajo, y ésta es una situación en la que no se espera que el

usuario esté con frecuencia. Para resolver este problema y así poder emplear

el mapa se recomienda rotar 180º la imagen antes de tratarla. Esto hará que el

ángulo de orientación esté dentro de los límites requeridos.

Este fenómeno es debido a que el valor real del ángulo de orientación

nunca es calculado. El ángulo de orientación nunca se utiliza directamente

durante el proceso de trasformación de coordenadas, sino afecta al resultado

de la conversión a través del valor de su seno y coseno. Estos valores no se

calculan a partir del valor del ángulo sino directamente como incógnitas de un

sistema de ecuaciones. A partir del sistema, de hecho, únicamente se calcula

el seno, y el coseno se calcula a partir de él.

cos α = √1-sen2 α

Es precisamente el que se use esta formula en lugar de calcular el

coseno a partir del sistema de ecuaciones igual que se hace con el seno lo que

se debe que el sistema falle cuando se vea expuesto a ángulos de orientación

mayores de +-90º. Un ángulo que se encontrase fuera de este rango tendría un

coseno negativo, pero se puede ver que la formula que se está empleando

para calcularlo siempre va a dar como resultado un valor positivo, puesto que

se está tomando únicamente la solución positiva de la raíz cuadrada. Al no

poder emplear un coseno negativo, no se puede representar un ángulo fuera

de +-90º.

92


5.5.3.3. Escala

La escala es el último de los parámetros que hace falta definir para

posicionar el mapa. Se define como el ratio existente entre la longitud de un

segmento representado en el mapa y la longitud real del segmento sobre la

superficie de la Tierra que estaría representando. En el sistema, se define

como el ratio existente entre la longitud representada de un km y la longitud de

uno de los lados de un píxel. De este modo, al aplicar este ratio a una distancia

real en kilómetros definida sobre la superficie de la Tierra se obtiene la longitud

en píxeles que correspondería esta distancia sobre el mapa.

Al emplear este método al trabajar con la escala se incluye el cambio de

escala propio del mapa y la conversión de unidades de kilómetros a píxeles,

requerida para realizar la representación sobre el mapa, en una única

operación matemática. La escala es el elemento más simple de calcular a partir

de los puntos de posicionamiento, simplemente calculando la distancia real

entre ellos contra la distancia en píxeles que separa los puntos en el mapa.

93


5.5.3.4 Empleo de un Modelo de Tierra Plana

Inicialmente se pensó en tratar la tierra como una esfera, viendo los

mapas como proyecciones sobre un plano de áreas de esta esfera. No

obstante, esto forzaría a realizar múltiples cálculos para convertir las

coordenadas geográficas a sus coordenadas equivalentes proyectadas sobre la

superficie del mapa. Además a la escala a la que está orientado el uso del

enrutador, que es la misma en la que se suelen emplear los mapas de

carreteras, la curvatura de la tierra tiene muy poca influencia en las distancias.

Por esto se ha decidido emplear un modelo de tierra plana. Al emplear este

modelo, es posible realizar la conversión de coordenadas y el posicionamiento

del mapa sin requerir ninguna operación compleja.

Al emplear esta conversión lo que se está haciendo es aplicar una

proyección Mercator sobre la Tierra. Este modelo proyecta la tierra sobre un

cilindro, de modo que las áreas que más deformadas se ven son las que están

a mayor distancia de la línea de contacto del cilindro con la Tierra. Por ello la

selección del radio del cilindro es crítica.

94


5.5.3.4.1. Uso de dos puntos frente a uso de tres puntos

Para definir la posición de un plano respecto a una esfera, hacen falta

tres puntos de fijación. No obstante, debido a que se está empleando un

modelo plano para la tierra, es posible hacerlo únicamente con dos puntos.

Aparentemente, para ubicar la posición de un plano respecto a otro hacen falta

igualmente tres puntos pero se posee una cierta cantidad de conocimiento que

restringe las posibles posiciones de los planos permitiendo determinar su

posición únicamente con dos puntos. Concretamente, este conocimiento

adicional consiste en el hecho de que se sabe que el plano del mapa es

concurrente con el plano de la Tierra y que el sentido positivo del eje z de

ambos apunta en la misma dirección, es decir, que el punto de vista desde el

que se ha creado el plano esta por encima de la superficie terrestre.

Los puntos que el usuario proporciona, definidos por sus coordenadas

geográficas reales sobre la Tierra y por sus coordenadas geométricas en

píxeles sobre el mapa se denominan puntos de posicionamiento, y a partir de

ellos se calcularan todos los parámetros requeridos para la conversión.

95


5.5.3.4.2. Parámetros de conversión de coordenadas

El propósito del proceso del posicionamiento es generar una serie de

parámetros, denominados parámetros de conversión, que serán empleados

para la conversión de coordenadas entre el sistema geográfico de la Tierra y el

sistema geométrico del mapa.

Grado de longitud

Como ya se ha definido con anterioridad, la longitud de un grado de

longitud varía con la latitud desde su longitud máxima en el Ecuador hasta cero

en los polos. Este parámetro representa la longitud de un radián de la

circunferencia del paralelo central del mapa, y con ello es idéntica al radio del

paralelo central. También se puede definir como la longitud de un radián de

longitud en la latitud del punto de localización. Esta medida es la que se tomará

como valor de la longitud en todo el mapa. El motivo de que se calcule la

longitud de un radián y no de un grado como parecería más natural es debido a

que la totalidad de los cálculos realizados internamente en el sistema se

realizan en radianes, al ser esta una unidad más manejable desde el punto de

vista matemático.

96


Para calcular el Grado de longitud se emplea la ley esférica de cosenos.

Aplicándola, se puede deducir una popular fórmula para calcular la distancia a

vuelo de pájaro sobre la superficie de la Tierra entre dos puntos definidos por

sus coordenadas geográficas.

d = arcos(sen(lat1)·sen(lat2)+cos(lat1)·cos(lat2)·cos(long2−long1))·R

Siendo R el radio de la Tierra en la unidad en la que se quiera obtener la

distancia, y estando las coordenadas descritas en radianes. Esta fórmula se

adaptó para ser empleada para este cálculo, resolviendo la distancia que

separaba dos puntos de misma latitud y longitud de diferencia 1 radián.

Aplicando esto, la fórmula queda:

Grado de Longitud = arcos(sin2(lat) + cos2(lat)·cos(1))·R

Siendo lat la latitud a la que se quiere calcular el grado de longitud, y R

estando expresado en kilómetros, que al ser esta la unidad en la que se está

manejando el resto de las distancias, y dándole un valor de 6372 km como ya

fue explicado en la descripción del Modelo Geográfico. Se puede ver que,

efectivamente, para lat=0º, el Ecuador, el Grado de Longitud es igual al radio

de la Tierra, es decir, a un radián de la Tierra, y que a lat=90º, los polos, el

grado vale 0.

97


Ratio de Kilómetros a Píxeles

El valor de este parámetro representa la longitud en píxeles de un

kilómetro representado en el mapa. Por ello, al realizar el producto entre este

ratio y una distancia real en kilómetros, se obtiene la distancia equivalente

definida en píxeles sobre el mapa. Esta conversión tiene varios propósitos. Por

un lado introduce la escala del mapa como parámetro de posicionamiento en la

conversión de coordenadas y también cambia la unidad de medida de los

kilómetros empleados para definir una posición geográfica sobre la Tierra a las

medidas en píxeles que definen una posición geométrica sobre el mapa. Por

otro lado, permite convertir las distancias calculadas por el algoritmo de rutas

mínimas, que se encuentran en píxeles a kilómetros, una unidad mucho más

útil para el usuario. Para calcular este ratio lo único que se hace es dividir la

distancia geográfica real en kilómetros que separa los dos puntos considerados

entre la distancia en píxeles que sepa los mismos dos puntos sobre el mapa.

Matriz de Conversión de Coordenadas

El sistema geográfico, ya esté valorado en grados sexagesimales,

radianes o kilómetros, tiene como centro de coordenadas la intersección del

Ecuador con el meridiano de Greenwich y como vertical la dirección Norte-Sur.

El mapa tiene como centro de coordenadas su esquina superior izquierda, y su

propia vertical que puede o no coincidir con la dirección Norte-Sur.

98


Para resolver el paso de uno a otro se emplea la Matriz de Conversión

de Coordenadas. Esta matriz es una versión modificado de la habitual matriz

de conversión por el hecho de que la segunda fila tiene el signo opuesto. Esto

es necesario porque las coordenadas del mapa están medidas respecto al

punto superior izquierdo y la y crece hacia abajo, es decir, la dirección opuesta

a los sistemas de coordenadas tradicionales y también al sistema de

coordenadas de la Tierra. Al cambiar el signo de la y durante la conversión del

mapa se consigue invertirla para sus usos en este tipo de sistema de

coordenadas.

cosα senα -X

senα cosα Y

0 0 1

99


5.5.4. Conversión de coordenadas

Para poder representar al usuario las coordenadas proporcionadas por

el dispositivo GPS sobre el mapa de carreteras proporcionado, es necesario

realizar una conversión entre los sistemas de coordenadas. Las

proporcionadas por el GPS, representan un ángulo, en grados decimales,

sobre una esfera que un determinado punto mantiene respecto al Ecuador y al

Meridiano de Greenwich. Sobre la pantalla de una PDA las coordenadas

utilizadas se miden en píxeles, y representan la distancia a la esquina superior

izquierda de la pantalla, trabajando sobre un plano. Además, durante la

conversión habrá que aplicar los parámetros del mapa que fueron definidos por

el posicionamiento: La localización, la orientación y la escala. Esta conversión

de coordenadas requiere de tres procesos.

5.5.4.1. Aplanamiento de la Tierra

La Tierra es una esfera, y las coordenadas proporcionadas por el

dispositivo GPS definen una posición sobre esa esfera. No obstante, durante el

posicionamiento se ha definido el plano sobre una proyección Mercator de la

Tierra, es decir, un medio plano. El primer paso para la conversión de

coordenadas es, por tanto, definirlas respecto a un plano. Para ello, se calcula

la distancia en kilómetros que separa punto definido por las coordenadas

geográficas del Ecuador y del Meridiano de Greenwich.

100


Es decir, se convierte la distancia en grados a una distancia en

kilómetros, por ser ésta una unidad que puede emplearse tanto en superficies

esféricas como planas.

Antes de realizar ningún cálculo, se convierten los ángulos medidos en

grados decimales que proporciona el GPS a radianes, debido a que esta es

una medida mucho más manejable desde un punto de vista matemático,

especialmente porque se estará trabajando con funciones trigonométricas.

La longitud en kilómetros de un grado de latitud se una como constante,

valiendo 111 km. Los grados de longitud, por otro lado, varían respecto a la

latitud, desde 111 km en el ecuador los círculos convergen sobre sí mismos

hacia los polos, manteniéndose constantes dentro de una determinada latitud.

Para resolver esto, durante el posicionamiento del mapa se calcula la longitud

de un grado de longitud en la latitud media en la que se encuentra el mapa, y

se toma como constante. Con esto, el efecto que se está consiguiendo es

transformar las coordenadas a una proyección Mercator que emplea como

circunferencia del cilindro de proyección el paralelo situado en la latitud del

mapa. Sobre esta proyección Mercator ya se puede trabajar como mapa plano.

101


5.5.4.2. Cambio de Escala

El posicionamiento define los tres elementos que deben ser tenidos en

cuenta para la conversión de coordenadas: La localización, la orientación y la

escala. En esta fase se trata el último de estos elementos. Para ello

simplemente se le aplica a las coordenadas en kilómetros calculadas un ratio

de conversión calculado durante el posicionamiento que define la proporción

entre kilómetros y píxeles presente en el mapa. Como resultado, se obtienen

las coordenadas medidas en píxeles respecto al Ecuador y al Meridiano de

Greenwich.

5.5.4.3. Cambio de Ejes Coordenados

En este proceso se tratarán los dos elementos restantes del

posicionamiento: la localización y la orientación. Ambos elementos pueden ser

fácilmente incluidos en la conversión a las coordenadas respecto a la imagen

aplicando a las coordenadas respecto a paralelos y meridianos una matriz de

transformación.

Los elementos de esta matriz son calculados durante el posicionamiento.

X e Y son las coordenadas de la intersección del Ecuador con el Meridiano de

Greenwich respecto al mapa, medidas en píxeles. Alfa es el ángulo existente

entre la dirección Norte y la vertical del mapa. Esta matriz introduce otra

modificación más en el sistema de coordenadas. El sistema de coordenadas

102


que se le introduce a la matriz es natural, es decir, x crece hacia la derecha del

centro de coordenadas e y crece hacia arriba. Pero las coordenadas de una

imagen de bits están definidas con un sistema de coordenadas cuya y crece

hacia abajo. Por tanto, al emplear esta matriz también se invierte el eje y. Al

realizar esta conversión se obtendrán finalmente las coordenadas en píxeles

respecto a la esquina superior izquierda de la imagen, y se podrá así

representar la ubicación actual del usuario.

103


5.5.5. Fallo a Mayor escala

Al emplear proyección Mercator en los cálculos, se está introduciendo

una deformación sobre el mapa. Esta deformación es despreciable cuando se

está trabajando a baja escala, pero conforme aumenta la superficie cubierta por

el mapa, la imprecisión puede dar lugar a fallos de localización considerables.

La deformación es introducida debido a que se considera que la longitud

de los grados longitudinales se mantiene constante. Pero realmente, varía

conforme el punto de observación se desplaza en latitud. Esta variación es más

pronunciada conforme el punto de observación se aleja del Ecuador. La

imprecisión se ve reflejada en el mapa en tanto que se determinan las

coordenadas de puntos situados a una mayor distancia longitudinal del

meridiano central del mapa.

Combinando estos fenómenos, se puede determinar que existe un factor

de imprecisión que es el resultado de una función compleja que crece con la

latitud absoluta a la que se encuentra el paralelo central del mapa, y con la

latitud relativa que el punto observado se encuentra respecto al paralelo

central. Este factor de imprecisión implica un desplazamiento del punto real

proporcional a la latitud relativa, con un factor de proporción, es decir, una

pendiente, que varía con la latitud absoluta. Aunque esta variación no es lineal

sino el resultado de una función más compleja, la función que indica el factor

104


de desvío adopta de todos modos una estructura de Saddle Point, es decir, de

silla de caballo, como se puede ver en esta gráfica.

La altura de la superficie representa el desplazamiento positivo o

negativo insertado por la deformación, según varía con la latitud a la que se

encuentra el mapa desde -90º a 90º del paralelo central al Ecuador y la latitud

relativa desde -90º a 90º del punto observado respecto al paralelo central del

mapa. Las áreas planas de valor cero que se pueden observar en las esquinas

de la gráfica son valores que la función no puede adquirir, al tratarse de puntos

situados más allá de +-90º de latitud, es decir, más al Norte del Polo Norte o

105


más al Sur del Polo Sur. El factor de imprecisión insertado, no obstante, es más

sencillo de observar como el valor absoluto del desplazamiento.

En este grafico se pueden observar con claridad que los puntos de

mínima imprecisión son aquellos en los que la latitud relativa es mínima, y este

efecto se ve más pronunciado conforme aumenta la latitud absoluta. También

se puede apreciar que la única área donde la imprecisión se mantiene nula es

en la línea en la que la latitud relativa es cero, es decir, el paralelo central.

El desplazamiento del punto propiamente dicho aumenta de forma

proporcional a su distancia longitudinal al meridiano central del mapa como una

función lineal cuya pendiente es el factor de imprecisión.

106


La única imprecisión introducida es longitudinal, representando un

desplazamiento sobre el paralelo, es decir, en dirección Este-Oeste, del punto

calculado respecto al punto real. El punto calculado se desplaza alejándose del

meridiano central si se encuentra entre el paralelo central y los polos, puesto

que se está considerando los grados de longitud más largos de lo que

realmente son, y acercándose al meridiano central si el punto observado se

encuentra entre el Ecuador y el paralelo central, al darse el caso inverso.

Debido a que la latitud se mantiene constante, el punto calculado nunca

se desplazará sobre los meridianos, en dirección Norte-Sur, respecto al punto

real. Realmente, debido a que la Tierra no es una esfera perfecta sino que está

ligeramente achatada en los polos, se está introduciendo una ligera imprecisión

conforme el punto observado se aleja del Ecuador. Esta imprecisión es

proporcional a la latitud absoluta en la que se encuentre el punto observado.

No obstante, se considera que esta imprecisión es insignificante y que se

puede considerar la Tierra como una esfera perfecta. Por ello, esta imprecisión

no se tiene en cuenta en el cálculo del grado de imprecisión introducido.

De estos cálculos se puede determinar que la imprecisión introducida en

un determinado mapa es proporcional a la distancia que separa el mapa del

ecuador y de la diferencia de longitud y latitud máxima que puede producirse

en el mapa, lo que viene directamente indicado por el tamaño del mapa.

Combinando estos dos factores es posible hacerse una idea de cual será la

107


deformación máxima que aparecería en un mapa cuadrado dependiendo de su

superficie y latitud.

En esta gráfica se puede apreciar que la imprecisión se incrementa con

el tamaño del mapa y con la latitud del paralelo central de modo casi lineal, con

una pendiente muy pronunciada.

Pero, conforme la superficie representada en un mapa aumenta, es

razonable pensar que su tamaño real no varía de forma proporcional, lo que

significa que su resolución se reduce. Por ello, la gravedad absoluta de una

imprecisión una vez representada sobre el mapa pasa a ser menos

significativa.

108


Si se considera una imagen de un tamaño constante 400x400 px y se

valora la imprecisión como el número de píxeles que una aproximación se ha

desviado del punto correcto, es posible ver que la velocidad de crecimiento de

la grafica se reduce significativamente.

Empleando esta grafica es posible definir una serie de líneas en las que la

imprecisión relativa se mantiene constante conforme varían la escala del mapa

y su latitud absoluta. Así, si se asigna al mapa un tamaño constante que sea

probable en encontrar en mapas reales, y se define un umbral de error máximo

a partir del cual se considera que un mapa es inutilizable por parte del

programa, es posible definir una función dependiente de la escala y la latitud

del mapa. Los resultados que se calculen sobre mapas que se encuentren por

109


debajo de esta función producirán siempre una cantidad de imprecisión que

este por debajo del la imprecisión fijada como límite.

Imprecisión propia del mapa

Como se ha definido, en el proceso de aplanamiento de las coordenadas

reales sobre la esfera de la Tierra a las coordenadas del mapa plano sobre el

que se está trabajando se esta insertando una cierta cantidad de

desplazamiento generado por la deformación propia de la proyección. Sin

embargo, el mapa que se está empleando está deformado del mismo modo,

puesto que es igualmente la representación sobre un plano de una esfera. Por

esto, la deformación introducida en el cambio de coordenadas no debería ser

visible, es más, debería precisamente compensarse con la deformación

introducida por el propio mapa.

En efecto, el desplazamiento causado por la deformación que se ha

descrito se observa únicamente al comparar las coordenadas actuales contra la

propia esfera de la Tierra, una situación que nunca va a darse a lo largo del

funcionamiento de la aplicación.

Parece por tanto inútil la realización de estos cálculos para definir el

desplazamiento generado por el punto analizado pues este desplazamiento no

se manifiesta contra el mapa, y la aplicación debería poder por ello funcionando

con mapas situados a cualquier latitud y de cualquier escala. Pero este

fenómeno de anulación de la deformación introducida por la conversión de

110


coordenadas solo se da cuando el mapa analizado ha sido generado mediante

la misma proyección que la empleada para la conversión de coordenadas, la

proyección Mercator, y ésta además está basada en los mismos meridianos y

paralelos centrales.

Cuando se emplee un mapa que no siga estos parámetros, en el

proceso de conversión aparecerán dos fuentes de imprecisión; la deformación

generada por la conversión como se ha descrito y la deformación e imprecisión

propias del mapa. La imprecisión del mapa no es posible calcularla porque será

distinta dependiendo de cada mapa, y como tal es imposible para la aplicación

controlarla. Podrá ser reducida, no obstante, empleando mapas precisos y

también mapas a baja escala. La imprecisión propia del proceso de conversión

si que es predecible, y gracias a ello es posible actuar a su respecto,

empleando mapas que se mantengan bajo la función de imprecisión que se

requiera.

Se ha elegido no emplear la función de desplazamiento para corregir la

deformación introducida por el proceso de conversión. Hacerlo implicaría

introducir una transformación a las coordenadas calculadas que si bien haría el

cálculo correcto respecto a las coordenadas reales de la Tierra, probablemente

introduciría un desplazamiento respecto al mapa empleado peor que el

introducido por la proyección. Además supondría añadir una serie de cálculos

adicionales de considerable complejidad al proceso de conversión de

coordenadas.

111


5.6. Limitaciones de la aplicación

5.6.1. Generación del Grafo de Rutas

5.6.1.1. Influencia del formato

Como parte de los objetivos y requisitos definidos al comienzo del

proyecto, se indicó que el proceso de análisis de la imagen del mapa de

carreteras debía producir un Grafo de Rutas correcto independientemente del

formato del mapa de carreteras. Con este requisito no se quería indicar tanto la

independencia del programa respecto al formato de la imagen analizada sino al

formato del propio mapa de carreteras. Es decir, los parámetros que

caracterizan el modo en el que representa las carreteras, como colores

elegidos para su representación, combinación con mapa físico, uso de

símbolos para representar elementos del mapa, presencia de texto, resolución

y calidad de la imagen.

El resultado real del análisis de la imagen no obstante se ve afectado por

estos parámetros. Esto es inevitable, pero se ha buscado reducir esta

influencia al mínimo y de dotar a la aplicación de la capacidad de modificar sus

parámetros de análisis para poder adaptarse a las características propias de

cada mapa y seguir produciendo resultados de calidad suficiente. En particular

se han observado varias fuentes de problemas asociadas al formato del mapa.

112


Problema Efecto SoluciónBaja calidad de color No se reconocen parte

de los colores de vías

como tales

Aumentar la pluma de

color en la configuración

Elementos de color

similar a las carreteras

Es posible que esos

elementos se confundan

con las carreteras

Reducir la pluma de

color

Vías definidas mediante

patrones en lugar de

colores

Puede ser difícil trazar

esas vías

Definir uno o más

colores del patrón como

víasPresencia de texto Puede interrumpir las

vías del mapa

Incrementar los radios

de refinadoTexto en el interior de

las vías

Causa un número de

cúmulos elevado

Reducir el Radio de

Centro, incrementar el

Radio de ConexiónCarreteras delgadas Partes de la carretera

puede no ser

reconocidas

Desactivar los filtros,

reducir los parámetros

de despeckle

5.6.1.2. Abstracción al grafo

En tanta medida como los problemas anteriormente descritos aparezcan

en la imagen original, esto se traducirá en diferentes problemas en el grafo de

113


rutas tras la aproximación. Estos problemas se pueden reducir a cuatro

fenómenos concretos:

Identificación de elementos que no son carreteras.

Este problema es principalmente causado debido a la aparición de

elementos que no son carreteras pero que tienen unas características,

principalmente color, que los hace similares a carreteras y lleva al programa a

confundirlos con carreteras. Esto puede llevar a problemas principalmente

durante la aproximación del grafo debido a que dichos elementos suelen

convertirse tras la abstracción en zonas altamente concentradas de nodos.

Esto puede llevar al desvío de puntos significativos que realmente pertenecen a

una carretera y que se encuentren dentro de estas zonas cuando se

concentren en puntos únicos durante la aproximación. También es posible que

una de estas zonas haga de puente conectando entre sí elementos que no

deberían estar conectados, ya sea de forma directa o durante la pasada del

algoritmo de conexión de nodos.

Perdida de carreteras.

Este problema aparece especialmente al tratar carreteras que están

representadas muy delgadas sobre el mapa, y especialmente en el caso de

114


que la calidad del color sea baja. El color de la carretera se confunde con el del

fondo, y cuando la carretera en si pasa el pretratado acaba convertida en un

camino de puntos y pequeñas líneas. Estos son borrados bien por parte de los

filtros o por parte del proceso de refinado del grafo.

En este mapa del área de Colorado es posible apreciar como las carreteras de

mayor grosor han sido percibidas sin problemas por el programa, pero que las

delgadas que se encuentran en el centro no se han visto representadas.

Aumentar la tolerancia de color hará más visible el color de la carretera

delgada, y eso permitirá que el proceso las incluya en el grafo. Es probable, no

obstante, que el proceso de conexión de nodos tenga que terminar de reparar

la carretera para que aparezca correctamente representada.

Cúmulos de Nodos

Estas estructuras problemáticas suelen aparecer sobre vías de

circulación sobre las que aparezca una cantidad elevada de texto. Este texto

115


causa que partas de la vía de circulación, que en un caso ideal seria una línea

continua, aparezcan como nubes de puntos, que a su vez se ven convertidas

en cúmulos de nodos tras la abstracción. También pueden aparecer debido a la

confusión de otros elementos con vías de circulación, en particular texto y

superficies.

Este es un caso en el que puede apreciarse el problema con claridad. El

motor de vectorización a tratado de ser fiel al trazado de las vías de circulación,

pero se ha visto severamente confundido por los nombres de las calles escritos

sobre estas. Al tratar de seguir el trazado alrededor del texto, los cúmulos han

aparecido.

Fallo de Conexión

Este problema es el único de los que pueden aparecer en esta fase que

no es una secuela del formato del mapa. El principal componente del grafo,

116


particularmente mientras está siendo generado, son sus nodos. Dos arcos

están conectados entre sí a través de un nodo si se da uno de tres escenarios.

Primero, que fueran identificados como pertenecientes al mismo nodo durante

la abstracción, lo cual ocurre cuando ambos son parte del mismo spline.

Segundo, que ambas este conectadas a nodos que este lo bastante cerca para

ser fundidos en uno solo durante la abstracción. Y tercero, que uno de los dos

arcos haya sido generado por parte del algoritmo de conexión de nodos. Todos

estos sistemas de conexión requieren que ya haya un nodo en el punto donde

se va a establecer la conexión. Debido a esto es posible que una vía de

circulación cuyo trazado es lo suficientemente simple como para ser

representada sin necesidad de emplear más de una curva no presente nodos

en puntos donde harían falta para establecer en ellos una conexión con otra vía

de circulación que existe en el mapa real.

Este es un mapa sin texto de la zona de Alberto Aguilera. Debido a la

simplicidad de las calles, que son solo líneas rectas sin obstáculos en ellas, al

haber sido quitado el texto, este es un mapa donde puede aparecer este tipo

de problema.

117


En todo el mapa, no obstante, solo ha aparecido uno de esos problemas.

Esto es una indicación de lo improbable que es su ocurrencia. La mejor

solución en este caso particular posiblemente sería añadir el cruce a mano

mediante el Editor de Grafo.

La probabilidad de aparición de este problema es como se ve

considerablemente baja. Esto es debido a que se ha dado a los parámetros de

vectorización de AutoTrace con unos valores que fuerzan al motor a ajustar las

curvas a la realidad con una gran precisión. Por tanto la posibilidad de que

decida emplear una sola curva para representar un tramo que presenta una

intersección es muy baja. Para eliminarlo completamente es posible forzar aún

más el ajuste por ejemplo, reduciendo el Error Threshold, pero eso

incrementaría sensiblemente la complejidad del grafo resultante. Los

parámetros de vectorización definido como predeterminados ya ajustan el

trazado del plano a un nivel suficiente como para que este problema no se

presente.

118


5.6.1.3. Refinado

En el proceso de refinado es donde lo errores de interpretación definidos

con anterioridad realmente se manifiestan y causan problemas en el grafo

resultado. También es la fase sobre la cual se tiene más control en tiempo de

ejecución al modificar los valores de sus parámetros.

La principal fuente de problemas es la aproximación de los cúmulos de

nodos. En este proceso se están convirtiendo grupos de nodos, que pueden

ser considerablemente grandes en número en un único nodo que presenta

todas las conexiones que el cúmulo tenía con el exterior.

La longitud de los arcos que conectaban los nodos del cúmulo con otros

nodos y a continuación pasan a conectar con el núcleo no es modificada, pero

sus extremos las coordenadas de sus extremos cambian. Este efecto se ve

maximizado si ambos extremos de un arco están dentro de cúmulos de nodos.

Esto no es una limitación severa a las capacidades del grafo porque aún en

este caso el desplazamiento que se sufre es solo de unos pocos píxeles, y las

rutas mínimas que normalmente pasasen por el nodo antes de la aproximación

seguirán pasando por el nodo, pero aún así genera una incorrección en el

cálculo de la longitud total de la ruta mínima.

La modificación de las coordenadas de los extremos mueve el arco

sobre el plano del grafo, lo que normalmente reducirá el nivel de ajuste del arco

al trazado original. Esto puede causar problemas en la presentación de las

119


rutas mínimas, desde un simple empeoramiento estético, por ejemplo al hacer

que un arco vaya a través de la esquina de una manzana en un mapa

metropolitano, a situaciones en las que sea confuso cual es la ruta que debe

tomar el usuario, especialmente en mapas particularmente complejos.

Un caso extremo de desplazamiento de las coordenadas de los arcos

durante la aproximación es el denominado “efecto estrella”, en el que el grafo

calculado está dominado por zonas vacías de nodos excepto en su centro, en

el que hay un único nodo, el resultado de una aproximación, del que salen

multitud de arcos a los nodos de su entorno, dándole el aspecto de una

estrella. Un grafo donde se dé este problema es definitivamente inusable y la

mejor aproximación al problema es directamente descartarlo y volver a

generarlo. Este problema es señal de que se han optado por unos valores de

Radio de Nodo y especialmente de Radio de Centro excesivamente elevados y

convendrá reducirlos en la próxima generación.

120


En este grafo generado a partir de un mapa de la zona de Alberto

Aguilera se puede apreciar de inmediato el efecto estrella en varios nodos que

han sido el resultado de la agrupación de un cúmulo. Como ya se ha

comentado, los mapas de ciudad tienden a ser especialmente vulnerables a la

aparición de cúmulos de nodos. Si además en uno de ellos se emplean valores

excesivamente elevados en los parámetros de Radio de Nodo y Radio de

Centro, el efecto estrella aparecerá en un grado elevado.

El problema que puede introducir el algoritmo de conexión de nodos es

evidente. La aparición de arcos que no se corresponden con carreteras o

conexiones reales. Esto solo se va a producir, no obstante, en el caso de que el

valor de aproximación de los arcos sea excesivamente elevado. En el caso de

que haya nodos que deberían estar conectados tan separados entre sí como

para requerir un valor de Radio de Conexión excesivamente elevado lo mejor

que se puede hacer es reparar esas conexiones mediante el Editor de Grafo.

Activar la opción Conexión antes de Aproximación también puede resultar útil.

121


5.6.2. Problemas insertados por el uso de la proyección

Mercator

Se decidió que la proyección Mercator se emplease para realizar la

conversión entre los dos sistemas de coordenadas empleados en la aplicación

por ser la que mayor simplicidad de cálculo, especialmente desde un punto de

vista computacional, que proporciona. No obstante, su uso causa dos

problemas principales sobre el funcionamiento de la aplicación.

5.6.2.1. Imprecisión por deformación

Este problema está causado por el efecto de deformación característico

de la proyección Mercator, representando un cierto nivel de imprecisión

insertado en los mapas cuando estos representan una gran área, aunque esta

imprecisión no empieza a ser apreciable hasta que se alcanza una gran escala,

del nivel del que la tendría un mapa de toda Europa, por ejemplo. Este

problema también aparece en mapas que representan latitudes muy elevadas.

En términos generales, se puede considerar la imprecisión insertada como

exponencialmente proporcional, aunque con un ritmo muy reducido antes de

pasar los círculos polares, a la latitud del paralelo central del mapa y como

directamente proporcional al tamaño real del mapa. Esta deformación no

aparece sobre mapas generados por la propia proyección Mercator, al moverse

122


su deformación propia al mismo ritmo que la generada por la conversión. Este

grafico representa el índice de desplazamiento del punto observado respecto a

las coordenadas reales del punto.

Un pregunta a la que esto da lugar de inmediato es que, conociéndose el

valor y la función de crecimiento de la deformación con tanta precisión como

este grafico indica, ¿por qué no se ha empleado en el proceso de conversión

de coordenadas? La decisión de no aplicarlo es debido a dos motivos. Primero,

la deformación sólo es realmente significativa en mapas a muy gran escala, en

los que no se espera que haga un gran uso de la aplicación, y aquellos cuya

latitud esta situada por encima de los círculos polares, en los que de todos

modos no es que haya muchas carreteras. El segundo motivo es que esta

deformación únicamente se ve reflejada en mapas dibujados mediante otras

proyecciones, cada uno de los cuales a su vez añade una deformación propia.

La deformación descrita por la formula es la que la proyección inserta respecto

a la superficie real de la Tierra. De modo que aún si se corrigiese las

coordenadas del punto calculado seguirían apareciendo desviadas respecto a

las que realmente le corresponden sobre el mapa. Por ello resulta un cálculo

innecesario y considerablemente complejo que añadiría al proceso de

conversión de coordenadas una carga de cálculo considerable, especialmente

si se considera que debe realizarse sobre una plataforma PDA.

123


5.6.2.2. Mapas inutilizables

Con el propósito de simplificar la lógica del proceso de conversión de

coordenadas y de reducir la carga de operaciones matemáticas presentes en la

propia conversión y en el proceso de cálculo de los parámetros de conversión

se han introducido varias suposiciones sobre las características del mapa que

no obstante provocan que existan determinadas restricciones sobre los mapas

con los que el sistema puede trabajar.

Los problemas que hacen estos mapas inutilizables se presentan

únicamente al realizar el posicionamiento y por consiguiente también en el

proceso de conversión de coordenadas, pero no en ninguno de los otros

procesos del sistema. Eso significa que el algoritmo de cálculo de rutas

mínimas y la generación del Grafo de Rutas seguirán funcionando exactamente

igual que si estos elementos problemáticos no aparecieran en el mapa de

carreteras, debido a que internamente utilizan el sistema de coordenadas en

píxeles de la imagen, que no se ve en absoluto afectado por estas ocurrencias.

124


Mapas en otra proyección

Existe una amplia gama de sistemas de proyección geográfica, cada uno

de los cuales introduce su propia deformación al mapa de la Tierra. Cuando el

sistema trabaja sobre un mapa que tiene una escala lo suficientemente alta

como para que la deformación introducida por la conversión de coordenadas es

apreciable y que además haya sido generado por otro sistema de proyección

distinto, la deformación introducida por la proyección del mapa y la introducida

por la conversión de coordenadas se combinan causando un desplazamiento

imprevisible y doblemente grave. Para evitar esto, se recomienda directamente

evitar emplear mapas a escalas tan elevadas.

Mapas en los que aparece uno de los polos

Todas las proyecciones cilíndricas, incluyendo la proyección Mercator

tratan al Norte y al Sur como direcciones, no como puntos, que es lo que

realmente son. Un mapa en el cual aparezca uno de los polos no podrá haber

sido, por tanto, generado por una proyección cilíndrica. Pero, según se ha

comentado en el caso de mapas creados por otras proyecciones, esto no

debería suponer un problema si se trata de un mapa a una escala lo suficiente

baja. El problema es causado por otro motivo. Puesto que el sistema de

conversión de coordenadas esta desarrollado sobre un esquema cilíndrico,

trata al Norte y al Sur como direcciones en línea recta y no como puntos, por lo

125


que es incapaz de interpretar los mapas correctamente, dando resultados

absurdos. Esta limitación no se considera un problema grave, pues no se

espera que se vaya de hacer uso del programa en las áreas polares en las que

podría presentarse este problema, especialmente porque en estas áreas ni

siquiera hay carreteras que trazar.

Mapas localizados en el Antimeridiano de Greenwich

La proyección de la Tierra que emplea el sistema de coordenadas se

basa en un cilindro que a continuación se despliega siendo cortado por el

meridiano 180º o Antimeridiano de Greenwich de dando lugar a un rectángulo

centrado en la intersección del Ecuador con el Meridiano de Greenwich. Esto

tiene el efecto secundario de que el algoritmo de conversión no reconoce el

hecho de que el meridiano 180º W y el meridiano 180º E son el mismo, y por

ello no podrá trabajar adecuadamente sobre un mapa en el que aparezca el

meridiano 180º. No obstante, esta limitación solo se verá reflejada en el

funcionamiento del programa si se disponen los puntos de posicionamiento en

lados opuestos del meridiano, en cuyo caso el posicionamiento no funcionará

correctamente y los cálculos de conversión de coordenadas darán resultados

absurdos. En el caso de que ambos puntos estén situados en el mismo lado del

meridiano, el algoritmo de conversión de coordenadas será capaz de funcionar

correctamente con la conversión de puntos situados del mismo lado del

meridiano que los puntos de posicionamiento, pero no podrá posicionar

126


concretamente los del otro lado. Afortunadamente, el Antimeridiano de

Greenwich atraviesa únicamente algunas zonas despobladas de Siberia y el

Océano Pacifico, de modo que es improbable que el usuario requiera el análisis

de un mapa con este problema.

Mapas cuya ángulo de orientación es mayor de +-90º

Uno de los elementos que definen el posicionamiento de un mapa es su

orientación, definida como el ángulo formado entre una línea dibujada en el

mapa y la que representa sobre la superficie de la Tierra. No obstante, el valor

real de este ángulo nunca es empleado directamente en la conversión, sino

que lo son su seno y su coseno. Estos a su vez son calculados como

soluciones de un sistema de ecuaciones, con lo que el valor real de la

orientación nunca se calcula. Mediante el sistema de ecuaciones solo se

calcula el valor del seno, el valor del coseno se calcula en función del seno

según la formula:

cos α = sqrt(sen2 α)

Ésta fórmula sólo puede dar como resultado para el valor de coseno

valores positivos, al emplearse sólo la solución positiva de la ecuación. Los

ángulos superiores a +-90º se caracterizan por el valor de su coseno es

negativo. Como esto es imposible debido a la fórmula, un ángulo de orientación

superior dará lugar a resultados absurdos durante la conversión de

127


coordenadas. Este problema no se daría si se calculase el coseno también

como una solución del sistema de ecuaciones. Se ha decidido tomar el camino

que requería menos cálculos porque la única situación en la que se va a

presentar este problema es en mapas donde el Norte este colocado apuntando

hacia abajo en algún grado. En este tipo de mapas, la mejor solución es invertir

la imagen antes de emplearla. Esto permitirá emplear el mapa sin necesidad de

ninguna otra adaptación y la aplicación funcionará correctamente sobre él.

128


Capitulo 6 - Evaluación del proyecto

129


En el proceso de evaluación del sistema desarrollado se ha dividido el

funcionamiento de este en una serie de procesos y elementos independientes.

Los procesos que se han recogido en esta evolución son los más significativos

del desarrollo del proyecto y los que tiene el mayor grado de influencia sobre la

calidad de la aplicación desarrollada y de los resultados que esta proporciona.

6.1. Generación del Grafo de Rutas

La generación del grafo de rutas es una de los más importantes

procesos que ejecuta la aplicación, así como la principal tarea del Módulo

Vectorizador. De hecho, se podría considerar como la única tarea del módulo

Vectorizador, puesto que sus otros procesos, el Editor de Grafo y la generación

del documento XML están orientados a completar el grafo y guardarlo en un

formato manejable por el Módulo Enrutador.

Profesionalmente, estos grafos para la navegación mediante GPS se

generan a partir de mapas especialmente diseñados para ello, en ocasiones

incluso a partir de un trazado manual de las propias carreteras. Se involucra en

su creación a un equipo de varias personas y se obtiene un mapa que refleja

perfectamente la realidad preparado para ser usado directamente por un

dispositivo de navegación GPS.

130


El proceso de tratamiento de imagen empleado en el proyecto es,

evidentemente, más limitado. El proceso de creación del grafo de rutas

empleado por el programa se encuentra restringido en su funcionamiento

respecto a los procesos empleados profesionalmente en un gran número de

formas.

La intervención humana es mínima

Solo un individuo maneja el proceso, y no se esperan de él ningún

tipo de conocimientos de computación

El proceso no tiene ningún tipo de requisito de hardware o software

especial, aparte de la propia aplicación.

El proceso es capaz de reconocer vías de circulación sobre cualquier

mapa de carreteras, aunque no haya sido especialmente preparado

para ello.

El proceso da resultados en muy corto tiempo comparado con el

proceso profesional.

Como resultado de estas restricciones, el grafo generado es de peor

calidad que el que habría sido generado por una compañía profesional, lo que

haría a priori el uso de la aplicación para la obtención de mapas una peor

elección que la adquisición de los mapas proporcionados por una compañía

profesional, si solo se evalúan ambas opciones por sus resultados.

Pero el uso de la aplicación permite evitar los problemas asociados al

uso de mapas profesionales, tal y como se definió al hablar de la necesidad del

131


proyecto, y al tiempo proporciona un Grafo de Rutas lo suficientemente bueno

como para permitir una navegación fiable del mapa de carreteras. Además,

mediante el uso del Editor de Grafo se permite al usuario alterar el grafo según

sus necesidades, una capacidad que no se encuentra en los mapas

profesionales.

Teniendo en cuenta las restricciones introducidas sobre el proceso, se

puede afirmar que el grafo generado por el proceso alcanza el máximo nivel de

exactitud que se puede lograr sin violarlas. El módulo Vectorizador es una

simple aplicación que puede emplearse sobre un ordenador cualquiera, y que

puede producir un grafo representando un mapa de carreteras cualquiera en

cuestión de un par de minutos.

La intervención del usuario necesaria es en efecto mínima, pero al

mismo tiempo se le permite acceder a un mayor alto nivel, a través del Editor

de Grafo y de los parámetros de vectorización y refinado. Esto es útil para el

tratado de mapas particularmente complejos, y permite al usuario la inclusión

de vías de circulación y puntos significativos no representados. Intervenir

directamente en le procese de cualquiera de estos modos es intuitivo y sencillo

gracias a la facilidad de la interfaz empleada, de modo que el usuario sigue sin

necesitar conocimientos específicos para emplear la aplicación

132


6.2. Calcular Ruta de Mínimo Recorrido

Es el principal propósito del Módulo Enrutador y en cierto sentido, de

toda la aplicación. El propósito con el que se genera el grafo de rutas, a fin de

cuentas, es crear un grafo para que este proceso navegue por él, y el propósito

del posicionamiento es permitir extrapolar las entradas y resultados de los

cálculos de este proceso al mundo real.

Para lograr implementar un cálculo de rutas mínimas eficiente era

necesario el uso de un algoritmo de búsqueda heurística adecuado al problema

que se estaba estudiando y que fuera capaz de resolverlo de forma eficiente. El

algoritmo de búsqueda seleccionado, A*, cumple perfectamente con estos

requisitos. Al emplear técnicas de cálculo del camino óptimo y no solo de la

solución óptima, se adapta perfectamente a los requisitos del problema. La

función heurística, parte fundamental del algoritmo, también ha sido

adecuadamente escogida, y funciona de modo eficiente y eficaz.

La implantación en sí del algoritmo A* es plenamente satisfactoria. El

algoritmo funciona como se espera que haga, alcanza una solución, si existe,

en tiempo óptimo y devuelve la ruta de mínimo recorrido hasta el nodo destino

completa. También hay implantados mecanismos de control para permitir que

el algoritmo detecte cuando no existe ninguna ruta que lleve hasta el destino.

133


Una limitación importante que sufría A*, y que es propia de todos los

algoritmos de búsqueda es que solo es capaz de encontrar rutas mínimas entre

los nodos que tiene definidos en el grafo, y no entre dos puntos cualquiera que

al usuario le interesen. Esta limitación se ha resuelto añadiendo a la ruta

calculada, tanto en la representación como en el cálculo de longitud, dos

tramos que conectan los puntos que el usuario ha indicado con los nodos más

cercanos, de modo que el resultado es transparente al usuario.

134


6.3. Posicionamiento y Conversión de Coordenadas

Estos dos procesos suponen el principal peso matemático de la

aplicación. Aunque en toda la aplicación desarrollada se hace un uso

considerable de técnicas matemáticas básicas, el funcionamiento de esta área

de la aplicación requiere del uso de funciones trigonométricas compuestas y de

cambios de ejes coordenados. Estas funciones además requieren de

interacción con el dispositivo GPS, lo cual significa que tendrán que ejecutarse

sobre la PDA.

Es necesario que la operaciones matemáticas de estos procesos sean lo

más eficientes posible para que se ejecuten en la plataforma PDA sin

problemas.

El posicionamiento del mapa tiene operaciones considerablemente

complejas, pero solo se ejecuta una vez, y sus resultados quedan guardados

en el documento XML del grafo. Debido a esto la eficiencia en este proceso es

menos importante. Se ha decidido sacrificar eficiencia en este proceso para así

maximizar la de la conversión de coordenadas.

Las funciones de conversión de coordenadas, por su parte, se han

hecho mucho más simples puesto que se estarán utilizando frecuentemente.

Las funciones de conversión únicamente emplean en su funcionamiento

productos y sumas con los factores calculados en el posicionamiento. Puesto

135


que estos factores se guardan en el documento XML y no requieren de ninguna

conversión para ser utilizados de nuevo, es posible ejecutar la conversión de

coordenadas en cualquier momento sin necesidad de hacer ninguna operación

más compleja que aritmética básica.

136


Capitulo 7 - Conclusiones

137


El propósito inicial del proyecto que se ha desarrollado era la creación de

una aplicación para una plataforma PDA que pudiera proporcionar funciones

similares a las de un programa comercial de autorouting, esto es, cálculo de

rutas entre puntos e interacción con el dispositivo GPS de la PDA. Estas

funciones se ejecutarían empleando como base un mapa de carreteras

perfectamente normal, es decir, que no estuviera preparado para su uso en un

programa de autorouting, que se encontrase en un simple formato de imagen

ráster cualquiera, como BMP.

La necesidad de este proyecto surge por el hecho de que aunque

actualmente el sistema GPS proporciona una cobertura global y constante, el

porcentaje del mundo que dispone de mapas preparados para aprovechar las

ventajas que proporciona, y que sean capaces de cubrir todas las necesidades

del usuario es extremadamente bajo. Esto es especialmente cierto si se

compara el número de mapas preparados para esa tecnología existente con el

de los mapas de carreteras no preparados para su uso por parte de esa

tecnología pero a los que el usuario tiene fácilmente a su alcance a través de

Internet, publicaciones en formato digital de las diferentes compañías

dedicadas a guías de carreteras y similares, escaneo de mapas de carreteras

que ya posea, etcétera.

Como resultado, se puede afirmar que en cualquier momento, el usuario

de uno de estos mapas tiene a su alcance un mapa de carreteras que, de estar

preparado para su uso por parte de un dispositivo GPS, cubriría sus

138


necesidades en un mayor grado que el de cualquier mapa desarrollado

especialmente para GPS del mismo área, en caso de que siquiera exista un

mapa que abarque la zona que se requiere.

El propósito del proyecto es, por tanto, permitir al usuario aprovechar las

capacidades proporcionadas por un dispositivo de navegación GPS con

cualquier mapa que posea independientemente de que no haya sido

desarrollado para ello, y proporcionar funciones de cálculo de rutas mínimas

sobre esos mapas.

Siguiendo esta definición, es posible ver que existen dos tareas

funcionales fundamentales a desarrollar:

Analizar el mapa para detectar como están dispuestas y cual es la

longitud de las diferentes vías de circulación representadas en el mapa. Con

esta información se generará un Grafo de Rutas como una abstracción de

estos datos y sobre el se podrá implantar un algoritmo de búsqueda heurística.

Sobre éste Grafo de Rutas, calcular mediante el uso de un algoritmo de

búsqueda heurística rutas de mínimo recorrido entre cualesquiera dos puntos

del mapa definidos por el usuario, mostrando como resultado el trazado y la

longitud de la ruta calculada.

Además, la aplicación debe interactuar con el dispositivo GPS la

realización de sus funciones, pudiendo proporcionar al usuario datos sobre sus

139


coordenadas actuales, y pudiendo emplear estas como puntos de comienzo y

fin en los cálculos de rutas mínimas.

Estas dos funcionalidades fundamentales han sido a su vez implantadas

en dos módulos distintos en el sistema.

El Módulo Vectorizador realiza las funciones de tratamiento de la imagen

del mapa de carreteras para extraer de ella, una vez la ha transformado a un

formato vectorial fácilmente manejable, los datos que necesita para construir el

Grafo de Rutas. Una vez creado, también es capaz de editar sus

características a través de un editor integrado. Finalmente, el módulo almacena

los datos necesarios para construir el Grafo de Rutas en un archivo XML que

será la entrada del otro módulo. El módulo Vectorizador está desarrollado para

una plataforma PC debido a que sus funciones tienen unos requisitos de

memoria y capacidad de proceso demasiado elevados como para implantarlos

sobre una plataforma PDA.

El Módulo Enrutador emplea el grafo generado por el Módulo

Vectorizador en combinación con el algoritmo de búsqueda heurística A* para

calcular la ruta de mínimo recorrido entre los dos puntos que le indique el

usuario. También interactúa con el dispositivo GPS para determinar la posición

actual sobre el mapa y a continuación mostrarla o emplearla como origen o

destino del cálculo de una ruta mínima. Para poder emplear esta funcionalidad,

es necesario antes de ello realizar el proceso de posicionamiento. El

posicionamiento se realiza indicando las coordenadas reales sobre el mundo

140


de varios puntos del mapa. Mediante estos puntos el sistema es capaz de

calcular el lugar en el que se encuentra el mapa (localización), la posición en la

que se encuentra (orientación) y la superficie que cubre (escala). El Módulo

Enrutador esta desarrollado para una plataforma PDA (concretamente una

plataforma PocketPC 2002 o superior) debido a que es únicamente en este tipo

de plataforma donde la capacidad de calcular rutas mínimas de inmediato es

realmente útil, y para poder interactuar con su dispositivo GPS en la realización

de su funciones.

141


7. 1. Cumplimiento de los Objetivos

El concepto original del proyecto y el objetivo central definido a su

comienzo se han cumplido con éxito: El sistema es capaz tomar una imagen en

un formato ráster, vectorizarla, analizar los resultados, crear un grafo de rutas

representante de las vías de circulación representadas en el mapa, calcular

rutas mínimas sobre ese grafo de rutas e interactuar con un dispositivo GPS

para el cumplimiento de sus funciones. Recorriendo los diferentes objetivos uno

por uno, es posible ver en que grado se han cumplido.

“La aplicación podrá tomar un archivo de imagen en cualquier

formato y será capaz de crear un Grafo de Rutas a partir únicamente de la

imagen, de modo que en él se detallen las distancias, trazado de la vía y

rutas entre los puntos significativos del mapa, y las coordenadas

geográficas de esos puntos.”

El objetivo se ha cumplido con total éxito. Puede parecer que, puesto

que se ha unificado la entrada de la aplicación como BMP, se está violando el

objetivo de aceptar cualquier formato, pero en este objetivo es importante notar

dos puntos de importancia. El primero es que con “cualquier formato” el

objetivo se está refiriendo principalmente al formato del mapa de carretera, es

decir, a los detalles intrínsecos del mapa como los colores elegidos para

142


representar las carreteras, la cantidad de texto en el mapa, etcétera Segundo,

el hecho de que el sistema únicamente acepte imágenes en formato BMP

como entrada no esta limitando en absoluto el rango de mapas que el usuario

puede emplear con el sistema. Esto es porque cualquier programa grafico

existente es capaz de convertir cualquier formato de imagen a BMP, y porque

probablemente la mayor parte de los mapas que el usuario posea ya se

encontrarán de hecho en formato BMP, especialmente si han resultado del

escaneo de mapas físicos.

Independientemente de cómo se considere la limitación de los formatos

de imagen, el punto principal del objetivo, que el sistema sea capaz de generar

un Grafo de Rutas con todas las capacidades que se describen en el objetivo a

partir únicamente de un mapa de carreteras ha sido cumplido de forma

completamente satisfactoria.

“El proceso de vectorización de la imagen deberá ser capaz de

diferenciar los tipos de vía presentes en el mapa. Así mismo, deberá

diferenciar estas de otros elementos del mapa que puedan causar

confusión, como ríos y otros elementos geográficos.”

Desgraciadamente, aunque las versiones iniciales del sistema eran

capaces de reconocer los diferentes tipos de vía observando únicamente su

color, se decidió retirar esta capacidad en versiones posteriores del sistema. El

143


principal motivo por el que se hizo esto fue porque los nuevos arcos que eran

introducidos en el Grafo de Rutas durante el proceso de vectorización y por

parte del Editor de Grafo del Módulo Vectorizador no tenían tipo asociado y

había que hacerlo manualmente. Puesto que el cálculo de rutas óptimas no

introducía ningún componente excesivamente interesante en el diseño del

proyecto, no era parte del concepto inicial y su resolución exigía una gran

cantidad de trabajo al usuario se decidió eliminar la característica por completo.

Esto permitió la posibilidad de que el pretratado convirtiera la imagen a dos

colores, descargando la carga de trabajo de AutoTrace que antes de aplicar

este cambio podía llegar a estar trabajando durante horas tratando de convertir

una imagen, simplificando considerablemente el código de lectura del fichero

SVG y produciendo resultados del grafo de rutas mucho más correctos y fieles

al mapa de carreteras original.

No obstante, el Módulo Vectorizador es perfectamente capaz de

reconocer las vías definidas por el usuario y de separarlas de ríos y otros

elementos que puedan llevar a confusión. Todos estos elementos, además, son

eliminados de la imagen analizada (pero no de la original) reduciendo

enormemente la carga de trabajo del sistema. De modo que, una vez retirada la

funcionalidad descartada del sistema, el objetivo se ha cumplido con éxito.

144


“El usuario podrá posicionar el mapa en el sistema de coordenadas

de latitud y longitud utilizado por el GPS simplemente definiendo las

coordenadas de varios puntos en el mapa. A partir de esto, el dispositivo

calculará todos los parámetros que pueda necesitar para realizar un

cambio de coordenadas entre los sistemas empleados por la aplicación, y

a partir de esos datos, calcular la localización del mapa, su orientación y

su escala. Conociendo esto, podrá calcular la longitud de los tramos de

vías de circulación, de las rutas calculadas por el sistema y las

coordenadas actuales del usuario sobre el mapa. Este proceso solo

necesitará ser realizado una vez, y el mapa recordara los resultados para

futuras ejecuciones.”

Este objetivo se ha cumplido completamente y con éxito. El usuario

únicamente tiene que definir los dos puntos de posicionamiento y el sistema de

inmediato calcula todos los parámetros que necesita para hacer sus funciones.

Estos parámetros pueden, así mismo, guardarse en el propio archivo del grafo

de rutas para su uso en futuras ejecuciones.

145


“El sistema podrá asignar pesos a los tipos de vía presentes en el

mapa identificados durante el análisis del mapa, de modo que favorezca

algunos, como las autopistas, sobre otros al calcular el recorrido óptimo.

El usuario podrá definir estos pesos a voluntad, o utilizar algún esquema

de pesos predeterminado.”

Como ya se ha mencionado, esta funcionalidad ha sido retirada

enteramente del sistema. Por ello, este objetivo fue cancelado y no esta

cubierto en absoluto

“Partiendo de estos datos, el sistema podrá calcular la ruta de

mínima distancia entre dos puntos cualesquiera del mapa, no solo los

definidos como puntos significativos durante el proceso de análisis, y a

continuación podrá mostrar esta ruta directamente sobre el mapa, e

indicara al usuario su longitud total.”

Este objetivo, otro de los principales del sistema también ha sido

completado en su totalidad con éxito.

146


7.2. Cumplimiento de los Requisitos

Aparte de los objetivos, se ha decidido revisar también el grado de

cumplimiento de los requisitos que fueron definidos al comienzo del proyecto.

Esto es debido a que se considera que los requisitos son en sentido otra forma

de objetivos.

“El sistema deberá estar implantado completamente sobre una

plataforma Pocket PC, y ser capaz de interactuar con el receptor GPS de

ésta durante la realización de sus funcionalidades. Esto se requiere para

así poder dar al usuario la capacidad de trabajar de modo inmediato con

cualquier mapa de carretera que se introduzca a la aplicación.”

Este requisito se violó en cuanto se decidió dividir el sistema en dos

módulos, uno de los cuales se desarrollo para una plataforma PC. Este

requisito, no obstante, fue formulado antes de conocer las posibilidades reales

de desarrollar todos los procesos de tratamiento de imagen en la plataforma

PDA. Esto es imposible por múltiples objetivos; Primero, no existe ningún motor

vectorización preparado para su funcionamiento sobre una plataforma PDA.

Como ya se ha mencionado, el desarrollo de un motor de vectorización propio

queda totalmente fuera del alcance del proyecto. De todos modos, tratar de

desarrollarlo sería una perdida de tiempo, pues una PDA es una plataforma

147


demasiado limitada como para albergar el proceso de vectorizado de la

imagen, proceso que tiene unos elevados requisitos de memoria y una gran

cantidad de operaciones matemáticas complejas. Aunque la vectorización en sí

no diera problema, el proceso de generación del grafo sigue teniendo unos

elevados requisitos de memoria, tanto en ejecución, debido al elevado número

de variables y objetos que utiliza, como fuera de ella debido al uso de varios

archivos temporales.

Las funcionalidades que al usuario realmente le hacen falta que estén

implantadas en la PDA, es decir, la interacción con el dispositivo GPS y el

cálculo de rutas mínimas están en efecto íntegramente localizadas en la PDA.

“La herramienta deberá estar orientada a un usuario al que no se le

supone ningún conocimiento sobre informática, funcionamiento de

dispositivos GPS, sistemas de navegación o tratamiento de imagen. Por

ello, su interfaz deberá ser intuitiva, sencilla y autoexplicativa, y el uso de

la aplicación deberá ser extremadamente sencillo, manteniendo todos los

procesos de tratamiento de la imagen y de interacción con el dispositivo

GPS transparentes al usuario.”

Se ha puesto un gran esfuerzo en cubrir este requisito, pues el propósito

de la aplicación es proporcionar con esta herramienta al público general, y

permitir que cualquiera pueda emplear sus mapas en formato ráster con su

148


sistema de navegación GPS, una tecnología que cada vez se está abriendo a

más gente.

Todos los procesos complejos que realiza el sistema son completamente

transparentes al usuario. De hecho, para emplear el Módulo Vectorizador solo

hay que abrir la imagen que se quiera convertir y pulsar el botón de

“Vectorizar”. El sistema muestra una barra de progreso mientras por detrás

realiza todas las operaciones por su cuenta. Si el usuario quiere meterse en la

configuración del proceso (aunque no hace ninguna falta, porque los valores

que la aplicación tiene por defecto han sido probados en múltiples ocasiones y

son lo han dado los mejores resultados en la mayoría de mapas de carreteras)

la propia ventana de configuración le muestra un texto de ayuda explicándole

cual es la función de cada valor. Una vez este satisfecho con el resultado,

solamente tiene que hace clic en “Guardar XML” y tendrá el archivo que pasar

al otro módulo. El proceso se completa con tres clics.

En el Módulo Enrutador también se han ocultado al usuario los procesos

del sistema. Para realizar la localización, una de las tareas más complejas del

sistema, le basta con hacer clic en el mapa y rellenar el formulario que aparece

con las coordenadas del punto. Le basta con hacer esto dos veces y ya a

definido la posición del mapa sobre la Tierra.

En suma, se puede considerar que este requisito ha sido completamente

cubierto.

149


Capitulo 8 - Planificación y Presupuesto

150


8.1. Planificación del Proyecto

El desarrollo de este proyecto comenzó en julio de 2005, después de

que, mediante la entrega del Anexo A, el proyecto quedara asignado de forma

definitiva. No obstante, el trabajo realizado antes de octubre de 2005 fue

bastante escaso, limitándose a un análisis del estado de arte de las tecnologías

existentes en el campo de la navegación GPS y en el aprendizaje de las

tecnologías que serían empleadas en el desarrollo del proyecto.

Por esto, se ha decidido definir en la planificación el inicio del proyecto

como octubre de 2005. El trabajo realizado hasta entonces puede ser

considerado despreciable desde el punto de vista de una empresa o

innecesario, puesto que se empleo tiempo en la adquisición de ciertos

conocimientos que ya serían poseídos por un programador analista profesional,

y en los que por tanto no se invertiría tiempo de desarrollo.

La fecha de finalización del proyecto está definida como 10 de julio de

2006, puesto que es en esa semana cuando el proyecto es presentado frente al

tribunal de revalida. Si se ignora el tiempo dedicado a la preparación de la

presentación y el que se ha dejado vacío antes de esto para la preparación de

los exámenes de la convocatoria de Junio y de Reválida, se puede definir la

fecha de finalización planificada del proyecto como el 15 de Junio de 2006.

151


A continuación se incluye un diagrama GAT detallando la EDT

(Estructura de División de Tareas) del proyecto, realizado con Microsoft Project.

152


8.2. Presupuesto del Proyecto

El presupuesto de un proyecto habitualmente se divide entre dos costes

principales: El coste de los recursos humanos que han trabajado en el

desarrollo del proyecto y el coste de las herramientas y recursos empleados en

su desarrollo

El coste de recursos humanos del proyecto desarrollado se limita al

trabajo de un único analista programador. Se ha estimado una media de 10

horas de trabajo semanales en el desarrollo del proyecto, que a lo largo de las

32 semanas dedicadas al desarrollo del proyecto ascienden a un total de 320

horas de trabajo por parte del analista programador.

Se ha considerado que el salario de un analista programador tipo sobre

el cual podría ser puesto el desarrollo de este proyecto asciende a 20 €/hora. El

coste de recursos humanos estimado, por tanto, asciende a 6400€ para la

totalidad del proyecto.

El coste de herramientas y recursos en que incurre el proyecto puede

considerarse prácticamente insignificante, puesto que explícitamente se ha

buscado el uso de recursos gratuitos y abiertos en el proyecto. Debido a esto,

el coste de herramientas se limita únicamente al entorno de desarrollo

empleado, en este caso Microsoft Visual Studio .NET 2003. Esta herramienta

probablemente ya se encontrará instalada en los equipos de desarrollo de la

153


empresa, de modo que no se puede considerar realmente como un coste del

proyecto. No obstante, el coste de este entorno en su versión Professional (la

que se emplearía para el desarrollo del proyecto) tiene un coste de 250€.

Puesto que solo se requiere que esté instalado en un único equipo de

desarrollo no es necesario incluir en esto el coste de licencias adicionales.

Combinando estos valores, se llega a la conclusión de que el coste total

estimado para el proyecto asciende a 6650€.

154


Capitulo 9 - Bibliografía

155


(OLIV04) - Transparencias de Técnicas de Búsqueda Heurística, José

Ángel Olivas Varela.

(WWWC) - Scalable Vector Graphics (SVG) 1.1 Specification, World

Wide Web Consortium. http://www.w3.org/TR/SVG11/

(WEIS99) - Spherical Trigonometry, Eric W. Weisstein. MathWorld

http://mathworld.wolfram.com/SphericalTrigonometry.html

(WEBE04) - AutoTrace Documentation, Martin Weber

(WIKI06) - Mercator Projection, Wikipedia.

http://en.wikipedia.org/wiki/Mercator_projection

(WIKI06) - Global Positioning System, Wikipedia.

http://en.wikipedia.org/wiki/GPS

156


Apéndice - Uso de la aplicación

157


A.1. Módulo de Vectorización

Para poder emplear un mapa de carreteras con el Módulo Enrutador,

antes es necesario someterlo a un proceso de tratamiento de imagen. Este

proceso generará un archivo .xml que será empleado para el calculo de rutas.

Este proceso es realizado por el Módulo Vectorizador

158


Para empezar a trabajar con un mapa de carreteras el primer paso es

abrir el archivo de imagen que lo contiene. Para ello, ir a Archivo Abrir

159


Aparece a continuación una ventana para abrir el archivo. Se selecciona

y se abre.

160


Con esto el mapa contenido en el archivo de imagen aparecerá en la

ventana principal de la aplicación. Para esta guía de uso se va a emplear como

ejemplo un mapa de calles de la zona de Alberto Aguilera, tomado

directamente del Callejero Web de Páginas Amarillas.

161


162


A continuación, se indican las vías de circulación presentes en el mapa.

Para ello basta con hacer clic en cada uno de los tipos de vía presentes. Al

hacer clic se abre una nueva ventana para confirmar el color seleccionado.

En este caso se ha señalado el color vainilla de la calle Princesa.

También abría que señalar el blanco empleado por las calles normales.

163


Una vez seleccionados los tipos de vía que son significativos para el

mapa que se está generando, ya se puede iniciar el proceso de vectorización.

Esto se hace seleccionando Archivo Vectorizar.

La vectorización es un proceso que puede llegar a durar varios minutos.

Durante este tiempo se abre una ventana de proceso indicando cuanto queda

de la transacción mediante una barra de progreso.

164


Una vez completado el proceso de vectorización es posible ver el grafo

generado mediante el menú Ver Mapa y Grafo

165


El grafo generado se muestra como una serie de puntos rojos (nodos)

conectados por líneas negras (arcos).

Este es el grafo generado. Parece excesivamente recargado, contiene

información redundante y en algunos puntos su trazado no es correcto. Es

posible reducir estos efectos y mejorar el aspecto y funcionalidad del grafo

alterando los parámetros de vectorización y refinado. No obstante, el grafo

generado seguirá siendo imperfecto hasta cierto punto, pues el único mapa que

166


puede generar un grafo que ignore la existencia de texto en las calles y otros

problemas es uno que no los presente.

Una vez que se esté satisfecho con el grafo generado, es el momento de

guardarlo como un fichero .xml. Para ello, primero se hace clic sobre Archivo

Guardar XML.

167


En la ventana que se abre se le da un nombre al fichero y se guarda.

Este es el proceso inmediato para generar directamente el grafo. Pero

es posible generarlo con un mayor de nivel de control sobre el proceso. Para

ello existen varios modos de actuar sobre el grafo antes y después de su

generación.

168


En la ventana de colores definidos se listan los colores que han sido

definidos sobre el mapa. No es posible añadirlos ni modificarlos desde aquí,

sino que el propósito de la lista es proporcionar la posibilidad de eliminar los

que se desee.

169


La ventana de configuración permite definir los diferentes parámetros de

vectorización y refinado para conseguir un resultado más limpio y correcto.

La pestaña izquierda, AutoTrace, contiene los atributos del proceso de

vectorización realizado por AutoTrace, también conocidos en este documento

como parámetros de vectorización. Al mover el ratón sobre los diferentes

parámetros aparece una descripción de su significado en el cuadro de abajo.

Esta pestaña también contiene la ruta de la carpeta principal de

AutoTrace, que contiene el ejecutable autotrace.exe que es empleado por la

aplicación. En caso de que la aplicación no tuviera acceso al archivo

autotrace.exe, le preguntaría al usuario su ruta durante el arranque del módulo.

170


La pestaña de la derecha, Vectorización, contiene otros parámetros

empleados durante el proceso de vectorización, incluyendo los parámetros de

refinado. Nuevamente, mover el ratón sobre los parámetros mostrará

descripciones de los mismo en la parte de debajo de la ventana.

171


La otra principal herramienta para alterar el grafo resultado es el Editor

de Grafo.

El Editor de Grafo permite hacer cualquier tipo de modificación al Grafo,

siendo capaz de añadir, mover y quitar tanto nodos como arcos. En el caso

particular de añadir un nodo, es capaz aplicar magnetismos para colocar el

nodo en un cierto arco, o atraer el arco para que pase por el nodo.

172


A1.2. Módulo Enrutador

La tarea para la que fue desarrollado este proyecto era el cálculo de

rutas mínimas. Empleando el fichero XML creado por el Módulo Vectorizador,

el Módulo Enrutador es capaz de realizar esta tarea.

Puesto que este módulo está desarrollado para una plataforma PDA, de

ahí es de donde provienen las capturas de pantalla empleadas en este

documento. Para poder hacer capturas de pantalla de la PDA se empleo una

aplicación de Microsoft, el Remote Display Control for Windows CE. Esta

aplicación añade su propia barra de titulo y menú característicos de Windows

XP, y que no pertenecen a la Módulo Enrutador

173


Para empezar a trabajar con el fichero de rutas y el mapa hace falta

abrirlos antes, mediante Principal Abrir

Primero se pedirá el archivo XML que contiene los datos del grafo de rutas

174


Y a continuación, se abre el archivo de imagen con el mapa de

carreteras. El archivo no es usado directamente por la aplicación, simplemente

se emplea para la interfaz de la aplicación.

Una vez abierto, se puede empezar a trabajar sobre la aplicación.

175


Puede interesar posicionar el mapa directamente para así poder

empezar a interactuar con el dispositivo GPS de inmediato, pero esto no es

necesario durante el desarrollo de sus funciones.

176


Para posicionar, primero se activa la función de posicionamiento

haciendo clic en Principal Posicionar

177


A continuación se hace clic en un punto cualquiera de la imagen, y la

aplicación preguntará las coordenadas geográficas del punto.

Si se marca la casilla Usar Localización Actual, el proceso empleará

como coordenadas del punto indicado las actuales del dispositivo.

Este proceso se debe realizar dos veces para proporcionar dos puntos

de referencia mediante los cuales posicionar.

Tras haber realizado el posicionamiento, es posible almacenarlo en el

fichero XML del grafo empleado por el mapa para así no tener que realizar el

proceso de nuevo. Esto se realiza con la opción Principal Guardar Posición.

178


Para realizar el cálculo de rutas mínimas primero se deben de identificar

el origen y el destino de la futura ruta.

179


Tras activar la tarea Ruta Mínima Desde..., hacer clic en el mapa

colocará un punto de color rojo marcando el inicio de la ruta. Este clic se puede

hacer varias veces, cambiando el origen cada vez. Utilizando la función Ruta

Mínima Desde Actual se define como punto de origen el punto actual en el

que se encuentra el dispositivo.

180


Las opciones Ruta Mínima Hasta... y Ruta Mínima Hasta Actual

funcionan de modo análogo, definiendo el destino con un punto verde.

181


Una vez origen y destino han sido calculados, hacer clic en Ruta Mínima

Calcular Ruta calculará y representará la ruta calculada.

182


Aquí, la longitud de la ruta aparece expresada en píxeles, puesto que el

mapa aún no ha sido posicionado, y por tanto se desconoce la proporción entre

píxeles y kilómetros. Si estuviera posicionado, la longitud aparecería

representada en kilómetros.

183


Por último, es posible para la aplicación indicar la posición actual del

dispositivo al usuario sobre el mapa haciendo clic en GPS Localización

Actual, siempre y cuando el mapa haya sido ya localizado.

184

Documentacion

Documents

Transcript of Documentacion