Qual é a diferença entre a ferramenta Criar polígonos de Thiessen (ArcGIS) e a ferramenta Voronoi Polygons (QGIS)?

12

Os polígonos de Thiessen são a mesma coisa que os polígonos de Voronoi? Estou usando o ArcMap 10 e também o QGIS 2.4 e gostaria de saber a diferença exata (se houver) entre os dois métodos.

Maria Karypidou
fonte
Você poderia, por favor, descrever qualquer pesquisa que tenha feito sobre o assunto e sobre o que você precisa de esclarecimentos?
Aaron
1
Na verdade, estávamos discutindo se as duas tags devem ser combinadas em meta: meta.gis.stackexchange.com/questions/3677/…
Chris W

Respostas:

20

Sim, eles são a mesma coisa. No campo do SIG, tendemos a nos referir a eles como polígonos de Thiessen, depois do meteorologista americano que freqüentava seu uso. Em outros campos, particularmente matemática e ciência da computação, são geralmente chamados de diagramas de Voronoi, em homenagem ao matemático Georgy Voronyi. Ambos os usos são aceitáveis.

WhiteboxDev
fonte
Embora o conceito é o mesmo, gostaria de saber se a implementação em cada software é ...
Chris W
@ ChrisisW Essa é uma pergunta interessante, mas difícil de responder, eu acho. Eu acho que, como a maioria dos problemas espaciais, há mais de uma maneira de chegar à solução, o que sugere que existem implementações diferentes.
WhiteboxDev
Desculpe, eu estava mais sendo retórica. Eu só queria salientar que, embora os conceitos sejam os mesmos, e você geralmente obtenha o mesmo resultado (ou pelo menos o tipo de resultado) nos dois softwares, como eles funcionam, podem não ser os mesmos e os resultados podem não ser exatamente o mesmo. Basicamente, optar por ler mais sobre a questão do que realmente pode ser necessário, mas pode importar se você for aprofundado o suficiente.
Chris W
@ Chrishr Sim, foi assim que interpretei sua pergunta. E é um ponto realmente válido que você levanta. Eu acho que os detalhes da implementação em dois GIS que oferecem uma ferramenta de polígono de Thiessen levariam a pequenas diferenças da mesma maneira que uma ferramenta de acumulação de fluxo ou bacia hidrográfica aplicada aos mesmos dados em dois GIS diferentes pode diferir ligeiramente. Há muita coisa entre o funcionamento teórico de um algoritmo e sua implementação de código de computador.
WhiteboxDev
@ChrisW Aliás, é exatamente sua pergunta que me levou à noção de software de 'acesso aberto' e do Whitebox GAT em primeiro lugar. Se o OP perguntasse como a ferramenta de polígono de Thiessen do Whitebox GAT, a resposta seria tão simples quanto pressionar o botão 'Exibir código' na caixa de diálogo da ferramenta. Veja o blog no link
WhiteboxDev 16/14
9

Não podemos saber a diferença exata porque não podemos ver o código fonte da implementação da ESRI. No entanto, parece de relance superficial que as duas implementações, de fato, utilizam o mesmo método que é uma tradução aproximada do algoritmo clássico de sweepline de Steven Fortune .

Aqui você pode dar uma olhada no código-fonte real usado no QGIS. Inclui a seguinte descrição:

For programmatic use two functions are available:

   computeVoronoiDiagram(points)

        Takes a list of point objects (which must have x and y fields).
        Returns a 3-tuple of:

           (1) a list of 2-tuples, which are the x,y coordinates of the
               Voronoi diagram vertices
           (2) a list of 3-tuples (a,b,c) which are the equations of the
               lines in the Voronoi diagram: a*x + b*y = c
           (3) a list of 3-tuples, (l, v1, v2) representing edges of the
               Voronoi diagram.  l is the index of the line, v1 and v2 are
               the indices of the vetices at the end of the edge.  If
               v1 or v2 is -1, the line extends to infinity.

   computeDelaunayTriangulation(points):

        Takes a list of point objects (which must have x and y fields).
        Returns a list of 3-tuples: the indices of the points that form a
        Delaunay triangle.

Agora não podemos ver o código proprietário da ESRI que aciona sua ferramenta , mas a descrição da documentação revela imediatamente que a base por trás de ambas as ferramentas é a mesma:

Thiessen polígonos proximais são construídos da seguinte maneira:

Todos os pontos são triangulados em uma rede irregular triangulada (TIN) que atende ao critério de Delaunay. Os bissetores perpendiculares para cada aresta do triângulo são gerados, formando as arestas dos polígonos de Thiessen. A localização na qual as bissetoras se cruzam determina a localização dos vértices do polígono de Thiessen.

As nuances reais do código que dirige os dois são obviamente diferentes, pois foi demonstrado que a tradução de Bill Simon conhece bugs que não estão presentes na versão da ESRI.

Existem (como foi declarado nos comentários acima) várias outras maneiras diferentes de gerar diagramas de Voronoi, mesmo em SIG, como essa metodologia baseada em varredura . Existem também outros métodos baseados em vetores para gerar diagramas de Voronoi no SIG.

Existem várias vantagens e desvantagens em cada um dos métodos. Por exemplo, o algoritmo da Fortune é relativamente rápido e bem documentado, mas atualmente não há maneira conhecida de gerar diagramas de Voronoi ponderados multiplicativamente usando sua implementação direta.

Os métodos raster são geralmente muito mais lentos em termos computacionais, mas permitem a criação de diferentes tipos de diagramas de Voronoi ( como os diagramas de Voronoi de ponto mais distante ) sem reinventar completamente a metodologia.

Divulgação completa: Trabalhei como assistente de pesquisa do professor que escreveu o artigo para a metodologia baseada em varredura para gerar diagramas de Voronoi.


TL; DR: Embora as implementações reais sejam um pouco diferentes, elas são baseadas no mesmo algoritmo e ambas devem produzir o mesmo resultado (além dos poucos casos extremos que produzem os bugs observados na pergunta de Dan Patterson acima).

Conor
fonte