Polígons de Thiessen

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

 

Els polígons de Thiessen, anomenats també diagrama e Voronoi o tessel·lació de Dirichlet en matemàtiques, són una partició o tessel·lació d'un espai en àrees de proximitat a l'entorn de cada un dels punts d'un conjunt de punts, de tal manera que cada polígon delimita l'àrea més pròxima a cada punt, que no pas a la resta de punts.

La partició en polígons de Thiessen és l'estructura dual de la triangulació de Delaunay, que en els sistemes d’informació geogràfica s'utilitza per a generar xarxes irregulars de triangles i els popis polígons de Thiessen. Els polígons de Thiessen reben el nom del meteoròleg nord-americà Alfred H. Thiessen.

Els polígons de Thiessen serveixen com a tècnica bàsica per a l'anàlisi de proximitat. L'anàlisi de proximitat és una operació espacial de geoprocessament aplicable a dades del model de dades vectorials, que, juntament amb la selecció per distància, l'anàlisi de l'element més proper, el càlcul de matrius de distància entre elements i l'anàlisi d'àrees d'influència, forma el grup d'operacions de SIG d'anàlisi de distància.

Polígons de Thiessen o àrees de proximitat: a) punts generadors; b) polígons de Thiessen corresponents al conjunt de punts generadors.

Tot i no ser una operació ràster, ja que no es basa en cel·les, alguns programes de SIG ràster implementen també el càlcul de polígons de Thiessen com a operació sobre dades del model de dades ràster, que essencialment consisteix en la rasterització del resultat del càlcul vectorial dels polígons de Thiessen.

Polígons de Thiessen calculats amb dades ràster.

A més de servir com a eina per a l'anàlisi de proximitat, els polígons de Thiessen s'utilitzen principalment com a mètode d'interpolació de dades categòriques a partir de punts de mostreig, equivalent a la interpolació pel veí més proper, i com a base d'altres mètodes d'interpolació derivats com la interpolació pel veí natural.

 

 

Origen

Els polígons de Thiessen es coneixen en matemàtiques amb el nom de diagrama de Voronoi (també tessel·lació de Voronoi, polígons de Voronoi o tessel·lació de Dirichlet), ja que fou el matemàtic rus Georgy Fedoseevich Voronoi qui en formulà la definició formal i general per a espais de n dimensions (Voronoi, 1908). Anteriorment el matemàtic alemany Dirichlet (1850) havia fet servir diagrames de Voronoi en 2 i 3 dimensions per a l'estudi dels polinomis de segon grau, i encara abans sembla ser que el mateix Descartes n'havia fet ús a mitjans del segle XVII.

Polígons de Thiessen és el nom amb què es coneixen els diagrames de Voronoi en geofísica i meteorologia, i per extensió en geografia, a partir de les aplicacions del meteoròleg nord-americà Alfred H. Thiessen (1911) dels diagrames de Voronoi a l'anàlisi de la distribució espacial d'observacions meteorològiques com les precipitacions.

La implementació del càlcul de polígons de Thiessen en els sistemes d’informació geogràfica data de l'època inicial de desenvolupament dels primers sistemes d’informació geogràfica. En concret, 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, oferia ja la funcionalitat de produir polígons de Thiessen (mapes de proximitat), a més de mapes de coropletes, d'isopletes, anàlisi de superfícies de tendència, interpolació ponderada per la distància inversa i altres tipus de mapes (Shepard, 1968; Peucker, 1972; Schmidt and Zaft, 1975).

Definició

En matemàtiques un diagrama de Voronoi o partició de polígons de Thiessen és una partició d'un espai mètric de qualsevol nombre de dimensions, determinada per les distàncies a un subconjunt de punts (o objectes) d'aquest espai, anomenats llocs, generadors o llavors (seeds), de manera que a cada punt o objecte generador li correspon un polígon de Thiessen o cel·la de Voronoi, que comprèn el subconjunt de tots els punts de l'espai considerat la distància dels quals al punt o objecte generador és inferior o igual a la distància a qualsevol dels altes punts o objectes generadors. Formalment,

 

on 
R_k    és  la cel·la de Voronoi o polígon de Thiessen per al punt generador k generador
x      és tot punt pertanyent a l'espai mètric X
d(x,P_k)    és la distància del punt x al punt generador k
d(x,P_j)    és la distància del punt x al punt generador j
(P_k , P_j denota que els punts k i j pertanyen al conjunt de punts generadors P)

Aleshores, el diagrama de Voronoi o la partició de polígons de Thiessen és simplement el tuple o conjunt de totes les cel·les de Voronoi o polígons de Thiessen, essent K la llista d'índexs dels punts de P.

Encara que teòricament és possible definir una partició de Voronoi per a un conjunt infinit de punts generadors, normalment la majoria d'aplicacions utilitzen un conjunt finit de punts generadors. Idealment també, les cel·les de Voronoi o polígons de Thiessen poden ser disjuntes o no disjuntes, i connexes o no connexes, però en la majoria d'aplicacions es consideren només polígons de Thiessen connexos i disjunts.

Propietats i casos simples

Algunes de les propietats importants dels polígons de Thiessen, en l'espai euclidià i especialment en el pla de dues dimensions, són les següents (Aurenhammer, 1991; Okabe et al., 2000):

• En el cas de l'espai euclidià i emprant punts com a generadors, l'estructura dual dels polígons de Thiessen o diagrama de Voronoi és la triangulació de Delaunay. Concretament, ambdós són grafs plans i són mútuament el graf dual l'un de l'altre. La triangulació de Delaunay compleix el criteri de Delaunay, segons el qual el cercle en què s'inscriu cada triangle no pot contenir altres punts generadors que els tres vèrtexs que defineixen el triangle. El compliment del criteri de Delaunay assegura que tot punt de la superfície generada és tan proper com sigui possible a un dels vèrtexs de triangle, de manera que les bisectrius dels costats dels triangles donen lloc directament a una partició en polígons de Thiessen.
• Cada parell de punts generadors més propers correspon a un parell de polígons de Thiessen adjacents. Els punts més propers a un punt donat en una partició de polígons de Thiessen o en una triangulació de Delaunay s'anomenen veïns naturals.
• En el pla euclidià, els polígons de Thiessen adjacents sobre el polígon convex mínim comparteixen un costat de longitud infinita. Això vol dir que els polígons de Thiessen més exteriors s'estenen infinitament sobre el pla de dues dimensions. A la pràctica, en les aplicacions relatives a la informació geoespacial, l'àrea coberta per la partició de polígons de Thiessen es tanca convencionalment mitjançant un rectangle.
• Els polígons de Thiessen gaudeixen d'una certa estabilitat. És a dir, lleugers canvis en la forma o posició dels generadors produeixen només lleugers canvis en la forma dels polígons de Thiessen, però no en el nombre i la disposició dels polígons. En aquest sentit són estables quant a la topologia.
  

  Polígons de Thiessen i la corresponent triangulació de Dealunay (parcial, només per als punts centrals). Els costats dels polígons de Thiessen són la bisectriu dels costats dels triangles de Delaunay.

 

Casos simples en el pla

En el cas particular que l'espai mètric és un espai euclidià de dimensió finita, que els generadors són punts, que el nombre de punts generadors és finit i que tots són diferents, els polígons de Thiessen o cel·les de Voronoi són polígons convexos, disjunts i connexos, que es poden definir pels seus vèrtexs o costats.

La partició de polígons de Thiessen o diagrama de Voronoi s'acostuma a calcular per a conjunts de punts distribuïts irregularment, ja que la tessel·lació de proximitat per a punts distribuïts regularment dóna lloc a malles de fomes conegudes. Algunes de les tessel·lacions més conegudes corresponents a malles de punts regulars són la tessel·lació en quadrats, corresponent a la tessel·lació d'un ràster, la tessel·lació triangular i la tessel·lació hexagonal.

Aquestes tessel·lacions regulars, en l'espai de 3 dimensions donen lloc a tessel·lacions en cubs, corresponents als vòxels, o en dodecaedres hexagonals.

Polígons de Thiessen el pla per a diferents malles de punts: a) malla de punts irregular; b) malla de punts regular quadrada; c) malla de punts regular triangular; d) malla de punts regular hexagonal.

 

Aplicacions

Les aplicacions més habituals dels polígons de Thiessen en l'àmbit de la informació geoespacial són l'anàlisi de proximitat i la interpolació pel veí més proper o la interpolació pel veí natural. Els camps d'aplicació en aquest àmbit són molt diversos. En climatologia, s'utilitzen per a calcular totals o mitjanes de paràmetres com les precipitacions per a àrees a partir dels punts de les estacions meteorològiques. En ecologia, els polígons de Thiessen permeten interpolar valors de variables com la coberta forestal o el patró de creixement dels boscos per a àrees a partir de punts d'observació, i també generar mapes de models de combustible per a models de simulació d'incendis forestals. En epidemiologia permeten relacionar especialment els possibles punts d'origen d'epidèmies amb la difusió espacial de la malaltia. En exploració minera, proporcionen una estimació inicial de la distribució dels recursos encara que són preferibles altres mètodes més acurats d'interpolació. En telecomunicacions, serveixen per a derivar la capacitat de les cel·les de les xarxes de telefonia mòbil. També es documenten aplicacions similars en geografia i arqueologia.

Fora de l'àmbit de la informació geoespacial, els polígons de Thiessen o diagrama de Voronoi tenen nombroses aplicacions en informàtica. En bases de dades serveixen per a respondre cerques basades en el veí més proper i per a desenvolupar tècniques de compressió de dades. En informàtica gràfica permeten generar textures d'aspecte orgànic. També s'utilitzen en intel·ligència artificial per a tècniques de classificació en aprenentatge automàtic i com a auxiliar de navegació en robótica.

En física, química computacional i ciència dels materials, els diagrames de Voronoi serveixen per a representar l'estructura volumètrica dels polímers, estructures microcristal·lines i la distribució de les càrregues atòmiques en les estructures mol·leculars.

Per últim, en geometria, els diagrames de Voronoi serveixen per a avaluar la circularitat de conjunts de punts.

Temes relacionats

• Àrea d'influència
• Interpolació
• Model de dades ràster
• Model de dades vectorial
• Sistemes d’informació geogràfica
• Xarxa irregular de triangles

Referències

Aurenhammer, F. (1991) "Voronoi Diagrams. A Survey of a Fundamental Geometric Data Structure". ACM Computing Surveys, 23, 3, 345–405.

Dirichlet, G.L. (1850) "Über die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen", Journal für die Reine und Angewandte Mathematik, 40, 209–227.

Okabe, A.; Boots, B. Sugihara, K. and Chiu, S.N. (2000) Spatial Tessellations – Concepts and Applications of Voronoi Diagrams. 2nd edition. New York: John Wiley.

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

Shepard, D. (1968) "A two-dimensional interpolation function for irregularly-spaced data", Proceedings of the 1968 ACM National Conference.

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.

Thiessen. A.H. (1911) "Precipitation averages for large areas", Monthly Weather Review, 39, 7, 1082-1084.

Voronoi, Georgy (1908) "Nouvelles applications des paramètres continus à la théorie des formes quadratiques", Journal für die Reine und Angewandte Mathematik, 133, 97–178.

Lectures recomanades

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

Kang, J.M. (2008) "Voronoi diagram" in Shekar, S. and Xiong, H. (eds.) Encyclopedia of GIS. New York: Springer.