Anar al contingut

Polígons de Thiessen

De L'Enciclopèdia, la wikipedia en valencià
20 punts en el pla i la seua partició del pla en regions de Voronoi.

Els polígons de Thiessen, nomenats en honor al meteoròlec nortamericà Alfred H. Thiessen, són una construcció geomètrica que permet construir una partició del pla euclídeo. Estos objectes també varen ser estudiats pel matemàtic ucranià Gueorgui Voronói en 1907, d'a on prenen el nom alternatiu de diagrames de Voronoi o teselació de Voronoi, i pel matemàtic alemà Gustav Lejeune Dirichlet en 1850, d'a on prenen el nom de teselación de Dirichlet.

Els diagrames de Voronoi són un dels métodos d'interpolació més simples, basats en la distància euclidiana, especialment apropiada quan les senyes són qualitatius. Es creen en unir els punts entre sí, traçant les mediatrices dels segments d'unió. Els segments determinats per les interseccions d'estes mediatrices determinen una série de polígons en un espai bidimensional al voltant d'un conjunt de punts de control, de manera que el perímetro dels polígons generats siga equidistant als punts veïns i designen la seua àrea d'influència.

Diagrames de Voronói en el pla euclidiano ℝ2

La forma més fàcil i intuïtiva de visualisar als diagrames de Voronói és a través de la seua representació en el pla euclídeo. En la lliteratura clàssica se supon el fet de contar en un conjunt d'establiments que es desigen colocar sobre una certa regió geogràfica de tal manera que les ubicacions siguen lo més rendables possible. Per tant, es deu trobar una configuració que permeta que el número de clients atrets siga el més factible. La suposició llògica indica que els clients anirien a l'establiment més propenc al seu domicili i no a aquells que siguen molt lluntans. En base en açò, els diagrames de Voronói otorguen la configuració desijada pels establiments. El diagrama de Voronói induïx una subdivisió del pla euclidiano (la regió geogràfica) en funció d'un conjunt de llocs (els establiments), a on a cada lloc se li associa una i solament una subdivisió. Ademés, cada subdivisió engloba tots els punts més propencs al lloc associat als llocs restants, a açò li'l denomina un model de asignamiento de Voronói.[1]

Definició formal

Els quatre llocs més externs té associats regions de Voronói obertes caracterisades per les semi-arestes.

En primera instància, denotem a la distància euclidiana entre dos punts p i q per ‖p−q‖. En el pla llavors es té:

‖p−q‖=(px−qx)2+(py−qy)2

Construcció de la regió de Voronói d'un lloc per l'intersecció de semi-plans.

Siga P=p1,p2,…,pn el conjunt de n punts distints en el pla que són denominats com a llocs. Es definix el diagrama de Voronói de P com la subdivisió del pla en n regions, una per a cada pi∈P, complint la propietat de proximitat en la que un punt q pertany a la regió d'un lloc pi si i només si ‖q−pi‖<‖q−pj‖ per a cada pj∈P,j≠i. Es denotarà al diagrama de Voronói de P per mig de Vor(P). Cada regió que correspon a un lloc pi es denotarà com 𝒱(pi) i serà cridada regió de Voronói de pi.


La regió de Voronói per a un lloc pi està construïda a partir de les interseccions dels semiplanos formats en traçar els bisectores de pi cap als llocs pj,j≠i. Prenent el cas a on únicament hi ha dos llocs p i q, es traça el segment de recta pq‾ i posteriorment es traça el bisector de pq‾. Este bisector partix el pla en dos semiplanos, a on el semiplano que conté a p (representat com h(p,q)) representa el lloc geomètric de tots els punts més propencs a p que a q; i el semiplano que conté a q (h(q,p)) alberga a tots els punts més pròxims a q que a p. D'acort en açò, llavors es pot establir de forma general cóm es definix la regió de Voronói per a un lloc pi.

𝒱(pi)=⋂j=1,j≠inh(pi,pj)


𝒱(pi) està composta per l'intersecció de n−1 semiplanos que conformen una regió poligonal convexa que pot ser oberta o tancada. La regió està acotada per un màxim de n−1 vèrtiços i un màxim de n−1 arestes. Es tenen estes cantitats de vèrtiços i arestes degut a que els llocs més lluntans solen tindre associats regions de Voronói no acotades conformades per arestes i semi-arestes (arestes que tenen un vèrtiç d'inici pero no un de final).

Propietats

A continuació s'enunciaran un conjunt de propietats[1][2] del Diagrama de Voronói a on s'assumix que no pot haver quatre punts del conjunt original P en posició cocircular. En cas que esta situació no siga contemplada, llavors es deuen considerar una gran cantitat de detalls que deuen ser agregats a les diferents propietats.

  • Teorema 1. Siga P un conjunt de n llocs en el pla. Si tots els llocs són colineales, llavors Vor(P) consistix de n−1 llínees paraleles. D'una atra forma, Vor(p) és conexo i les seues arestes podrien ser segments o semi-llínees.
  • Teorema 2. Per a n≥3, el número de vèrtiços en el diagrama de Voronói d'un conjunt de nllocs en el pla és a lo més 2n−5 i el número d'arestes és a lo més 3n−6.

La següent propietat ajuda a caracterisar els vèrtiços i arestes que componen el diagrama de Voronói. No obstant, és necessari definir qué significa el círcul buit més gran de q, denotat com CP(q). Per a un punt q, CP(q) es definix com el círcul més gran que té a q com el seu centre i no conté cap atre lloc de P en el seu interior.

  • Teorema 3. Per a un diagrama de Voronói Vor(P) d'un conjunt de llocs P lo següent es complix:
    • Un punt q és un vèrtiç de Vor(P) si i solament si el seu més gran círcul buit Cp(q) conté tres o més llocs en el seu contorn.
    • El bisector entre els llocs pi i pj definix una aresta de Vor(P) si i solament si hi ha un punt q sobre el bisector tal que Cp(q) conté tant a pi i a pj en el seu contorn pero no un atre lloc.
  • Teorema 4. Cada veí més propenc del lloc pi en P definix una aresta de 𝒱(pi).
  • Teorema 5. La regió de Voronói 𝒱(pi) és oberta si i solament si pi és un punt en l'envolvente convexa del conjunt P.
  • Teorema 6. La gràfica dual del diagrama de Voronói definix la triangulació de Delaunay.

Algoritmes per a la construcció del Diagrama de Voronói

Algoritme per força bruta

Una primera aproximació per a la construcció del diagrama de Voronói consistix en explotar la geometria de cada regió de Voronói. Per cada lloc pi∈P es construirà la seua regió de Voronói per mig del càlcul explícit dels n−1 semiplanos originats pels bisectores traçats sobre els demés llocs. Posteriorment, es computarà l'intersecció d'estos n−1 semiplanos para, finalment, donar orige a 𝒱(pi).

Este algoritme té moltes desventages d'entre les quals es tenen les que a continuació es descriuen. En primera instància, el càlcul explícit dels semi-plans i la seua intersecció pot provocar problemes de precisió en la computadora generat, evidentment, una versió incorrecta de Vor(P). El segon inconvenient involucra que no es produïx informació immediata i que es puga aprofitar sobre el veïnat de cada lloc. Finalment, ya que es tracta de l'algoritme d'un algoritme ineficiente, no resulta estrany descobrir que la seua complexitat computacional siga alta. L'algoritme està en l'orde de O(n2log⁡n)

Algoritme dividix i venceràs

Este algoritme està fonamentat sobre el paradigma de disseny d'algoritmes dividix i venceràs. Donat el problema de construir el diagrama de Voronói per al conjunt P de llocs, ara es dividirà a este últim en dos subconjunts P1 i P2, en aproximadament el mateix tamany, dels que es deu trobar el seu diagrama de Voronoi independentment. Finalment, Vor(P1) i Vor(P2) deuen ser units per a poder obtindre Vor(P). No obstant, ¿quina raó existix per a que es crea que Vor(P1) i Vor(P2) tinguen alguna relació en Vor(P)?

Per a que es puga contestar l'última pregunta, és necessari definir construccions geomètriques que seran de vital importància.

Definició 1. Donat una petició P1P2 de P, siga σ(P1,P2) el conjunt d'arestes de Voronoi que són compartides per parells de regions de Voronoi 𝒱(pi∈P1) i 𝒱(pj∈P2).

La colecció d'arestes σ(P1,P2) té les següents propietats.

Teorema 7 σ(P1,P2)és el conjunt d'arestes d'una subgráfica de Vor(P) en les següents propietats:

  • σ(P1,P2) consta de cicles i cadenes d'arestes disjuntas. Si una cadena té una sola aresta, esta és una llínea recta; d'una atra forma les seues dos arestes extremes són rajos seminfinitos.
  • Si P1 i P2 són linealmente separats (si més d'un punt pertany a la llínea de separació, tots estos punts són assignats a un mateix conjunt de la partició), llavors σ(P1,P2) consistix d'una sola cadena monotónica.

En la finalitat de separar a P en dos subconjunts se li deurà ordenar sobre les abcisas i prendre la recta m que passe per la mijana, de tal sòrt que es tinguen dos subconjunts d'aproximadament el mateix tamany. Adicionalment, donada esta elecció de recta de separació, es pot dir que σ part al pla en una porció esquerra πL i una porció dreta πR. En base en açò, es té la següent propietat:

Teorema 8. Si P1 i P2 són linealmente separats per una llínea vertical en P1 a l'esquerra i P2 a la dreta, llavors el diagrama de Voronoi Vor(P) és l'unió de Vor(P1)∩πL i Vor(P2)∩πR.

A partir de l'última teorema és que es pot respondre la pregunta inicial sobre cóm es vinculen dos diagrames de Voronoi de dos particions per a generar el diagrama de Voronoi de tot el conjunt de llocs. El següent algoritme[2] establix la forma de calcular el diagrama de Voronoi per mig de la tècnica dividix i venceràs.

Procediment DIAGRAMA DE VORONOI

Pas 1. Partir a P en dos subconjunt P1 i P2, d'aproximadament el mateix tamany, per mig de la mijana en les coordenades x.

Pas 2. Construir Vor(P1) i Vor(P2) recursivament.


Pas 3. Construir la cadena polígona σ, separant a P1 i P2.

Pas 4. Descartar totes les arestes de Vor(P2) que estiguen a l'esquerra de σ. El resultat és Vor(P), el diagrama de Voronoi del diagrama sancer.

Algoritme de Fortune (agranada de recta)

Inspiració

L'algoritme de força bruta prèviament revisat té una complexitat O(n2log⁡n) , no obstant, per la teorema 2, es pot supondre que hi ha una forma molt més eficient de trobar el diagrama de Voronoi puix els seus elements constituents tenen complexitat O(n).[1] En efecte, existix este algoritme i és cridat Algoritme de Fortune[3] en honor a Steven Fortune qui ho va inventar en 1986 i la complexitat del qual és O(nlog⁡n).[1]

Càlcul del diagrama de Voronoi en ajuda de la tècnica d'agranada de recta. Es nota que conforme la recta es mou, la llínea de plaja canvia generant les regions de Voronoi dels llocs.

L'algoritme de Fortune està basat en una de les tècniques clau dins de la geometria computacional denominada agranada de recta. L'essència d'esta tècnica yacer en supondre que existix una recta ℓ que recorre el pla de dalt cap a avall (o d'esquerra a dreta, inclús en direccions opostes) i que a lo llarc del seu recorregut es interseca en les estructures que desigem processar. Quan es dona esta intersecció, es guarda certa informació de tal forma que ajude en els càlculs. És necessari que l'informació que s'haja obtingut en regions ya visitades per la recta siga invariante. És molt comú que està tècnica utilise dos tipos d'estructures de senyes: coa de prioritats a on es guarden events que no són més que punts a on la recta deu detindre's i un arbre binari de busca a on s'almagasenen els elements geomètrics que s'han intersecado en la recta i es necessita recordar per al processament futur. cal resaltar que degut a que en la computadora no es pot emular tal com el moviment continu de la recta d'agranada, es requerix idear una forma de discretisació del moviment de la recta que siga procesable en la computadora, d'ahí que els events siguen tal discretisació.

Propietats combinatòries

Per a aplicar l'agranada de recta al diagrama de Voronoi, intuitivament, es podria prendre al conjunt de llocs P=p1,…,pn com els events i d'esta manera dur l'intersecció de la recta d'agranada en el diagrama de Voronoi. No obstant, degut a que el càlcul de 𝒱(pi) depén de l'intersecció de n−1 plans, llavors no es podria mantindre el invariante de la tècnica ya que aun cuando ℓ ya haja processat un lloc, l'informació sobre la seua regió de Voronoi seguirà canviant pels llocs restants per processar. En base en açò, és imperatiu canviar la perspectiva i en lloc de mantindre l'intersecció de ℓ en Vor(P) es necessita mantindre l'informació sobre aquells llocs sobre ℓ que ya no podrà canviar pels llocs baix de ℓ.

Llínea de plaja per al diagrama de Voronoi.


Es denotarà al semi-pla tancat sobre ℓ com ℓ+. Es busca quin és la part del diagrama de Voronoi sobre ℓ que ya no podrà canviar jamai, per ad açò es té lo següent. Donat un punt q∈ℓ+, la distància d'este a qualsevol punt baix de ℓ és més gran que la distància de q a ℓ pròpiament. Ademés, el lloc més propenc q no pot estar baix de ℓ si q és a lo manco tan propenc a algun lloc pi∈ℓ+ com q lo és a ℓ. Per tant, el lloc geomètric de punts més propencs d'algun lloc que a ℓ està llimitat per una paràbola. Seguint esta llínea, el lloc geomètric de tots els punts més propencs a algun lloc sobre ℓ que a ℓ en sí mateixa està acotat per un conjunt de lo més 2n−1[1] arcs parabòlics. Este conjunt d'arcs es denomina llínea de plaja. Cada lloc pi sobre la llínea d'agranada definix una paràbola completament. La llínea de plaja conta en la propietat de monotonicidad ya que si es fa passar qualsevol recta vertical per ella, esta la interseca en exactament un punt.[1]

Llavors, en lloc de mantindre l'intersecció de Vor(P) en ℓ, es mantindrà la llínea de plaja conforme la llínea d'agranada es moga. Evidentment, no es pot representar explícitament la llínea de plaja ya que és contínua i es transforma cada que ℓ canvia de posició.

Generació d'un nou arc en la llínea de plaja.

Un arc pot aparéixer en la llínea de plaja quan ℓ processa un nou lloc, d'ahí que açò prenga el nom de event de lloc. En este moment una nova paràbola (en forma de llínea vertical puix el costat recte és infinitesimalmente menut) trenca sobre la llínea de plaja. Conforme la llínea de plaja comença a baixar, la recentment creada paràbola comença a fer-se més amplia. Ademés, conforme va creixent la paràbola es generen interseccions en atres paràboles en la llínea de plaja, lo que comença a traçar les arestes[1] del diagrama de Voronoi.

Un segon event de la llínea d'agranada sorgix quan un arc β es fa tan chicotet que es convertix en un punt. Quan es presenta açò, les interseccions que tenia β en els atres arcs (β′ a l'esquerra i β″ a la dreta) es junten. Esta trobada dels punts d'intersecció implica que dos arestes del diagrama s'estan trobat. En conseqüència, s'ha format un vèrtiç q del diagrama de Voronoi. Gràficament, q és el centre d'un círcul que passa pels llocs p′,p i p″ corresponents a β′,β i β″, respectivament. Quan ℓ alcança el punt més baix d'este círcul, s'ostenta un event de círcul.

Estructures de senyes i algoritme

L'algoritme de Fortune necessita de tres tipos d'estructures de senyes:

  1. Estructura de senyes que ajude a guardar la porció del diagrama calculada fins al moment. Per a açò s'ampra una llista doblement conectada d'arestes DCEL.[1] Es referirà a este com 𝒟.
  2. Coa de prioritats 𝒬 que permeta guardar els events de lloc i de círcul que deu processar la llínea d'agranada.
  3. Arbre de busca binari balancejat 𝒯 que guarde la llínea de plaja. Ya que no es pot guardar directament la llínea de plaja per la seua naturalea contínua, es fa lo següent. En els fulls 𝒯, es guarden els arcs de la llínea de plaja, caracterisats pel lloc que els definix, mantenint l'orde com el que s'apreciaria en la llínea de plaja realment. Per la seua banda els nodos intermijos representen els punts de quebre (a on un arc trenca en la llínea de plaja) com túpalas <pi,pj>, a on pi denota la paràbola a l'esquerra i pj la corresponent a la dreta.


El següent pseudocódigo es basa en el que es presenta en l'obra de Mark de Berg et al.[1]

Algoritme DiagramaVoronoi(P)

Entrada. Conjunt de llocs P=p1,…,pn en el pla.

Eixida Vor(P) dins d'una caixa de restricció en 𝒟.

Inicializar 𝒬 en tots els llocs; inicializar 𝒯 com a buit i una DCEL 𝒟 buida.
while 𝒬 no estiga buida
Remoure l'event en la coordenadana y més gran de 𝒬.
if l'event és un event de lloc en pi then
ManejarEventoSitio(pi)
else ManejarEventoCirculo(γ), a on γ representa el full de 𝒯 representant l'arc que desapareixerà.
Computar caixa de restricció que continga tots els vèrtiços de Vor(P) dins i una les semi-arestes cap a la caixa.


ManejarEventoSitio(pi)

Si 𝒯 està buit, insertar pi. De lo contrari fer els següents passos.
Buscar en 𝒯 l'arc α verticalment sobre pi. Si el full α té una busca cap a 𝒬, llavors és una falsa alarma i deu ser eliminat de 𝒬.
Reemplaçar el full de 𝒯 que representa a α en un subárbol en tres fulls. El full en el centre guarda el lloc pi i atres dos guarden a pj que originalment estava en α. Guardar les túplas <pj,pi> i <pi,pj> representant els nous punts de quebre.
Crear nous registres de semi-arestes en 𝒟 per a l'aresta que separa a 𝒱(pi) i 𝒱(pj), que serà traçada pels punts de quebre.
Checar les tripleta d'arcs consecutius a on el nou arc de pi és l'arc esquerre per a vore si els punts de quebre convergixen.


ManejarEventoCirculo(γ)

Borrar el full γ que representa l'arc a desaparéixer α de 𝒯. Actualisar túplas que representen els punts de quebre. Reebalancear 𝒯. Eliminar de 𝒬 tots els events que involucren a α.
Afegir el centre del círcul causant de l'event com un registre de vèrtiç en 𝒟. Crear dos semi-arestes corresponents als nous punts de quebre de la llínea de plaja.
Checar la nova triplet d'arcs consecutius que tenia a α en el mig si els dos punts de quebre convergixen. De ser aixina, insertar-ho l'event corresponent en 𝒬. Fer lo mateix per a la triplet a on α estava a la dreta.
Complexitat

L'algoritme s'eixecuta en O(nlog⁡n) i usa O(n) almagasenament. Açò es deu a que les operacions sobre 𝒯 i en 𝒬 prenen O(log⁡n).[4] Les operacions en la DCEL prenen temps constant.[1] Quan es processa un event s'eixecuta un número constant d'operacions de tals operacions. I ya que es té O(n) events (per la teorema 2), llavors la complexitat és O(nlog⁡n). Per la seua banda, l'almagasenament és llineal novament per la teorema 2.

Generalisació a ℝn

Teselació de Voronói d'un conjunt de punts aleatori sobre el pla.

Per a cada conjunt topològic discret S de punts en un espai euclídeo i para casi tot punt x, existix un punt de S que és el més propenc a x. (Ací, el terme casi s'usa per a indicar que existixen excepcions en les quals x pot equidistar de dos o més punts de S.)


Si S conté només dos punts, a i b, llavors el conjunt de tots els punts que equidistan d'abdós és un hiperplano de codimensión 1. Eixe hiperplano és la frontera entre els punts més propencs a a que a b, i els punts més propencs a b que a a. De fet, eixe hiperplano és el pla bisector del segment que unix a i b. Més en general, el conjunt de punts més propencs a un punt c de S que a cap atre punt de S (conca d'atracció de c) és l'interior d'un politopo convexo (possiblement no acotat) cridat domini de Dirichlet o cela de Voronói de c. El conjunt de tots eixos politopos constituïx una teselació completa de l'espai euclídeo, cridada teselació de Voronói associada a S.

Si la dimensió de l'espai euclídeo és només 2, com en el pla euclídeo, llavors resulta molt senzill dibuixar teselaciones de Voronoi, com les de la figura adjunta.


Referències

  1. ↑ 1,00 1,01 1,02 1,03 1,04 1,05 1,06 1,07 1,08 1,09 de Berg, Mark; Cheong, Otfried; van Kreveld, Marc; Overmars, Mark (2008). «7», Computational Geometry: Algorithms and Applications, tercera edició (en anglés), Springer-Verlag Berlín Heidelberg, pp. 147-171. ISBN 978-3-540-77973-5.
  2. ↑ 2,0 2,1 Preparata, Franco P.; Shamos, Michael Ian (1985). «5», David Gries (ed.). Computational Geometry: an introduction (en anglés), Springer-Verlag, pp. 204-223. ISBN 0-387-96131-3.
  3. ↑ Steven Fortune. A sweepline algorithm for Voronoi diagrams. Proceedings of the second annual symposium on Computational geometry. Yorktown Heights, New York, United States, pp.313–322. 1986. ISBN 0-89791-194-6. ACM Digital LibrarySpringerLink
  4. ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Clifford, Stein (2009). Introduction to Algorithms, tercera edició (en anglés), MIT Press. ISBN 978-0-262-03384-8.