Como representar um polígono com furo (s)?

Question

É geralmente popular para trabalhar com polígonos com seus vértices classificadas CW ou CCW em vetores (2 * 1 ou 1 * 2 matrizes). No entanto, como afirmam os polígonos com buracos vetores?

Eu estou indo para aplicar vários processos sobre esses polígonos, então eu quero uma forma de representar com o qual eu poderia trabalhar facilmente ou de forma eficiente. (Ou seja, como afirmar que tipo de polígonos no meu programa, a fim de aliviar os meus algoritmos? )

polígonos são em 2D e estou programando em MATLAB.

EDIT 1: Eu estou indo para calcular gráfico visibilidade destes polígonos (com ou sem buracos).

Answer 1

Como já foi mencionado, um polígono com furos pode ser representado como uma fronteira exterior, além de zero ou mais interiores limites, todos os quais são não sobrepostos mutuamente *. Se você usar diferente de zero enrolamento número para determinar dentro / fora, certifique-se de especificar as suas fronteiras interiores em a direcção oposta, como os limites exteriores (sentido anti-horário para o exterior e no sentido horário para o interior, ou vice-versa) de modo que os integrais de contorno são iguais a zero no interior dos furos.

FYI, tis tipo de definição / representação foi formalizada no Simples OpenGIS Características Specification ( PDF ).

Quanto representação:

Eu provavelmente ter uma matriz de células de matrizes K nx2, onde o primeiro elemento na matriz celular é o limite exterior, e os elementos restantes (se houver) na matriz celular são os limites interiores. Gostaria de usar um conjunto de células, porque pode não haver o mesmo número de pontos em cada fronteira.

* = não sobrepostos excepto em pontos individuais, por exemplo um diamante dentro de um quadrado:

Answer 2

Você pode quebrar um polígono com um buraco no meio em duas formas, sem um buraco. Quando você está fazendo integração de contorno em um plano complexo, você pode criar um "corte" de uma extremidade do polígono que traz para a borda do buraco; integrar em torno de um lado do buraco e volta; em seguida, percorrem em torno do outro lado para o segundo polígono. Você acaba com duas integrais de caminho ao longo de cada corte que se anulam mutuamente.

"gráfico de visibilidade" - isto é para um fator de cálculo vista radiação com sombreamento? Ou um ray-tracing gráficos algoritmo?

Answer 3

Um polígono, além de uma lista de blocos poligonais. Apenas certifique-se os vários polígonos não se cruzam.

O que você pretende fazer com essa coisa?

Answer 4

Parece que cada furo é apenas um polígono dentro do próprio polígono. Talvez você poderia armazenar um vetor como você descreve para o polígono exterior, em seguida, um vetor de mais vetores de polígonos para os buracos.

Answer 5

Provavelmente, você vai querer ter uma estrutura de árvore, se você quer que isso seja o mais genérico possível (ou seja, polígonos com buracos poligonais que têm polígonos dentro deles com buracos no interior que, ...). Matlab não é realmente grande em representar estruturas de árvore de forma eficiente, mas aqui está uma ideia ...

Tenha um struct-array de polígonos.

Cada polígono é uma estrutura com dois campos, 'cantos' e 'crianças'.

O campo 'cantos' contém uma matriz de (x, y) as coordenadas dos cantos, acedido como "dados {polyIdx} .corners (:, cornerIdx)".

O campo 'crianças' é um struct-array de polígonos.

Aqui está um exemplo de algum código para fazer um triângulo com as crianças falsos que são buracos (não são embora muito válido porque provavelmente eles vão se sobrepõem:

polygon = struct;
npoints = 3;
polygon.corners = rand(2,npoints);
polygon.children = struct;
nchildren = 5;
for c=1:nchildren
    polygon.children(c).corners = rand(2,npoints);
    polygon.children(c).children = struct;
end

Você pode continuar a definir de forma recursiva crianças que se alternam entre a criação de buracos e enchê-los.

Answer 6

O que exatamente você quer dizer em "um gráfico visibilidade"?

Dois polígonos "completos", dois estados possíveis, quer +1 ou -1.

Se você está representando um buraco, você tem um com o estado +1 e um com estado -1, o que representa um buraco, resultando no estado 0.
Se você tem polígonos sobrepostos, você vai acabar com o estado resultante> 1. Então você pode calcular as fronteiras de um novo polígono.
Se você tem dois polígonos com buracos que se cruzam, então primeiro calcular o estado de um novo polígono que consiste das fronteiras externas dos dois mais velhos, então lidar com buracos.

De qualquer forma, ... Eu acho que você começa o princípio geral.

Não tenho idéia como fazê-lo em Matlab, eu usei-o apenas marginalmente até agora, e mesmo que para coisas muito simples.