Estructuració topològica

Autor: Dr. Joan Nunes. Universitat Autònoma de Barcelona
Promotor: Institut Cartogràfic de Catalunya, 2013

 

L'estructuració topològica és el procés automàtic que permet generar l'estructura d'arcs i nodes del graf pla corresponent a qualsevol conjunt de línies i, en el cas que l'objectiu sigui obtenir polígons, formar els polígons a partir de reconèixer les seqüències d'arcs que formen els contorns tancats dels diferents polígons. En termes de model de dades espacial, l'estructuració topològica permet passar automàticament del model vectorial de dibuix o del model vectorial sense topologia al model vectorial topològic (vegeu model de dades vectorial).

L'estructuració topològica té avantatges importants en el procés de creació i validació de dades espacials vectorials. En primer lloc, permet independitzar el procés de dibuix o digitalització del procés de validació de les dades vectorials, ja que és capaç de generar sempre una estructura d'arcs i nodes a partir de qualsevol conjunt de línies. En segon lloc, permet detectar, automàticament els errors de connectivitat de línies existents en el conjunt de línies originals i,  per tant, serveix per a validar i depurar qualsevol digitalització. En tercer lloc, genera informació espacial addicional, de caràcter topològic (connectivitat entre línies i adjacència entre polígons), que s'afegeix a la informació geomètrica original i que pot ser utilitzada en diversos tipus d'anàlisis basades en les relacions topològiques, a més de servir per a validar la coherència espacial de les dades vectorials.

L'estructuració topològica és una funcionalitat característica del programari de SIG professional, o d'altes prestacions.

 

Estructuració topològica. a) conjunt de línies originals; b) topologia arc-node: conjunt de nodes i d'arcs (cada arc és límit només entre dos polígons; c) topologia polígon-arc: conjunt de nodes, d'arcs i de polígons formats com a seqüències d'arcs que comencen i acaben en un mateix node.

 

Origen

Els conceptes de topologia o de teoria de grafs aplicats a l'estructuració de les dades espacials de tipus vectorial s'introduïren en els sistemes d’informació geogràfica a mitjans de la dècada de 1960, precisament amb la finalitat de disposar d'una estructura de dades que permetés verificar la coherència espacial dels límits entre polígons adjacents en una partició de polígons o mosaic (Loomis, 1965; Cook, 1967).

Una de les primeres estructures de dades topològiques operatives en el camp de la informació geogràfica fou l'estructura de dades DIME, Dual Independent Map Encoding (Cooke and Maxfield, 1967), ideada entre 1965 i 1967 pel US Census Bureau per a enregistrar la definició espacial de la xarxa de carrers de les poblacions dels Estats Units, juntament amb altres línies de límit d'unitats censals, amb la finalitat de definir les àrees estadístiques del cens del 1970 (Smith, 1967). L'estructura de dades DIME utilitzava únicament segments rectes i enregistrava la topologia completa per a cada segment (node inicial i node final, i polígons a l'esquerra i a la dreta de cada segment), a més dels rangs d'adreces a cada costat del segment en el cas dels carrers. Les formes lineals més complexes es definien com a sèries de segments. El fet de basar-se en segments estrictes permetia una gran simplicitat i uniformitat d'emmagatzematge, ja que els elements gràfics es reduïen a dos vèrtexs (dos parells de coordenades), que alhora eren nodes, en tots els casos. La referència a dual independent en la denominació prové del fet que la codificació simultània de la topologia arc-node i de la topologia de polígons permet la verificació de la consistència de les dades per mitjà de dos procediments independents (mitjançant la connectivitat dels segments a través dels nodes i mitjançant la delimitació dels polígons resseguint els arcs).

La generalització dels principis topològics incorporats a l'estructura de dades DIME (Corbett, 1975) permeté a mitjans de la dècada de 1970 definir el model vectorial topològic (Peucker and Chrisman, 1975), aplicable tant a xarxes d'elements lineals com als límits dels polígons d'una partició de polígons, i que permet representar tot tipus de formes lineals, gràcies al fet d'emmagatzemar per un costat la geometria, mitjançant la llista de coordenades de cada arc, i per altre costat la topologia, mitjançant les referències dels nodes inicial i final i dels polígons esquerre i dret associats a cada arc. El pas d'una estructura simple, basada en segments, com DIME, que es pot codificar manualment, a una estructura apta per a qualsevol tipus d'elements lineals portaria a desenvolupar procediments per a generar automàticament l'estructura d'arcs i nodes a partir de qualsevol conjunt de línies.

Els primers algorismes d'estructuració topològica són també de mitjans de la dècada de 1970. Entre aquests destaquen els desenvolupats al Laboratory for Computer Graphics and Spatial Analysis de Harvard University, primer en el programa POLYVRT (White, 1977) i després en el programa ODYSSEY de finals de la dècada de 1970 (LCGSA, 1983), els quals posteriorment serien implementats en programes comercials de SIG com ArcInfo i altres a la dècada de 1980.

Definició

Establir la topologia arc-node d'un conjunt de línies consisteix a identificar i enregistrar explícitament el punt inicial i el punt final (nodes) de cada línia (arc), que també ha d'estar identificada individualment. En altres paraules, consisteix a explicitar i enregistrar el graf que formen el conjunt de línies, enteses, independentment de la seva forma, com a connexions (arcs) entre els punts inicial i final de cada línia (nodes).

Atès que la finalitat inicial de l'aplicació dels conceptes de la teoria de grafs als SIG fou poder representar els límits dels polígons que formen una partició de polígons disjunta i exhaustiva en el pla, a fi de poder verificar-ne la consistència, la topologia arc-node es defineix estrictament com un graf pla (és a dir, un graf en què tots els elements, arcs i nodes, pertanyen o estan en el mateix pla). Això obliga necessàriament a intersecar totes les línies originals, dividir-les en els punts d'intersecció, quan aquest no coincideix amb el punt inicial o final d'una línia original, i considerar el punt d'intersecció com un node, en tant que punt inicial o final de les noves línies (arcs) resultants de la intersecció. Dit d'un altra manera, en la topologia arc-node no hi pot haver línies que es creuïn a diferents nivells, en diferents plans, és a dir, sense intersecar-se, tal com correspon als límits d'un conjunt de polígons que divideixen exhaustivament (sense buits) un espai d'un mateix pla en àrees disjuntes (sense encavalcaments). Per aquest motiu, la topologia arc-node, i la topologia polígon-arc que en deriva, s'anomenen topologia plana (en anglès, planar topology) i el procés d'intersecció per a formar el graf pla constrenyiment planari (en anglès, planar enforcement). La conseqüència lògica del constrenyiment planar és que, a més de fer efectives totes les interseccions i dividir necessàriament les línies en els punts d'intersecció, les línies duplicades col·lapsen en un mateix arc. En el cas de línies parcialment duplicades, només col·lapsa la part duplicada, es crea una intersecció (node) i es divideixen les linies originals allà on deixen de coincidir.

Constrenyiment planar. a) dues línies que es creuen s''intersequen necessàriament i es divideixen en arcs a la intersecció; b) dues línies totalment duplicades col·lapsen en un mateix arc; c) dues línies parcialment duplicades col·lapsen en un mateix arc en la part duplicada i es divideixen a la intersecció en arcs corresponents a les parts no coincidents.

La topologia polígon-arc deriva de la topologia arc-node i consisteix a reconèixer explícitament els polígons situats respectivament a l'esquerra i a la dreta de cada arc, en el sentit determinat pel node inicial i pel node final de l'arc. Per aquest motiu, la topologia arc-node, a més de ser un graf pla és un graf orientat (és a dir, un graf en què els arcs tenen sentit, de manera que la connexió entre dos nodes reconeix explícitament l'inici i final, i no és necessàriament igual a la seva inversa). La informació de la topologia polígon-arc (polígon a l'esquerra i a la dreta de cada arc) permet definir i emmagatzemar els polígons per mitjà dels arcs, com a seqüències d'arcs connectats que formen contorns tancats (es a dir, que comencen i acaben en un mateix node) tot mantenint un polígon determinat en un mateix costat, segons el sentit dels arcs o invertint l'arc en cas necessari si ha estat dibuixar en sentit invers.

El procés d'estructuració topològica consisteix a generar la topologia arc-node per a un determinat conjunt de línies, representades vectorialment com a llistes de coordenades, resolent totes les interseccions existents en el conjunt de línies considerades en un mateix pla, dividint les línies originals en els punts d'intersecció quan aquests no coincideixin amb els punts inicials o finals de les línies originals, identificant de forma única cada arc i cada node, i identificant i enregistrant per a cada arc els seus nodes inicial i final.

Addicionalment, el procés d'estructuració topològica genera també la topologia polígon-arc a partir de la topologia arc-node i, encara que no és part del procés de creació de topologia, assigna també un atribut a cada polígon a partir dels punts d'etiqueta. Habitualment, els programes donen opció a triar si es desitja només topologia de línies (arc-node) o topologia de polígons (polígon-arc), que requereix també prèviament la de línies.

Cal remarcar, per últim, que l'estructuració topològica és un procés que, per poder generar la informació topològica del límit compartit entre arcs i del límit compartit entre polígons, crea nous elements espacials a partir dels elements (línies) originals, modificant aquells i construint-ne de nous d'acord amb les regles de la topologia plana. En el cas de la topologia arc-node genera nodes i arcs, i en el cas de la topologia polígon-arc, genera nodes, arcs i polígons. En aquest sentit, és un procediment de construcció d'elements espacials que es creen segons un conjunt de regles fix a partir d'elements originals arbitraris, de manera que compleixen aquestes regles per definició i, per tant, el mateix procés de creació n'és també el procés de validació.

L'estructuració topològica dóna lloc necessàriament a un nou conjunt de dades, a part del conjunt de dades original, ja que els elements originals i els estructurats no poden coexistir en un mateix conjunt de dades.

Procediment de càlcul

El procés d'estructuració topològica comprèn les fases de creació de la topologia arc-node, creació de la topologia polígon-arc i etiquetatge dels polígons. L'estructuració topològica de línies comprèn només la primera fase, mentre que l'estructuració de polígons comprèn totes tres fases. Les dades de partida del procés d'estructuració topològica són un conjunt de línies qualssevol, en el cas de l'estructuració topològica de línies, i un conjunt de línies i de punts d'etiqueta en el cas de l'estructuració topològica de polígons. Idealment l'etiquetatge de polígons hauria de ser opcional, ja que la identificació dels polígons és prèvia i independent a la identificació del punt d'etiqueta corresponent a cada polígon, de manera que seria opcional disposar o no de punts d'etiqueta a les dades de partida. A la pràctica, la majoria de programes obliguen a usar punts d'etiqueta en el procés d'estructuració topològica de polígons i alguns fins i tot emmagatzemen els punts d'etiqueta de manera permanent i els usen com a substitut per a accedir als polígons.

Creació de la topologia arc-node

La topologia arc-node és la topologia bàsica en el model de dades vectorial topològic. És obligada tant en el cas d'estructuració de línies com en el d'estructuració de polígons. El procediment de càlcul comprèn els següents passos:

• càlcul d’interseccions de línies 
• identificació de nodes (punts d’intersecció, i punts inicials i finals de les línies originals)
• divisió de línies en els nodes (punts d’intersecció)
• identificació d’arcs
• emmagatzematge de la topologia arc-node (node inicial i final de cada arc)
• marcatge dels nodes anòmals (nodes terminals i pseudonodes) 
• càlcul i emmagatzematge de la longitud dels arcs

Càlcul d’interseccions de línies

L'operació fonamental per a la creació de la topologia arc-node és el càlcul d'interseccions de línies (Douglas,1974; Little and Peucker, 1979; Lee and Preparata, 1984). La resta de passos es limiten a assignar un identificador numèric únic a cada node i arc generat, i a emmagatzemar aquesta informació, conforme es va produint.

La intersecció de línies és una operació estrictament geomètrica que es duu a terme mitjançant la resolució del sistema de dues equacions de primer grau corresponents als segments de recta que defineixen cada un dels parells de vèrtexs consecutius de les dues línies a intersecar, tot comprovant que el resultat de la intersecció es trobi comprès dins dels dos segments i no sigui un punt virtual resultat de la prolongació dels segments. Hi ha un cert nombre de casos particulars a tenir en compte per tal de no obtenir resultats incommensurables (divisió per zero), com és ara els casos de línies verticals o de línies paral·leles, però es tracta d'un procés de càlcul simple.

Càlcul d'intersecció de línies. Cas simple entre dos segments, sense tenir en compte línies verticals ni paral·leles.

La complexitat apareix quan el nombre de rectes a intersecar esdevé molt gran, tenint en compte que les formes de les línies poden ser molt elaborades (és a dir, contenir molts vèrtexs) i que dues línies es poden creuar múltiples vegades. Igualment cal tenir en compte que també s'han de calcular com a interseccions els casos en que el punt final d'una línia coincideix amb el punt final d'una altra línia (és a dir, dues línies ben connectades pels seus extrems durant el dibuix) o bé aquells en què el punt final d'una de les línies cau enmig d'un segment de l'altra línia sense coincidir amb cap vèrtex.

Aíxi, el nombre d'interseccions a resoldre esdevé realment molt gran. Si una línia consta de n vèrtexs i l'altra de m vèrtexs, el nombre de segments de recta de cada línia és respectivament n-1 i m-1, i per tant el nombre de sistemes d'equacions a resoldre per tal de detectar i calcular interseccions entre les dues línies és de (n-1) x (m-1), ja que idealment cada segment de cada línia s'ha de contrastar amb cada segment de l'altra línia. Comptant que el conjunt de línies original pot estar format per milers o desenes de milers de línies i que la forma de cada línia pot estar definida per centenars o milers de vèrtexs, el procés de càlcul d'interseccions és un procés realment intensiu en termes computacionals. Per accelerar el procés i evitar haver de contrastar cada segment de cada línia amb tots i cada un dels segments corresponents a la resta de línies, els programes utilitzen diverses estratègies. La majoria es basen en la comparació del rectangle envoltant mínim de cada línia amb els de la resta de línies, a fi de descartar el càlcul d'interseccions entre els parells de línies en què no hi ha encavalcament entre els respectius rectangles envoltants mínims, i successivament en la comparació dels rectangles envoltants mínims dels segments de les dues línies a fi d'anar descartant parells de segments i d'aïllar aquells en què cal fer el càlcul per detectar si realment hi ha intersecció. Juntament amb aquest procediment, s'apliquen altres mètodes per accelerar el càlcul, com és ara ordenar les línies i els segments en ordre decreixent segons la coordenada y i processar el càlcul per rangs de coordenades. Això estalvia haver de comparar tots els rectangles envoltants mínims, ja que només es comparen els que són dins del mateix rang de coordenades. També s'utilitza la descomposició de les línies a intersecar en seccions monòtones, creixents o decreixents en x o en y, ja que dues seccions monòtones pertanyents a dues línies diferents un cop s'han intersecat ja no poden tornar a intersecar.

Ús dels rectangles envoltants mínims per a accelerar el càlcul d'interseccions entre línies.

També s'utilitza la descomposició de les línies a intersecar en seccions monòtones, creixents o decreixents en x o en y, ja que dues seccions monòtones pertanyents a dues línies diferents un cop s'han intersecat ja no poden tornar a intersecar.

Un segon aspecte important a considerar en les operacions d'intersecció de línies és la necessitat de contemplar un cert marge d'incertesa, error o imprecisió en les coordenades dels vèrtexs de les línies que defineixen els segments de recta a intersecar. Aquest marge de fluctuació dels valors de les coordenades s'implementa per mitjà del concepte de tolerància, que és la distància mínima per sota de la qual dos punts es consideren iguals, i és especialment rellevant a l'hora de resoldre els casos de línies que connecten pels extrems o enmig d'un segment i també els casos de línies duplicades. Com que no es pot determinar a priori quins casos requereixen o no l'aplicació d'un cert valor de tolerància, el paràmetre de tolerància de correcció (fuzzy tolerance) s'aplica uniformement a les coordenades de tots els vèrtexs de totes les línies en les operacions d'intersecció durant el procés d'estructuració topològica, i la majoria de programes no admeten que el valor de la tolerància aplicada pugui ser zero ja que aleshores la simple discrepància en els decimals deguda a la representació digital dels números reals que expressen els valors de les coordenades originaria errors de manca de connectivitat. Aquesta aplicació uniforme d'un valor de tolerància no nul a tots els vèrtexs de totes les línies d'un conjunt de dades en el procés d'estructuració topològica o en les operacions posteriors de processament en què cal recalcular la topologia del resultat origina el concepte de banda èpsilon, o banda de Perkal o banda d'error, formulat per Perkal l'any 1966, que és una banda d'una certa amplada definida pel valor de la tolerància a l'entorn d'una línia per a tenir-ne en compte la imprecisió o incertesa de les coordenades com a conseqüència d'errors de dibuix o de limitacions de precisió dels aparells de digitalització o de la mateixa representació digital dels números reals, de manera que una línia passa a ser considerada una banda d'un cert gruix, la qual constitueix una representació més acurada o realista de la línia.

La tolerància de correcció aplicada durant el procés d'estructuració topològica permet resoldre petits errors de connectivitat comesos durant el procés de digitalització o de dibuix, com és ara línies inacabades (undershoots), línies sobrepassades (overshoots) o en general qualsevol discontinuïtat entre punts que provoca manca de connectivitat. Tanmateix el valor de tolerància aplicat no pot ser gaire alt, ja que la tolerància causa variació en la posició dels vèrtex i per tant un valor alt pot produir deformacions de les línies i generar errors topològics o artefactes pel fet de col·lapsar punts que haurien de ser diferents. Un valor de referència a no sobrepassar és 0,2 mm multiplicat pel factor d'escala de l'original digitalitzat o de l'escala de presentació apropiada del conjunt de dades (per exemple, en el cas d'una cartografia a escala 1:5000, el valor de tolerància màxima a aplicar seria d'1 m, expressat en les unitats de les coordenades del mapa digitalitzat). Aquest valor prové del fet que el traç més fi sobre un mapa en paper sol ser de 0,2 mm i per tant conservar punts més propers entre sí que el mateix gruix del traç que representa la línia no té sentit. Recíprocament, aquest valor no deformarà el dibuix digital de la línia ja que no eliminarà vèrtexs més pròxims entre si que el gruix del traç digitalitzat.

Hi ha diferents maneres d'aplicar el paràmetre de tolerància durant les operacions d'intersecció. La més simple és fer el promig entre les posicions dels punts que estan a una distància inferior al valor de tolerància. Altres implementacions permeten establir un criteri de prioritat, de manera que un dels punts manté la seva posició i és l'altre que s'ajusta i canvia la seva posició fent-la igual a la del punt que té la prioritat. En aquest cas, la tolerància es comporta com la tolerància d'ajust emprada durant el procés de dibuix. Els programes més sofisticats permeten establir diferents criteris de prioritat i diferents graus de prioritat.

Identificació d'arcs i nodes, i emmagatzematge de la topologia arc-node

Cada línia és numerada de forma preliminar, així com cada un dels seus extrems. A mesura que el procés d'intersecció de línies detecta punts d'intersecció, sigui en els extrems o en punts intermedis, els punts d'intersecció es renumeren de forma definitiva en tant que nodes i les línies, originals o resultants de la divisió en les interseccions, reben la numeració definitiva en tant que arcs, a cada un dels quals s'associa la numeració dels nodes inicial i final.

Aquesta informació topològica s'emmagatzema amb cada arc, ja que per definició hi ha sempre i necessàriament un node inicial i només un per a cada arc i un node final i només un per a cada arc. Segons els programes la informació topològica de node inicial i node final de cada arc s'emmagatzema en la taula d'atributs dels arcs o en altres fitxers, juntament amb la geometria, o en ambdós.

Marcatge dels nodes anòmals

En la representació topològica dels límits d'un conjunt de polígons adjacents per mitjà d'un graf, tot arc ha de connectar necessàriament amb un altre arc. Per tant, tot node en el qual no hi comença o acaba cap més arc és un error de connectivitat que indica o bé un error de tancament de polígons o bé un arc sobrer. Aquests nodes es marquen com a errors de tipus node penjant o node terminal, que després caldrà corregir.

En el cas que la topologia arc-node tingui per finalitat representar només una xarxa d'elements lineals connectats, els nodes penjants poden ser o no errors, ja que en una xarxa d'elements lineals hi ha situacions en què és inevitable que hi hagi nodes terminals (per exemple, la capçalera o la desembocadura d'un riu, o una carretera que acaba en un poble i no porta enlloc més). No obstant, en una xarxa d'elements lineals també hi pot haver nodes terminals que siguin conseqüència d'una manca de connectivitat. Per tant, cal marcar igualment tots els nodes penjants i inspeccionar-los posteriorment per tal de decidir quins són errors que cal corregir.

Un segon tipus de node anòmal que els programes d'estructuració topològica acostumen a marcar com a possible error són els pseudonodes. En aquest cas es tracta de nodes en els quals només hi connecten dos arcs. Els pseudonodes no són pròpiament errors, ja que mantenen la connectivitat entre arcs. Simplement són nodes que potencialment poden ser prescindibles atès que els dos arcs connectats per un pseudonode es podrien substituir per un sol arc i el pseudonode ser simplement un vèrtex més. En general, se solen deixar ja que no causen cap problema altre que l'excessiva fragmentació dels arcs, que si convé es pot corregir mitjançant l'eliminació de pseudonodes automàtica. No obstant, hi ha casos també en què és imprescindible mantenir els pseudonodes perquè marquen un canvi de valor d'un atribut dels arcs que comparteixen el pseudonode (per exemple, diferent límit de velocitat al llarg d'una carretera, perquè el pseudonode en si mateix representa quelcom real (per exemple, les estacions al llarg d'una línia de ferrocarril), o bé perquè són inevitables com en el cas d'un polígon aïllat, definit per un sol arc que comença i acaba en el mateix node. Alguns programes marquen aquest darrer cas, com un tipus de node diferent, el node d'anella. La resta de nodes, aquells en els quals connecten tres o més arcs es consideren nodes normals.

El procés de marcatge examina tots els nodes i compta el nombre d'arcs que incideixen en cada node per identificar els diferents tipus de nodes, normals o anòmals. En realitat, per fer-ho examina els arcs a través de la informació topològica de node inicial i final de cada arc, generada en el procés de creació de la topologia arc-node.

Càlcul i emmagatzematge de la longitud dels arcs

Un cop finalitzat el procés de creació de la topologia arc-node i es disposa dels arcs i nodes definitius, un darrer pas és calcular la longitud dels arcs. Aquesta és una propietat espacial de cada arc que es manté inalterada fins que no canviï l'arc i s'hagi de generar de nou la topologia arc-node. Per tant, els programes solen calcular-la i mantenir-la emmagatzemada, generalment dins de la taula d'atributs dels arcs, ja que es conservarà fins al següent cop que calgui aplicar el procés d'estructuració topològica.

El càlcul de la longitud dels arcs és senzill. Simplement s'ha de calcular la longitud de tots i cada un dels segments de recta entre parells de vèrtexs consecutius de l'arc i sumar-les totes al final, La longitud de cada segment s'obté simplement aplicant la fórmula del teorema de Pitàgores per al càlcul de la distància euclidiana entre dos punts. Així la fórmula general de la longitud d'un arc és:

Creació de la topologia polígon-arc

La topologia polígon-arc només és necessària en el cas d'estructuració de polígons. Tanmateix, atès que aquest fou el cas inicial que motivà l'aplicació de la topologia en els SIG, es considera part del procés d'estructuració topològica per antonomàsia. El procediment de càlcul de la topologia polígon-arc comprèn dues parts que consten dels següents passos (Burrough, 1986):

• construcció dels contorns
  • creació del contorn exterior més general
  • creació de la resta de contorns que depenen del contorn exterior més general
  • repetició dels passos anteriors per a crear la resta de contorns exteriors i de contorns que en depenen
• construcció dels polígons
  • identificació de relacions d'inclusió entre contorns exteriors

Quan es disposa de topologia arc-node, un contorn és una seqüència d'arcs que comença i acaba en un mateix node i defineix un recinte tancat o polígon elemental. Un polígon, però, pot contenir altres polígons al seu interior, és a dir forats que cal descomptar. Per tant un polígon pot estar format per un contorn general i un o més contorns interiors.

El procés de creació de polígons i de la topologia polígon-arc passa, doncs, per construir primer els contorns a partir dels arcs, construir després els polígons a partir dels contorns i, un cop es disposa dels polígons finals, identificar el polígon que hi ha a cada costat de cada arc d'acord amb el sentit de l'arc.

Construcció dels contorns

La construcció dels contorns a partir dels arcs comença per construir el contorn exterior més general. Un contorn exterior és un contorn format per una seqüència d'arcs que, presos tots en el mateix sentit (en sentit horari, per exemple), sempre tenen un mateix polígon en el costat esquerre. Són casos de contorns exteriors el contorn exterior general de tota l'àrea geogràfica coberta per un conjunt de dades, en el cas que es tracti d'una àrea geogràfica contínua (per exemple, una comarca sense enclavaments interiors ni exteriors), o bé cada un dels contorns exteriors generals en el cas que l'àrea geogràfica sigui discontínua (per exemple, un conjunt d'illes urbanes). Els contorns de forats i polígons aïllats continguts dins d'altres polígons són casos també de contorns exteriors. En tots els casos el contorn exterior és un contorn que delimita una àrea aïllada dins d'un espai sense divisions, ja sigui en el buit o dins d'un altre polígon.

El procés de construcció de la topologia polígon-arc comença per identificar els contorns exteriors i després continua amb la identificació dels contorns dels polígons que subdivideixen l'àrea delimitada per cada contorn exterior. El primer contorn exterior a delimitar és el contorn exterior més general.

Creació del contorn exterior més general

La construcció del contorn exterior més general consisteix a resseguir la seqüència tancada d'arcs que el formen, aprofitant la informació topològica de connectivitat entre els arcs, començant sempre pel node més exterior (habitualment es considera el node de menor coordenada x i major coordenada y), sempre en sentit horari i sempre prenent l'arc més a l'esquerra de cada node travessat, fins arribar una altra vegada al node origen. Mentre es ressegueix la seqüència d'arcs es compta el nombre de vegades que es visita cada arc i cada node. Un cop completat el contorn exterior més general s'emmagatzema la llista ordenada d'arcs que el formen i es calcula la superfície i el perímetre de l'àrea delimitada pel contorn, a mode de valors preliminars.

Creació de la resta de contorns que depenen del contorn exterior més general

Un cop es disposa del contorn exterior més general, es creen els contorns que depenen d'aquest. És a dir, de les àrees en què es subdivideix l'àrea delimitada pel contorn exterior. El procés consisteix igualment a resseguir seqüències d'arcs tancades, començant pel node en què s'ha originat el contorn exterior, sempre en sentit horari i sempre prenent l'arc més a la dreta de cada node travessat fins a arribar al node inicial. En acabar cada contorn el procés continua a partir del node següent en la seqüència del contorn que s'acaba de crear seguint els mateixos criteris. Durant tot el procés es continua portant el compte del nombre de vegades que es visita cada arc i cada node i en acabar cada contorn s'emmagatzema la llista d'arcs i es calculen la superfície i el perímetre preliminars.

El procés de formació dels contorns dependents d'un contorn exterior finalitza quan tots els arcs a què es pot arribar des del node inicial del contorn exterior han estat visitats ja 2 vegades, atès que un arc és sempre i únicament el límit entre dos polígons i per tant no pot pertànyer a més de dos contorns.

Repetició del procés per a crear la resta de contorns exteriors i de contorns que en depenen

Quan s'ha completat la creació del primer contorn exterior i dels contorns que en depenen, s'examina la llista de nodes i aquells que han estat visitats 0 vegades són potencialment origen d'altres contorns exteriors. El procés es repeteix aleshores, seguint els mateixos criteris, per a delimitar la resta de contorns exteriors i de contorns que en depenen. El procés acaba quan no quedi cap node visitat 0 vegades.

Construcció dels polígons

La construcció dels polígons consisteix a determinar dins de quin contorn es troba inclòs cada contorn exterior per tal de poder establir la llista de contorns que defineix cada polígon i excloure'n els polígons corresponents als contorns interiors inclosos. La inclusió es determina per mitjà de l'algorisme de punt en polígon prenent qualsevol dels nodes del contorn per al qual es vol determinar dins de quin altre contorn és inclòs. El procés comença pel contorn d'àrea més petita, que és el més susceptible d'estar contingut dins d'un altre i continua pels d'àrees successivament més grans fins a examinar-los tots.

Per a cada contorn contingut dins d'un altre es dóna identificador al polígon que el conté. Un cop examinats tots els contorns exteriors i determinats en quin polígon estan continguts, s'emmagatzema la llista definitiva d'arcs que formen cada polígon afegint al contorn general del polígon les llistes d'arcs dels contorns continguts, que es marquen com a contorns a excloure, i es recalcula la superfície i perímetre final de cada polígon

Etiquetatge dels polígons

L'etiquetatge dels polígons, que consisteix a assignar un atribut a cada polígon per mitjà d'un punt d'etiqueta introduït durant el procés de digitalització, no forma part de la creació de la topologia polígon-arc. Els polígons queden completament definits i identificats un cop finalitzada la construcció dels polígons. La finalitat de l'etiquetatge dels polígons és simplement recuperar per a cada polígon el valor d'un atribut introduït durant el procés de digitalització. En aquest sentit, i en tant que final del procés d'estructuració de les dades procedents de la digitalització, l'etiquetatge dels polígons s'inclou com a pas final en el procés d'estructuració topològica de polígons a partir de la digitalització de línies i de punts d'etiqueta.

El procés d'etiquetatge dels polígons consisteix simplement a determinar, per mitjà de l'algorisme de punt en polígon, dins de quin polígon és contingut cada punt d'etiqueta i transferir al polígon el valor de l'atribut associat al punt d'etiqueta.

Algorisme de punt en polígon. Per a determinar si un punt és contingut o no dins d'un polígon es traça una línia vertical a partir del punt i es compta el nombre de vegades que la línia creua el contorn del polígon. Si el nombre d'interseccions és senar el punt és dins, si el nombre d'interseccions és parell el punt és fora.

 

Errors topològics

Errors de nodes

Després de l'estructuració topològica, és necessari revisar en primer lloc els errors de nodes (connectivitat de línies i per tant tancament de polígons) i corregir-los, la qual cosa implica editar el conjunt de línies digitalitzades i tornar a refer la topologia, comprovant altre cop en acabar que no queden errors de nodes. Tots els errors de nodes es materialitzen en forma de nodes penjants, que en el cas d'estructurar polígons s'han d'eliminar completament, mentre que en el cas d'estructurar línies caldrà admetre com a excepcions els orígens dels elements lineals.

Els pseudonodes, en la mesura que no interrompen la connectivitat de la línia, es poden conservar o eliminar segons les necessitats posteriors de treball. En tot cas, si s'eliminen cal vetllar de respectar aquells que són necessaris per a mantenir correctament els valors dels atrributs dels arcs. El procés d'eliminació de pseudonodes és un procés automàtic.

Errors d'etiquetes

Quan els errors de nodes estan ja resolts, té sentit, en el cas d'estructurar polígons, revisar els possibles errors d'etiquetes, ja siguin polígons sense cap etiqueta o polígons amb múltiples etiquetes. Abans no, ja que un suposat error d'etiquetes (per exemple, un polígon amb dues etiquetes) pot ser simplement la conseqüència d'un error de nodes (per exemple, un arc mal connectat que deixa oberts dos polígons com si fossin un de sol).

L'etiquetatge de polígons i la revisió d'etiquetes tot i no ser necessaris per a la creació de la topologia de polígons són útils per a revisar la correcció dels polígons creats, ja que ofereixen un procediment de comprovació addicional i permeten descobrir errors d'integritat de les dades que passarien inadvertits perquè no apareixen com a errors topològics, és a dir com a errors de nodes. Així, l'existència de polígons sense etiquetes ajudar a detectar la formació de polígons artefacte causats per línies connectades en punts incorrectes o de micropolígons causats per l'existència de línies duplicades que no coincideixen exactament. D'altra banda, l'existència de polígons amb múltiples etiquetes pot revelar l'omissió d'algun arc durant el procés de dibuix que deixa sense separa dues àrees diferenciades.

La correcció dels errors d'etiquetes passa igualment per editar la digitalització original i per regenerar la topologia comprovant al final que no queden errors d'etiquetes. La correcció en aquest cas pot consistir en afegir o suprimir etiquetes, però també en modificar les línies que han donat lloc a polígons falsos o afegir línies que s'havien omès.

Flux de treball

El procés de treball quan es disposa de la funcionalitat d'estructuració topològica automàtica permet realitzar la digitalització de forma independent, atenent només a reproduir correctament les formes i a respectar al màxim la connectivitat de les línies, i realitzar la correcció d'errors després de l'estructuració topològica que els detecta i posa de manifest. El procés esdevé iteratiu en la mesura en què la correcció dels errors requereix editar els elements digitalitzats originals o bé els estructurats i tornar a refer l'estructura topològica per revisar si resten errors i repetir el procés fins que no en resta cap.

Flux de treball del procés d'estructuració topològica.

 

Utilitat

L'estructuració topològica és un recurs fonamental en els sistemes d’informació geogràfica (de fet, es va idear per a poder comprovar i assegurar la consistència de les representacions digitals). L'estructuració topològica intervé no sols en el procés inicial d'estructurar les dades digitalitzades sinó també en totes les operacions de geoprocessament que generen noves dades espacials per tal de garantir la coherència dels resultats i dotar-los també d'estructura topològica. Generalment només es troba disponible en els programes de SIG de nivell mitjà o avançat. Els programes més bàsics de SIG només ofereixen la digitalització directa d'elements simples, sense estructuració topològica.

Fins a finals de la dècada de 1990 ha estat el procediment bàsic per a dotar de topologia les dades geoespacials de tipus vectorial. De fet, encara que posteriorment han aparegut altres formes de definir, emmagatzemar i validar la informació topològica en els conjunts de dades vectorials, el procés d'estructuració es continua emprant com a procediment de base, ocult a l'usuari, per a generar ni que sigui temporalment l'estructura de dades per mitjà de la qual es valida la coherència topològica dels elements espacials i el compliment de les regles en què es basa la topologia definida. Igualment serveix de base per a les operacions de consulta per mitjà de predicats espacials

Temes relacionats

• Digitalització
• Model de dades vectorial
• Sistemes d’informació geogràfica

Referències

Burrough, P.A. (1986) Principles of Geographical Information Systems for Land Resources Assessment, Oxford, UK, Clarendon Press.

Cook, B. (1967) "A computer representation of plane region boundaries", Australian Computer Journal, 1, 44-50.

Cooke, D. F. and Maxfield, W. H. (1967) "The Development of a Geographic Base File and its Uses for Mapping" in Urban and Regional Information Systems for Social Programs: Papers from the Fifth Annual Conference of the Urban and Regional Information Systems Association. Kent, Ohio: Center for Urban Regionalism, Kent State University.

Corbett, J.P. (1975) "Topological principles in cartography", Proceedings of AUTOCARTO 2, Reston, Virginia: ASPRS.

Douglas, D.H. (1974) "It makes me so cross," in Marble, D.F.; Calkins, H. and Peuquet, D. (1984) (eds.) Basic Readings in Geographic Information Systems, Williamsville, New York: SPAD Systems Ltd.

Lee, D.T. and Preparata, F.P. (1984) "Computational geometry: a survey", IEEE Transactions on Computers, C-33(12),1072- 1101.

Little, J.J. and Peucker, T.K. (1979) "A recursive procedure for finding the intersection of two digital curves", Computer Graphics and Image Processing, 10,159-71.

Loomis, R.G. (1965) "Boundary networks", Communications of the Association for Computing Machinery, 8, 44-48.

Peucker, T.K. and Chrisman, N. (1975) "Cartographic data structures", American Cartographer, 2(1), 55-69.

Smith, C. (1967) "The New Haven Census Use Study: A General Description" in Urban and Regional Information Systems for Social Programs: Papers from the Fifth Annual Conference of the Urban and Regional Information Systems Association. Kent, Ohio: Center for Urban Regionalism, Kent State University.

White, D. (1977) "A new method of polygon overlay" in Dutton, G. H. (ed.) Proceedings of the Advanced Study Symposium on Topological Data Structures for Geographic Information Systems, Cambridge, Massachussets: Laboratory for Computer Graphics and Spatial Analysis, Harvard University.

LCGSA (1983) The ODYSSEY system summary, Cambridge, Massachussets: Laboratory for Computer Graphics and Spatial Analysis, Harvard University.

Lectures recomanades

Burrough, P.A. (1986) Principles of Geographical Information Systems for Land Resources Assessment, Oxford, UK, Clarendon Press. Chapter 2.

Chrisman, N. (1988) "The risks of software innovation: a case study of the Harvard Lab", American Cartographer, 15(3), 291-300.

Coppock, J.T. and Rhind, D.W. (1991) "The history of GIS" in Maguire, D.; Goodchild, M. and Rhind, D.W. (eds.) Geographical Information Systems. Principles and Applications, Harlow: Longman.

Peucker, T.K. and Chrisman, N. (1975) "Cartographic data structures", American Cartographer, 2(1), 55-69.