Identificador de zonas Arduino + GPS

Buenas a todos/as, amigos del foro. Estoy trabajando en un proyecto con GPS (Ublox NEO 6M), un arduino UNO y un display LCD 16x2. Lo que estoy queriendo lograr con estas tres cosas es lo siguiente, la ciudad donde vivo (en Bolivia) está dividida en distritos/zonas de variadas formas geométricas; con las coordenadas que me de el GPS quiero que mi Arduino me indique (en el LCD) en que zona me encuentro. La siguiente imagen representa el mapa de la ciudad para que se den una idea mas clara.

Mi problema es que no se como encarar la parte del reconocimiento de zonas; dado un par de coordenadas del GPS indicar por el LCD en que zona me encuentro, ya que cada paso que dé ya es una coordenada distinta, y si cruzo una frontera (entre zonas) que me indique ese cambio.

Seria sencillo definir mis límites de coordenadas si los distritos fuesen cuadrados o rectangulares, pero no es asi. No se si me deje entender.

La única solución bruta que se me vino a la cabeza es agrupar un conjunto de coordenadas por cada distrito, y empezar a compararlas con las del GPS; con la que coincida seria la zona en que me encuentro. Pero seria escribir demasiado código y llenaría rápido la memoria del arduino UNO.

Si alguien pudiese haber hecho algún trabajo parecido agradeceria una orientación o alguna idea a nivel de algoritmo para la implementación de mi código.

De antemano les agradezco por cualquier ayuda que puedan ofrecerme.

Saludos!!

Hice algo parecido hace muuuucho tiempo.... en Fortran, para mapear moléculas orgánicas. Los mapas son generalmente gráficos vectoriales, pero no creo que el arduino le de el cuero. La única forma es utilizar Matrices topologicas.
Divides tu mapa en una cuadriculas de N x N elementos y construyes una matriz de n x n elementos, en cada punto (por ejemplo el punto (2,1) de tu matriz) colocas la topología, en tu caso el numero de departamento.
luego relacionas tus coordenadas con el valor devuelto de tu GPS y en todo momento sabes en el departamento que estas parado.
Como es obvio en problema de este planteamiento es que el tamaño de la matriz es proporcional a la resolución de la cuadricula. Si tienes necesidad de mucha definición deberías agregar algún dispositivo de almacenamiento para guardar submatrices con mayor definición y cargarlas según necesidad.

Saludos

No tenía ni idea pero tambien pensé en un mapa vectorial pero supuse que eso requiere mucha memoria y no quise opinar porque no es para Arduino en condiciones standard.
Vas a tener que buscarte una EEPROM externa y guardar todo ahi para las consultas.

Yo también había pensado en crear una cuadrícula, pero creo que se tendrían que hacer tantas comparaciones, que sería muy lento de respuesta con arduino.

carmeloco:
Yo también había pensado en crear una cuadrícula, pero creo que se tendrían que hacer tantas comparaciones, que sería muy lento de respuesta con arduino.

Por eso se utiliza una matriz ordenada, para no hacer comparaciones. Simplemente hay que relacionar la longitud con las columnas y la latitud con las filas.

PeterKantTropus, que genial, no se me habria ocurrido resolverlo con matrices, y ciertamente voy a necesitar una memoria externa para tener una buena resolución del mapa. Por lo pronto he estado programando mi solución a lo "bruto" como dije en el planteamiento de este tema, lo malo es que tengo muchos condicionales if-then-else anidados y un 80% de memoria del Arduino ocupado.

Intentaré probar la solución que me plantearon. ¡Muchas gracias!

Busca esta solución por el momento.
Arduino con capacidad USB para manejar un pendrive externo.
Si mal recuerdo Leonardo, Mega ADK, DUE.
Le agregas un pendrive, lo usas como elemento de almacenamiento de las matrices que sugiere PeterKanTropus y estas en camino.

O un módulo SD, que se puede usar en cualquier modelo.

Hola.
Se podría intentar hacer mediante algoritmo vectorial, pero primero deberíamos calcular cuánto espacio va a ocupar el mapa. Primero; establecer qué tipo de dato va a ser cada punto (x,y) de coordenada. Después, calcular el número total de vértices a guardar, que dependiendo del nivel de detalle puede ser muy variable. Si podemos meter todos los puntos necesarios en memoria, podríamos adaptar un algoritmo como el que aparece en esta página.

#define MIN(x,y) (x < y ? x : y)
#define MAX(x,y) (x > y ? x : y)
#define INSIDE 0
#define OUTSIDE 1

typedef struct {
	double x,y;
} Point;

int InsidePolygon(Point *polygon,int N,Point p)
{
	int counter = 0;
	int i;
	double xinters;
	Point p1,p2;

	p1 = polygon[0];
	for (i=1;i<=N;i++) {
		p2 = polygon[i % N];
		if (p.y > MIN(p1.y,p2.y)) {
			if (p.y <= MAX(p1.y,p2.y)) {
				if (p.x <= MAX(p1.x,p2.x)) {
					if (p1.y != p2.y) {
						xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;
						if (p1.x == p2.x || p.x <= xinters)
						counter++;
					}
				}
			}
		}
		p1 = p2;
	}

	if (counter % 2 == 0)
	return(Fuera);
	else
	return(Dentro);
}

Puedes usar una SD para guardar los puntos, creo que las cosas se van encaminando para tu proyecto.
Entre la idea de PeterKanTropus y la de Noter tienes dos muy buenas opciones.
La opción de Noter me quedó muy clara. La de Peter no termino de comprenderla pero solo por curiosidad.

Sin duda que se puede utilizar gráficos vectoriales, pero es la complejidad de los algoritmos de búsqueda y almacenamiento lo que lo hace difícil para implementar en el arduino, pero no imposible .

El caso es que no se puede utilizar un figura simple para representar un mapa, es obligatorio utilizar polilineas encerrando un área

Sin duda que es necesario almacenar menos datos y se tiene una representación precisa del problema.

En cambio la alternativa matricial obliga a almacenar mucho mas datos , pero es sencilla de implementar.

El problema queda representado por una matriz simple

0001000000000
0011111000000
0111111111000
0111112222220
0011112222200
0000112222200
0000022222000
0000222222000

La elección es complicarse con los algoritmos de almacenamiento y búsqueda o trabajar con una gran cantidad d datos.

Exactamente.
Yo personalmente utilizaría el método vectorial si me entran los polígonos en memoria flash. Si voy a tener que manejar dispositivo de almacenamiento externo me iría directo al método matricial.

3lios como hiciste la final nesesito ayuda porfa soy de Bolivia tambien