Model de dades vectorial | icgc

Model de dades vectorial

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

El model de dades vectorial és, juntament amb el model de dades ràster, una de les dues formes bàsiques de representació digital de la informació geoespacial.  El model de dades vectorial representa les entitats o fenòmens geogràfics per mitjà d'elements geomètrics, definits per coordenades, als quals s'associen els atributs temàtics que descriuen l'entitat o el fenomen representat. El model de dades vectorial és particularment apropiat per a representar la forma d'entitats geogràfiques amb límits definits.

En el model de dades vectorial la posició i la forma dels elements geomètrics es representa per mitjà de coordenades en un espai de coordenades cartesià, habitualment 2D (x, y) i de vegades 3D ( x, y, z), de precisió teòricament infinita, però a la pràctica limitada per la capacitat de representació numèrica dels ordinadors. En el cas en què els elements geomètrics portin associades mesures de referenciació lineal, a més de les coordenades x, y  o  x, y, z, s'afegeix una 'coordenada' m a continuació, que és la mesura de referenciació lineal (x, y, m o x, y, z, m). No tots els formats de dades vectorials ni tots els programes de sistemes d’informació geogràfica (SIG) admeten informació de referenciació lineal o són capaços d'usar-la.

La convenció bàsica del model de dades vectorial és el segment de recta definit per dos punts; és a dir, un vector, d'aquí el nom del model. Així, cada parell de punts consecutius d'una llista de coordenades s'interpreta sempre com un segment de recta entre aquests dos punts. La representació vectorial és per tant una representació essencialment lineal, ja que les formes es representen per mitjà dels seus contorns, que són aproximats per mitjà de línies poligonals, anomenades polilínies, més o menys detallades segons la quantitat de punts, anomenats vèrtexs, que defineixen la polilínia i la separació entre els vèrtexs.

SUMARI

Origen

El model de dades vectorial per a representar informació gràfica és tan àntic com els gràfics per ordinador. Les primeres aplicacions de dades vectorials amb finalitat gràfica daten de la dècada de 1950 en què l'ús de monitors d'ordinador amb pantalla de tub de raigs catòdics per a produir gràfics vectorials, els anomenats monitors vectorials, van esdevenir relativament populars en aplicacions científiques i tècniques. Aquest tipus de monitors produïen la imatge gràfica traçant un raig sobre la superfície de la pantalla, la trajectòria del qual era una línia descrita pel vector format per les posicions inicial i final. Aquest tipus de monitors generaven imatges d'alta resolució, per la qual cosa des de bon començament els gràfics vectorials han estat considerats gràfics d'alta qualitat.

L'aplicació dels gràfics vectorials a la cartografia digital i als sistemes d'informació geogràfica data també dels inicis de la cartografia assistida per ordinador i dels SIG. En el Canada Geograhic Information System, CGIS, iniciat el 1962 per Roger Tomlinson, que es considera el primer SIG de la història, es documenta ja l'ús de dades vectorials per a representar els polígons d'usos del sòl de la província de Saskatchewan, Canadà (Tomlinson, 1967). També en el camp de la cartografia assistida per ordinador, que de fet és l'antecedent dels sistemes d'informació geogràfica, es documenta l'ús de dades vectorials des dels primers intents d'informatització de la cartografia (Tobler, 1959; Bickmore and Shaw, 1963). Un dels programes de cartografia més emblemàtics i difosos de l'època, el programa SYMAP creat l'any 1967 al Laboratory for Computer Graphics and Spatial Analysis de Harvard University, utilitzava el model de dades vectorial per a produir mapes de coropletes, isopletes, polígons de Thiessen i altres tipus de mapes, per bé que el resultat s'havia d'imprimir mitjançant la sobreimpressió de caràcters en impressores de tipus matricial (Peucker, 1972; Schmidt and Zaft, 1975).

La definició dels principals models de dades vectorials utilitzats en els sistemes d'informació geogràfica daten de mitjan dècada de 1970, en gran part també en treballs derivats del Laboratory for Computer Graphics and Spatial Analysis de Harvard University (Peucker and Chrisman, 1975) i altres precedents de mitjans de la dècada de 1960 (Cook, 1967).

Informació espacial. Tipus d'elements geomètrics

Els tipus d'elements geomètrics (primitives geomètriques o gràfiques) bàsics del model de dades vectorial són:

  • el punt: definit i emmagatzemat com un sol parell de coordenades x, y.
  • la línia: definida i emmagatzemada com una seqüència (llista ordenada) de parells de coordenades x, y (punts anomenats vèrtexs). Sovint és anomenada polilínia per la seva forma poligonal, però també rep altres noms com cadena lineal (line string).
  • el polígon: definit i emmagatzemat com una seqüència de parells de coordenades x, y tancada; és a dir, una polilínia en què l'últim vèrtex és igual al primer.
     
Imatge

Representació vectorial dels elements geomètrics.

 

Altres elements geomètrics admesos per bastants programes, són:

  • la corba: forma lineal definida de manera analítica per mitjà de la funció apropiada i els paràmetres corresponents. Per exemple, el centre i el radi en el cas d'un cercle.
  • l'element de text o anotació: element gràfic sense forma geomètrica que consisteix en un punt d'inserció amb una cadena de text associada i propietats gràfiques relatives a l'estil del text, el tipus de lletra, la mida, l'orientació, el color, etc. Els elements de text serveixen per a resoldre les necessitats de retolació, principalment de toponímia, en els mapes de presentació, ja que s'introdueixen o es ressituen de forma individual i interactiva com a procés de dibuix i, per tant, estan molt més adaptats a les necessitats de cada mapa, per tal que sigui clar i llegible, que no pas les etiquetes generades automàticament.

Informació temàtica. Taules d'atributs

Normalment, sobretot en els formats més simples, cada fitxer d'elements geomètrics només conté elements geomètrics del mateix tipus, que representen entitats de la mateixa classe temàtica. Per exemple, un fitxer de punts que representa edificis, un fitxer de línies que representa carreteres, un de polígons que representa municipis, etc. Cada conjunt d'elements geomètrics del mateix tipus que representen una determinada classe temàtica d'entitats, sol anomenar-se una classe d'elements, o sovint també una capa.

Independentment de com s'emmagatzemi (un fitxer, diversos fitxers o, com en les bases de dades espacials, tot en una mateixa taula d'una base de dades), la classe d'elements és el conjunt, elements geomètrics amb la taula d'atributs corresponent.

Cada col·lecció de classes d'elements emmagatzemats formant una unitat de dades, s'anomena genèricament conjunt de dades, conjunt de dades geoespacials o base cartogràfica digital. Segons els formats dels diferents programes, un conjunt de dades pot contenir una o més classes d'elements, del mateix o de diferents tipus de geometria.

Dins de cada classe d'elements, els elements geomètrics estan identificats de forma única, de manera que es pugui saber quina entitat representa cada element i se li puguin associar els corresponents atributs temàtics.

Els atributs temàtics es guarden en un altre fitxer a part, gairebé sempre una taula, anomenada taula d'atributs de la classe d'elements corresponent. Dins de la taula d'atributs d'una classe cada registre també està identificat per mitjà del mateix identificador utilitzat per als elements geomètrics. Gràcies a aquest identificador comú és possible associar a cada element geomètric el registre de la taula amb els valors dels atributs que li corresponen.

Imatge

Classe d'elements: un conjunt d'elements geomètrics amb una taula d'atributs associada. A cada element li correspon un registre de la taula.

 

A part dels atributs propis, emmagatzemats a la taula d'atributs de la classe d'elements, es poden associar als elements altres atributs emmagatzemats en taules de bases de dades externes, que es poden relacionar amb els elements geomètrics a través de la taula d'atributs mitjançant l'operació d'unió relacional (join) pròpia de les bases de dades, que permet combinar o vincular dues taules.

Imatge

Base de dades externa connectada a una classe d'elements a través de la taula d'atributs.

 

Models de dades vectorials

Hi ha un nombre considerable de variants de model de dades vectorial, amb diferències tan notables quant al contingut i l'estructura de la informació (per exemple, amb o sense atributs, amb o sense topologia, etc.) que constitueixen models de dades diferents per si mateixos, de manera que és més apropiat parlar de la família de models de dades vectorials que no pas d'un model de dades vectorial.

Model vectorial de dibuix

L'estructura o model de dades vectorial de dibuix és format per línies simples, anomenades informalment espaguetis en el món dels SIG. És el model vectorial més senzill de tots. Simplement compleix la definició bàsica d'enregistrar les formes com a llistes de coordenades, és a dir com a línies simples, sense diferenciar entre polilínies obertes (línies) o tancades (polígons).

El que caracteritza el model vectorial de dibuix és el fet d'utilitzar en general polilínies obertes, fins i tot a l'hora de representar polígons, ja que la representació d'àrees per mitjà de polilínies permet reproduir visualment la forma dels polígons i es pot complementar amb textos a efectes d'identificació visual.

Imatge

a. Polígons representats per les línies dels seus contorns, més etiquetes identificatives. Visualment es reconeixen com a polígons, encara que en realitat són línies esparses. b. Una de les representacions possibles mitjançant línies simples.

 

L'ús de polilínies tancades per a representar les àrees en aquest model de dades no és sistemàtic, de manera que en realitat no es disposa dels elements de tipus polígon com a tals  i per tant no es poden calcular superfícies ni fer cap operació amb els polígons.

L'ús de polilínies tancades és ocasional i no obeeix a altra raó que la comoditat del dibuix. Per aquesta mateixa raó, el traçat d'una mateixa figura es pot resoldre dibuixant línies de moltes maneres diferents.

El model vectorial de dibuix té una utilitat principalment visual i no serveix directament per a càlculs o anàlisis. Sovint, i pel fet de ser una representació essencialment visual, no es fan servir funcions d'ajust durant el dibuix i les línies no connecten correctament entre si, encara que visualment no es noti.

El model vectorial de dibuix és una representació típica d'informació gràfica, més pròpia dels programes de disseny assistit per ordinador (CAD o DAO) o d'il·lustració que dels programes de SIG, tot i que aquests últims la poden entendre i usar com a format d'entrada o d'intercanvi.

En el model de dades dels programes de disseny assistit per ordinador (CAD) no es distingeix entre els diferents tipus d'elements geomètrics (punts, línies o polígons) per tal d'organitzar-los en classes d'elements separades segons la geometria. No hi ha classes d'elements, tots estan junts en el conjunt de dades (un mateix fitxer) i els elements geomètrics no disposen de taula d'atributs associada per a emmagatzemar atributs temàtics. Els elements d'un dibuix de disseny assistit per ordinador (CAD) només tenen associades propietats gràfiques (color, gruix, estil, etc.) i pertanyen a una capa, que permet activar-los o desactivar-los i aplicar altres funcions col·lectivament, però que no necessàriament té un significat temàtic.

Model vectorial sense topologia

El tret característic de l'estructura o model de dades vectorial sense topologia és el fet d'utilitzar sistemàticament polilínies tancades (últim vèrtex igual al primer) per a representar polígons. És a dir, per mitjà de polígons simples o polígons explícits. En aquest cas cada polígon es representa per mitjà d'una polilínia tancada, duplicant els límits comuns en el cas dels polígons adjacents.

Imatge

a. Representació per mitjà de polígons simples (explícits). El desplaçament dels contorns a la figura és intencionat per remarcar la duplicació dels límits comuns entre polígons adjacents. En realitat, si el traçat es fa correctament, els límits comuns són idèntics i coincideixen perfectament sense deixar buits ni solapaments entre polígons. b. Polígons simples interpretats com a tals pel programari de SIG.

 

En aquest model de dades es reprodueix realment la geometria dels polígons, no sols visualment, i es poden realitzar càlculs i anàlisis. Té l'inconvenient però que cada element és independent dels altres i que duplica els límits comuns, la qual cosa és una font potencial d'errors, com és ara la formació de buits i cavalcaments entre polígons veïns quan els límits comuns no coincideixen.

Per a alguns autors el model de dades de dibuix (línies simples o espaguetis) i el model vectorial sense topologia són un mateix model de dades vectorial simple. No obstant hi ha diferències considerables entre ambdós models de dades. Si més no entre el model de dades vectorial de dibuix, propi dels programes de CAD, i el model de dades vectorial sense topologia, propi del programari de cartografia temàtica i de SIG d'escriptori.

En el model de dades vectorial sense topologia (o model de dades vectorial simple de SIG) l'ús de polilínies tancades és sistemàtic per a representar polígons. A més, per aquest motiu, es distingeixen les diferents geometries (punts, línies o polígons) i s'emmagatzemen en classes d'elements separades, ja sigui en un mateix conjunt de dades o bé en conjunts de dades diferents, segons els diversos formats dels programes de SIG. D'altra banda cada classe d'elements disposa de la corresponent taula d'atributs per a emmagatzemar els atributs temàtics de les entitats geogràfiques representades pels elements geomètrics.

El model de dades vectorial sense topologia, excepte en els casos extremadament més simples, pot representar per mitjà de diferents convencions implementades en els diversos formats l'existència de forats a l'interior dels polígons, per exemple un enclavament d'una comarca dins d'una altra. En general, el que es fa és d'incloure en la definició del polígon les llistes de coordenades de tots els contorns que el formen, un d'exterior i cap o diversos d'interiors. Igualment, per mitjà de convencions, en el cas dels formats més desenvolupats, es poden representar elements multipart, formats per més d'un element individual, per exemple un arxipèlag format per diverses illes. El concepte d'element multipart no és limita als elements poligonals (multipolígons), també és aplicable en el cas de punts (multipunts) i de línies (multilínies).

Imatge

a. Exemple de polígon amb forats: la comarca del Bages té dos enclavaments a dins, un pertanyent al Solsonès i l'altre a Osona. b. Exemple de multipolígon: la comarca de la Cerdanya té dues parts, la principal dins de l'estat espanyol i Llívia dins de França.

 

El model de dades vectorial sense topologia dels SIG és un model de dades que no ofereix procediments de validació ni de detecció de les inconsistències entre els límits comuns dels polígons adjacents (buits, solapaments), a menys que els programes ofereixin recursos addicionals. En canvi, però, és un model de dades extraordinàriament simple i àgil de comprendre i de manejar, raó per la qual ha acabat sent un dels més populars actualment en el món dels sistemes d'informació geogràfica, inclosos els programes de SIG professional i els servidors de mapes web. El format shapefile o el format de vectors no estructurats de MiraMon són exemples del model de dades vectorial sense topologia, propi dels SIG. També en són exemples el format de geobase de dades d'ArcGIS o el format WKT (Well Known Text) del model de dades estàndard Simple Features Access, si bé aquests disposen de restriccions i mecanismes de validació de la consistència topològica de la geometria dels elements, encara que no emmagatzemin informació topològica en la definició dels elements espacials, només la geometria. Igualment, és un exemple del model de dades vectorial sense topologia el format KML (Keyhole Markup Language) de Google Earth i Google Maps, que ha esdevingut molt popular, gràcies a la cartografia web, fins al punt que ha acabat essent reconegut com un estàndard per part d'Open Geospatial Consortium.

Model vectorial topològic

L'estructura o model de dades vectorial topològic va néixer de la necessitat de disposar de procediments de validació de la consistència dels límits comuns entre polígons adjacents (Cook, 1967; Corbett, 1975). Per poder validar la consistència topològica de la geometria, el model vectorial topològic representa i emmagatzema explícitament relacions espacials de connectivitat entre línies i d'adjacència entre polígons. Així, a més de ser una estructura de dades més fiable perquè permet detectar els errors, és una estructura que ofereix major capacitat d'anàlisi perquè recull informació sobre relacions espacials entre els elements geomètrics, mentre que la resta de models de dades vectorials només recullen informació geomètrica sobre la forma dels elements.

L'estructura d'un mosaic, o partició de polígons, ve definida per la relació espacial d'adjacència o veïnatge entre els polígons. Els polígons d'un mosaic no poden deixar buits ni es poden encavalcar entre ells. Cada polígon té uns veïns concrets, i per tant fronteres precises que el separen d'aquests, les quals cal preservar en la representació. La coherència d'aquesta estructura s'assegura precisament representant els polígons no pas directament, en forma de línies tancades que defineixin l'àrea del polígon, sinó per mitjà de les fronteres comunes entre polígons veïns.

Aquestes fronteres, per tal de ser inequívoques i poder representar la relació de veïnatge entre parells de polígons, han de complir la condició de ser només frontera entre únicament dos polígons. Així hom pot emmagatzemar quin és el polígon que hi ha a cada costat -esquerre o dret- de la línia.

Imatge

a. Polígons representats per les línies (arcs) que compleixen la condició de ser límit només entre dos polígons veïns. b. Estructura topològica completa: nodes, arcs i polígons.

 

Les línies de frontera, en si mateixes, donada la condició anterior, formen una xarxa lineal connectada. La relació fonamental que defineix aquesta estructura és la connectivitat.

Segons aquesta relació el punt final d'una línia que connecta amb una altra ha de ser idèntic al punt inicial d'aquesta. Per tal de representar explícitament aquesta connexió és necessari que els punts inicials i finals de les línies es reconeguin per si mateixos com un tipus addicional d'elements: els nodes. D'aquesta manera es pot saber quina línia connecta amb quina altra a través de quin node.

Així, els arcs -línies connectades- es defineixen, amb independència de la seva forma, com línies entre únicament dos nodes. Els nodes, per definició, són els punts inicial i final d'un arc. Com que tots els elements es troben en el mateix pla, és a dir formen graf pla, tota intersecció ha de ser necessàriament un node i, per tant, les línies s'han de descompondre en arcs a les interseccions. Precisament, les interseccions de fronteres marquen el canvi de polígon en un o tots dos costats de l'arc i fan que calgui considerar un nou arc entre un parell diferent de polígons.

També es descomponen en arcs connectats per nodes els diferents trams de línies que representen entitats diferents (per exemple, un carrer que canvia de nom) o que presenten valors diferents en els seus atributs temàtics (per exemple, els trams d'una carretera amb diferents velocitats permeses). I, naturalment, tots els extrems d'arcs que no connecten amb cap altre arc estan delimitats pel corresponent node (per exemple, capçaleres i desembocadures de rius, finals de camins, carrers sense sortida, etc.).

En el model vectorial topològic les fronteres entre parells de polígons veïns es representen per mitjà d'arcs i nodes, de la mateixa manera que les xarxes lineals, guardant a més la informació -relació de veïnatge- de quin polígon hi ha a cada costat de l'arc, esquerra o dreta en el sentit de l'arc determinat pels nodes inicial i final de l'arc.

El polígon s'obté aleshores com la cadena d'arcs connectats que formen un recinte tancat, un contorn, sense cap altre arc al seu interior; o, dit d'altra manera, com la llista d'arcs, que tenen el polígon en qüestió en un dels seus costats.

Tots tres tipus d'elements (nodes, arcs i polígons) es numeren de forma única per tal d'identificar-los i poder enregistrar i emmagatzemar les relacions entre ells. Les relacions de connectivitat i d'adjacència se solen emmagatzemar a la taula d'atributs dels arcs, ja que el nombre de nodes i de polígons per a cada arc sempre és dos. La llista d'arcs que forma cada contorn de polígons s'enregistra en un fitxer a part, donat que el nombre d'arcs que formen cada contorn és variable i no es pot emmagatzemar de forma normalitzada dins de la taula d'atributs dels polígons.

Imatge

Taula d'atributs dels arcs, amb la informació topològica de connectivitat (node inicial i node final de cada arc) i d'adjacència (polígon a l'esquerra i a la dreta de cada arc).

 

En el cas de polígons que inclouen un altre polígon (forat) en el seu interior, el polígon està format per més d'un contorn i la llista d'arcs  corresponent és la llista d'arcs de tots els contorns.

L'estructura vectorial topològica evita duplicitats i errors, ofereix procediments automàtics de validació i es pot generar automàticament a partir de qualsevol conjunt de línies. Ha estat el model de dades clàssic dels programes de SIG professional durant molt de temps, fins a finals de la dècada de 1990. Alguns dels formats que implementen el model de dades vectorial topològic són el format de cobertura d'ArcInfo Workstation o el format de vectors estructurats de MiraMon. Actualment els programes tendeixen a afavorir les estructures de dades més simples i realitzen aquests processos internament, calculant informació sobre la topologia dels elements quan es necessita però sense emmagatzemar-la de forma permanent.

Model estàndard Simple Feature Access

Simple feature access (SFA) és un model de dades estàndard d'Open Geospatial Consortium (OGC, 2011a), i també d'ISO/TC211 (ISO/TC211, 2003), per a implementar la geometria d'elements simples en dues dimensions en bases de dades espacials. En particular, per a la implementació de bases de dades espacials mitjançant l'opció del llenguatge SQL ampliat espacialment (OGC, 2011b).

D'acord amb el model Simple Feature Access, un element geomètric en dues dimensions es considera simple quan no presenta interseccions amb ell mateix, d'aquí el nom del model. D'altra banda, els elements geomètrics del model estàndard Simple Feature Access es poden considerar elements simples en comparació amb els d'altres models de dades vectorials com per exemple el model vectorial topològic, en el sentit que cada element és independent de la resta i no emmagatzema informació topològica sobre relacions amb altres elements. En aquest sentit, la geometria dels objectes espacials del model Simple Feature Access és comparable, amb algunes diferències, a la dels elements geomètrics del model vectorials sense topologia (per exemple, el popular format shapefile o el dels elements de les geobases de dades d'ArcGIS, ambdós d'ESRI), en el ben entès que els models de dades en conjunt són diferents. Simple Feature Access és un model de dades exclusivament per a dades espacials de tipus vectorial.

Simple Featue Access és un model de dadesorientat a objectes, que defineix l'emmagatzematge comú per a la geometria de les dades espacials, juntament amb propietats, mètodes i predicats espacials, que són aplicables als objectes espacials (punt, línia, polígon, multipunt, multilínia, multipolígon, etc.). Simple Featue Access defineix a més un conjunt d'operadors espacials per a derivar o construir nous objectes espacials a partir dels objectes espacials emmagatzemats.

Imatge

Tipus d'objectes geomètrics bàsics del model estàndard Simple Feature Access.

 

El model de dades Simple Feature Access defineix tres tipus d'objectes geomètrics elementals: Point (punt), LineString (línia) i Polygon (polígon); i quatre tipus d'objectes geomètrics compostos: MultiPoint (multipunt), MultiLineString (multilínia), MultiPolygon (multipolígon) i GeometryCollection (col·lecció de geometries).

A més, defineix altres tipus d'objectes geomètrics per a modelitzar superfícies complexes: Triangle (triangle), TIN (TIN, xarxa irregular de triangles) i PolyhedralSurface (superfície polièdrica); i també tipus d'objectes abstractes que serveixen per a definir les propietats i mètodes generals dels altres tipus d'objectes: Geometry (geometria), Curve (corba), MultiCurve (multicorba), Surface (superfície), MultiSurface (multisuperfície).

Temes relacionats

Referències

Bickmore, D.P. and Shaw, M.A. (1963) Atlas of Great Britain and Northern Ireland. Oxford: Clarendon Press.

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

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

ISO/TC211 (2003) ISO 19125: Geographic information - Simple Feature Access (SFA), Geneva, Switzerland: International Organization for Standardization (ISO).

OGC (2011a) OpenGIS Implementation Standard for Geographic information - Simple feature access - Part 1: Common architecture (Version 1.2.1). Wayland, MA: Open Geospatial Consortium.

OGC (2011b) OpenGIS Implementation Standard for Geographic information - Simple feature access - Part 2: SQL option (Version 1.2.1). Wayland, MA: Open Geospatial Consortium.

Peucker, T.K. (1972) Computer Cartography. Commission on College Geography, Resource Paper No. 17, Washington DC: Association of American Geographers.

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

Schmidt, A.H. and Zaft, W.A. (1975) "Progress of the Harvard University Laboratory for Computer Graphics and Spatial Analysis" in Davis, J.C. and McCullagh, M.J. (eds) Display and analysis of spatial data. Wiley: London.

Tobler, W.R. (1959) "Automation and cartography", Geographical Review, 49: 526-534.

Tomlinson, R.F. (1967) An Introduction to the Geographic Information System of the Canada Land Inventory. Ottawa: Department of Forestry and Rural Development.

Lectures recomanades

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

Gandhi, V. (2008) "Vector data" in Shekar, S. and Xiong, H. (eds.) Encyclopedia of GIS, New York: Springer.

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