Entrades classificades amb: CAP

Mòdul generador de polígons de Voronoi (1/2)

En aquesta entrada es comentarà de forma extensa el nou mòdul del CCU “generador de polígons de Voronoi” des de el punt de vista del programador.

La funció d’aquesta nova aplicació serà la de poder generar zones d’influència per els diversos centres proveïdors de servei en Mataró, així com Escoles, CAPS, parades de bus etc. Aquest sistema s’implementarà amb un mètode geomètric anomenat Voronoi

Els diagrames de Voronoi són un dels mètodes d’interpolació més simples, basats en la distància euclidiana, sent especialment apropiada quan les dades són qualitatives. Es creen en unir els punts entre si, traçant les mediatrius dels segments d’unió. Les interseccions d’aquestes mediatrius determinen una sèrie de polígons en un espai bidimensional al voltant d’un conjunt de punts de control, de manera que dintre de cada polígon o regió la distància a un punt de control associat és sempre menor que a qualsevol altre punt de les altres regions.

Fig. 1. Exemple de diagrama de Voronoi

Algoritme utilitzat

Primer de tot és comentarà l’algoritme utilitzat per du a terme la nova aplicació, trobats a la pagina web de l’informàtic japonès Takashi Ohyam.

http://www.nirarebakun.com/voro/evoro.html

El programa final ha constat  d’una sèrie de mòduls i un formulari.

Fig. 2. Llistat de mòduls i formulari del projecte.

 

Formulari

Primer de tot s’ha creat el formulari, que serà la finestra que apareixerà una vegada pitgem per accedir al mòdul creat. El formulari el podem veure a continuació.

Fig. 3. Formulari de la aplicació creada.

Ara comentaré part per part els diferents desplegables i botons utilitzats en el formulari.

  • En el primer desplegable hem de seleccionar la classe d’entitat puntual sobre el qual volem crear els polígons de Voronoi.

Fig. 4. Desplegable per seleccionar l'entitat puntual.

Fig. 5. Codi relacionat amb el desplegable de selecció d'entitat puntual.

  • En el segon desplegable, haurem de seleccionar la classe d’entitat d’àrea que volem que limiti els polígons de Voronoi. En el nostre cas el terme municipal de Mataró.

Fig. 6. Desplegable per seleccionar l'àrea delimitant.

Fig. 7. Codi relacionat amb el desplegable de selecció d'àrea delimitant.

  • Per últim, seleccionarem la classe d’entitat de línia de sortida. És a dir, on volem que vagin a parar les línies o segments que formaran els polígons de Voronoi finals.

Fig. 8. Desplegable per seleccionar la sortida de les línies dels polígons.

Fig. 9. Codi relacionat amb el desplegable del desplegable de selecció de sortida.

  • Botó “calcular Voronoi”.

Aquest botó el que ens farà serà primerament carregar les dades seleccionades als                 quadres de diàleg del formulari, utilitzant la subrutina “Carregar_dades”.

Fig. 10. Botó calcular Voronoi.

Fig. 11. Codi que va darrere del botó "Calcular Voronoi".

I finalment executarà la subrutina Voronoi_mapa ( que conté l’algoritme ) i d’aquesta manera formarà els polígons desitjats. Aquesta subrutina serà comentada més endavant en l’explicació del mòdul voronoi_code.

  • Botó Sortir

El botó sortir, simplement seria per poder sortir de la aplicació en qualsevol moment.

Fig. 12. Botó sortir.

Fig. 13. Codi que va darrere del botó sortir.

Mòduls

Pel que fa als mòduls, comentaré els dos mòduls principals ( “Obtencio de coordenades”i “voronoi_code”) ja que la resta són creats de forma automàtica quan creem el Geomedia Comand Wizard, que seria el plug-in per tal de poder utilitzar l’aplicatiu VB en el geomedia (Explicat en l’annex II). Tot i que com es veurà més endavant també s’afegeixen algunes funcions necessàries en el mòdul “OperacionsGM”.

Mòdul Obtenció de coordenades

Aquest mòdul és essencial per poder passar al algoritme les coordenades de les diferents classes d’entitats puntuals o serveis sobre les quals haurà de crear les zones d’influència (polígons Voronoi).

El mòdul consta de la subrutina “proximitat”, que li entren els paràmetres rs, entitats.SelectedItem i entitats.ConnectionName procedents de la subrutina “carregar_dades” esmentada al formulari.

  • El primer pas per obtenir les coordenades és afegir a la taula de l’entitat puntual escollida per l’usuari les coordenades X Y d’aquesta. Això és codifica de la següent manera:

  • Generem un recordset afegint a la taula de l’entitat puntual escollida els atributs funcionals que s’han definit anteriorment (Xep, Yep). Un recordset és una estructura utilitzada en programació que permet emmagatzemar informació des d’una taula d’una base de dades.

 

  • Passem el resultat de la consulta (recordset) a una array per les X i per les Y.

  • Obtenim les coordenades en les variables X i Y, que seran utilitzades més endavant en el mòdul Voronoi_code, de cara al algoritme.

Modul Voronoi_code

Aquest mòdul consta bàsicament del algoritme i de subrutines i funcions d’ajuda per que es puguin crear els polígons de Voronoi sobre les coordenades de les classes d’entitats puntuals obtingudes gràcies al mòdul anterior.

La subrutina principal del mòdul és “voronoi_mapa”que podem veure comentada per part seguidament.

  • Primerament, definim les variables i recordsets necessaris per la utilització del programa.

  • Calculem els paràmetres ample i altura que seran utilitzats més endavant en l’algoritme.

  • Establim alguns recordsets necessaris i definim les noves variables utilitzades en l’algoritme. També cridem la funció “borrar_entitat”, que ens permetrà cada vegada que obrim el mòdul buidar la classe d’entitat de línia que he utilitzat per crear el Voronoi anterior.

  • Definim la variable NNN que determina el nombre d’entitats que te la classe d’entitat seleccionada. També  a última hora es van haver d’augmentar el número de posicions dels vectors utilitzats en l’algoritme, ja que en alguns casos on hi havien moltes entitats no acabava de completar l’algoritme per totes elles.

  • Comença l’algoritme amb el següent bucle, ens carrega en memòria totes les entitats en les coordenades corresponents, de cara a crear els polígons.

  • ad(i-1), rep el valor del mòdul de les coordenades X i Y de cada punt i l’utilitza alguns cops en l’algoritme


  • Cridem la subrutina “hSort” passant-li els paràmetres NN, ad, ax, ay calculats anteriorment.


  • Es va executant el gruix de l’algoritme (explicat en l’apartat algoritme i codi inicial) .

  • Finalment amb la funció  Inserta_linia es formen els segments dels polígons a partir d’un punt inicial i un punt final, on les coordenades dels punts serien respectivament x0= kx(k-1) y0= Ky(k-1) i les finals x=kx(k2-1) i y= Ky(k2-1).

Els segments resultants es guarden en un recorset anomenat “Recordset_linia”.

  • Per últim, haurem de mostrar el resultat aconseguit en el mapa i la llegenda

– Seleccionem l’estil de la línia i el nom que li volem posar al resultat.

– Introduïm la entrada de la llegenda en la primera posició

  • Per compilar l’arxiu el programa creat, haurem d’anar a Archivo> generar nomprojecte.dll com podem veure en la següent captura d’imatge. En cas, que no doni cap error de compilació se’ns haurà creat un arxiu ddl i estarà llest per carregar-ho al Geomedia.

Fig. 14. Generar.dll.

Cada vegada que s’hagin fet canvis en el programa, s’haurà de crear una nova dll, de cara a que els canvis sorgeixin efecte en el Geomedia. Com també haurà d’estar tancat el Geomedia Professional m’entres és realitza aquest procés, ja que en cas contrari donarà error.


 


 

 

 

 

 


 

 

Sobre el Graf de Trams de Carrer (GTC)

 

Tal com ja s’ha comentat en aquest bloc quan hem parlat del ‘Nou concepte de Zones d’Influència’, un element bàsic de la modelització dels desplaçaments a la ciutat de Mataró és el Graf de Trams de Carrer (GTC). Aquest graf està format per segments i nodes, cada segment és un tram de carrer (part del carrer entre cruïlles) i els nodes són precisament les cruïlles.

El GTC es pot obtenir de moltes maneres, però en resum hi ha dos orígens bàsics, ad­quirint-lo a una empresa especialitzada (com per exemple Navteq o  TomTom) , on s’inclouran informacions sobre els sentits de circulació en cada via i els girs prohibits i autoritzats en cada nus i moltes altres coses, o bé generant-lo nosaltres mateixos, aquí s’ha optat pel segon cas, més que res per que es vol estudiar més el desplaçament de vianants  que no pas el de vehicles i d’aquesta manera podem afegir i incloure en el GTC trams que no siguin vials de carrer, com ara camins de vianants dins de parcs o zones verdes i recorreguts específics de la gent que va a peu.

Des del punt de vista d’un SIG el GTC està format per un conjunt d’entitats, o classe d’entitat, segons la terminologia del GeoMedia, de tipus lineal, els segments del graf, i un conjunt d’entitats de tipus punt, els nodes. Aquestes entitats lineals han de ser total­ment connexes si es vol navegar al seu través, o sigui, no hi pot haver cap punt de des­connexió o discontinuïtat. També a part de les característiques geomètriques de cada classe d’entitat, línies i punts, cal que hi hagin uns atributs associats a cada element si­gui aquest segment o node.

Quins són aquests atributs?

En primer lloc hi ha d’haver un codi per a cada segment i un codi per a cada node aquests dos codis han d’estar relacionats, és a dir,  dins de cada segment hi ha d’haver informació d’entre quins dos nodes està definit aquell segment en concret, i això per a tots els segments, d’aquesta manera amb aquestes dues llistes la de segments amb els codis dels nodes dels extrems de cada segment i la dels nodes s’estableix la morfologia del graf i es podria calcular una ruta encara que no tinguéssim la imatge geomètrica precisa.

Un altre atribut que podem tenir dins de la taula de segments és sobre l’ orientació o sentit del tram, aquesta orientació és arbitrària i s’agafa en el moment de definir el graf, per tant ens cal saber quin és el node d’origen del tram i quin el node de final del tram, per tant aquests nodes extrems del tram no són qualssevol , un d’ells és des de on parteix el tram i l’altre és a on arriba.

Per la construcció del GTC utilitzem una eina del GeoMedia Transportation Manager que parteix d’una classe d’entitat lineal i ella mateixa et va guiant per acabar obtenint les dues classes d’entitat del graf, els segments i els nodes, automàticament és generen els camps: NodeId en la taula de nodes amb un codi per cada node, i els camps: EdgeId, FromNodeId, ToNodeId en la taula de segments, que ens indiquen el codi de segment, i des de quin node a quin altre node està definit el segment, respectivament. Aquests són els camps principals per la construcció del graf, després n’hi ha uns altres que anirem comentant a continuació. Vegeu a la figura 1 una part dels segments i els nodes del GTC amb els identificadors respectius.

Fig1. Segments i Nodes del GTC amb els codis de EdgeId (vermell) i NodeId (negre)

Si cliquem sobre del tram 1017 obtenim les informacions que es mostren a la figura 2, on es poden comprovar els valors dels atributs EdgeId, FromNodeId i ToNodeId i es pot veure que el tram 1017 efectivament va del node 836 fins al node 837 tal com es veu a la figura 1.

Fig2. Dades del Segment 1017

De la mateixa manera es pot comprovar que hi ha molts altres camps dins dels atributs del tram, fixem-nos de moment en els camps LENGTH i Cost i Cost_invers.

Per què volem el GTC?

Per a dues coses, en primer lloc per a navegar des d’un punt de la ciutat fins a un altre, aquesta navegació ens ha de portar al conjunt de segments concatenats que uneixin el punt inicial amb el punt final segons un determinat criteri d’optimització que podria ser minimitzant la distància o minimitzant alguna altra variable (a la figura 3 es mostren els trajectes a les 3 Escoles Bressol més properes des d’una adreça concreta de la ciutat)  i en segon lloc per desplegar a partir d’un punt el conjunt, ramificat en arbre, de trajectes fins a assolir una determinada distància màxima o un valor màxim d’un altre indicador (vegeu la figura 4)

Fig 3. Trajectes a les 3 Escoles Bressol més properes des d’un punt de la ciutat seguint el GTC. La variable a optimitzar és la distància.

A la figura 4 es pot veure aquesta construcció en arbre, seguin el GTC, a partir de l’entitat: Escola Bressol ‘Les Figueretes’ fins a una distància màxima de 250 m. Com es veu a la figura la progressió fins a assolir els 250 metres pot acabar en un punt entremig del tram.

Fig 4. Arbre corresponent a l’Escola Bressol ‘Les Figueretes’ sobre el GTC (segments i nodes) fins a una distància de 250 m.

Tant en el cas 1, camí o trajecte entre dos punts de la ciutat, com en el cas 2, arbre des­plegat sobre el GTC a partir d’un punt, s’ha utilitzat la distància, el camp LENGTH, de cada segment com a base dels càlculs, això vol dir el camí òptim de distància mínima entre dos punts o el desplegament per la xarxa de trams de carrer fins arribar a fer la distància fixada de 250 m.

Una altra possibilitat seria fer servir una altra variable a minimitzar quan volem definir un camí o a utilitzar quan volem definir un desplegament en arbre, aquesta variable se­ria la que tenim quantificada en els camps Cost i Cost_invers de cada tram. Així com la longitud del tram no depèn de si es recorre en un sentit  o en un altre, en canvi si es tre­balla amb una altra variable, com ara el temps de recorregut del tram, sí que depèn de les característiques específiques de cada tram, com ara el pendent, els obstacles i la ti­pologia (plataforma única, escales, etc.) i en aquest cas té sentit de tenir dos paràmetres per tram, per si es circula en el sentit definit del tram Cost o si es va en sentit contrari Cost_invers. Això pot donar lloc a diferències importants de recorregut o de conjunt de carrers a l’abast si es va de casa a l’Ambulatori o es torna de l’ambulatori, sobretot quan el terreny és accidentat, amb moltes pujades i baixades.

En resum, quan més acurada sigui la informació del GTC, i en concret de cada tram, més es podrà afinar en la cerca de recorreguts òptims i en la definició de les Zones d’Influència a través del graf. De la mateixa manera, la utilització de la variable temps com a funció de cost, ens dona una mesura molt més real de la proximitat o llunyania dels centres proveïdors de serveis al ciutadà però requereix de tenir un bon model de la velocitat en els desplaçaments.

Polígons de Voronoi

En aquest article es descriurà el funcionament dels polígons de Voronoi, una eina molt important a l’hora d’estudiar àrees d’influència.

Els polígons de Voronoi es basen en la distància euclidiana, i són molt apropiats quan les dades són qualitatives. Es tracta de fer una partició del pla, a partir d’uns punts que anomenarem punts generadors.

Aquesta partició del pla en regions té la peculiaritat de que des de qualsevol punt de dins d’una regió determinada, la distància al punt generador corresponent és sempre menor que la distància a qualsevol altre punt generador extern. Per tant, les fronteres de les regions són equidistants de dos o mes punts generadors.

Inicialment, aquest polígons van ser creats per l’anàlisi de dades meteorològiques, però avui en dia s’utilitzen també per determinar zones d’influència, que és el que s’explicarà en aquest article.

Els polígons de Voronoi serveixen per dividir un espai en un número determinat de regions. S’especifiquen un conjunt de punts (punts generadors) i quan es fa el diagrama, aquests queden dividits pels polígons, un punt en cada regió. Les regions s’anomenen cel·les o polígons de Voronoi.

Cada polígon correspon a l’àrea d’influència, per dir-ho d’alguna manera, del punt  que conté.

Primerament, crec que és interessant posar un exemple per entendre millor per a què serveixen els polígons:

Suposem el cas de que s s’està estudiant els centres d’atenció primària (CAP) del terme municipal de Mataró, i es vol construir un altre i no se sap on. Gràcies a les zones d’influència creades mitjançant els polígons de Voronoi, es podrà situar més o menys el nou CAP.

El programa que s’ha utilitzat, a més del Geomedia, ha sigut el Global Mapper.

Global Mapper és una potent aplicació que combina eines de tractament de dades espacials amb un accés a gran varietat de formats d’arxius. És molt útil com a complement del Geomedia.

Amb el Geomedia s’han exportat els caps com una única entitat, i el contorn de Mataró s’ha aconseguit agafant el perfil de la unió de totes les illes que formen Mataró.

Terme municipal amb els CAPS

Tots els arxius exportats són de tipus ShapeFile, per tal de que Global Mapper els reconegui i es pugui treballar amb ells.

Un cop es té el terme municipal de Mataró amb els CAPS, és hora de passar a l’acció, el procés és simple, i el resultat és molt satisfactori.

Primerament es selecciona tot i es crea el diagrama de Voronoi des del menú d’anàlisi.

Apareixerà una finestra en la que s’haurà d’indicar que es volen allargar els límits uns 4000 metres, això permetrà que, en cas de que el diagrama no arribi a tocar el perímetre de Mataró, aquest s’allargui fins a tocar-lo.

Allargar límits

Un cop allargats, només cal dir que el límit fins on s’allarguen els polígons és l’àrea contenidora, és a dir, el terme municipal de Mataró. Això es configura a partir del botó “Bounds” i seleccionant l’última opció. Per últim s’accepta per crear els polígons.

Limitar polígons

La imatge de Mataró amb els seus CAPS quedaria dividida pels polígons de Voronoi, hi hauria una cel·la per cada CAP.

Aquests polígons resultants, permeten veure l’àrea d’influència de cada CAP.

Polígons creats

Observant la imatge, es pot veure les divisions que corresponen a cada CAP, hi ha una concentració més elevada al centre urbà, degut a que la població és notablement més elevada.

El CAP de dalt a la dreta, el de Rocafonda-Palau, té molta zona d’influència, això és perquè la zona Nord de Mataró no està tant urbanitzada com la resta.

Segons la població, i el número de places de cada CAP, fent ús dels diagrames de Voronoi, es podria situar un futur CAP.