Polígonos de Voronoi – parte I

09/03/2022

Se desenharmos um conjunto de pontos pj {p1, …, pn} sobre uma superfície plana, essa superfície pode ser particionada no mesmo número de polígonos Rj {R1, …, Rn} cumprindo a condição de que todos os pontos x dentro do polígono Rk estão mais próximos do ponto pk do que de qualquer outro pj. Esses polígonos também são chamados de células.

Expresso algebricamente, Rk = { xX | d(x, px) d(x, pj) para jk }

Na imagem à esquerda, estão representados os polígonos (células) de Voronoi correspondentes aos 22 jogadores em um campo de futebol. Os polígonos verdes correspondem aos jogadores de um time e os marrons aos do time oposto. Desde que a bola esteja dentro do polígono de Voronoi de um jogador, ele terá vantagem para chegar antes de qualquer outro rival.

Para o caso particular de conjuntos de pontos pj equidistantes entre si, os polígonos de Voronoi têm a forma de hexaedros regulares.

A imagem à direita mostra o sistema desenvolvido na Comuna de Las Condes, em Santiago do Chile, para manter distâncias entre os pedestres que esperam na calçada para atravessar na passadeira. Os traços verdes representariam os pontos pj e os hexágonos brancos os limites das células Rj. Se todos estiverem localizados no centro, ficarão equidistantes uns dos outros, reduzindo as chances de propagação viral.

A teoria é simples e a prática também; softwares como o QGIS permitem o cálculo e a representação de um número ilimitado de polígonos associados aos pontos de referência correspondentes.

Por exemplo, poderíamos representar os polígonos de Voronoi cobrindo toda a superfície terrestre associada a todos os centros urbanos, representados por um ponto. Numa futura notícia veremos a sua utilização para a localização de subestações e antenas para telecomunicações 5G.

Para mais informações, entre em contato com Daniel Sánchez Castán (dsanchez@ingenieros-im3.com)