Hora de pensar: detectar adyacencias en un mapa

[dark_headhunter]

Hola amigos, en este caso no estoy interesado en líneas de código, sino en cómo vosotros plantearíais esto:

Dada uma imagem a negra y branco, limitada por negro (un mapa, las lineas en negro son las delimitaciones entre provincias)

¿Cómo detectaríais a adyacencia entre provincias? (dando por hecho que las lineas tienen un grosor en píxeles)

Para ilustraros, hablamos de un mapa de esta tipología:

http://imageshack.us/photo/my-images/192/mapkmz.jpg/

así pues, espero vuestra iluminación, un saludo:  

PD: Si queréis explicar algo mediante código, me vale c, c++,java c#... todo menos binario

[pucheto]

Se me ocurre una idea pero la tendria q programar para ver que tal anda...

*Conocer que pixels pertenecen a cada provincia es facil, se hace haciendo un BFS sobre la imagen y voy numerando cada provincia.

*Despues elegiria una cantidad de puntos al azar distintos para cada provincia... ( mientras mas mejor ).

*Y veria si trazando una recta  desde los puntos de una provincia, llamemosla P1, hacia todos los puntos de otra provincia P2.

*2 provincias son adyacentes si existe una linea negra en una recta que separe puntos de P1 con puntos de P2, sino es asi, existe alguna provincia entre medio de estas, por la recta que estoy tomando.

Igual no es un metodo exacto, habria q probarlo a ver si es bueno o no.

[pucheto]

estuve pensando un poco y el algoritmo que nombre tiene problemas en las esquinas... donde se junten mas de 2 provincias.

Aplicaria la primer idea y despues lo que haria seria escanear la imagen de manera secuencial, analizando un cachito de n*n pixels ( el n lo elijo de forma que un punto donde se junten varios limites entre adentro con un poco de su contorno para distinguir las provincias ).

[dark_headhunter]

Pienso al igual que tú, creo que la cosa es ir siguen las lineas rectas, de alguna manera considerar un anchura y relacionar la región que hay a la izquierda del pixel más a la izquierda, y a la derecha del pixel más a la derecha. El problema está, como bien dices cuando hay bifurcaciones en las regiones. Aun no lo tengo claro, pero quizá hubiese alguna manera de "detectar" esa situación...¿?