Um algoritmo para encher / esvaziar (compensação, tamponantes) polígonos

https://stackoverflow.com/questions/1109536

12-09-2019
|

Pergunta

Como eu "inflar" um polígono? Ou seja, eu quero fazer algo semelhante a isto:

text alt

A exigência é que as bordas da nova (inflado) do polígono / pontos estão todos na mesma constante distância do (original) antiga de polígono (na imagem de exemplo não são, desde então, teria que usar arcos para vértices inflacionados , mas vamos esquecer que, por agora;)).

O termo matemático para o que eu estou procurando é realmente para dentro / para fora polígono offseting . +1 para Balint para apontar isto. A nomeação alternativa é polígono buffer .

Resultados de busca:

Aqui estão alguns links:

Solução

Eu pensei que eu poderia mencionar brevemente minha própria recorte polígono e compensação biblioteca - Clipper .

Enquanto Clipper é projetado principalmente para operações polígono de recorte, ele faz polígono compensação também. A biblioteca é open source gratuito escrito em Delphi, C ++ e C # . Tem um licença impulso muito livre permitindo que ele seja usado em ambos freeware e aplicações comerciais sem cobrança.

Polygon compensação pode ser realizada utilizando um dos três estilos de compensação -. Quadrado, redondo e mitered

Polígono estilos de compensação

Outras dicas

O polígono que você está procurando é chamado para dentro / para fora compensado polígono na geometria computacional e está intimamente relacionado com o reta esqueleto .

Estes são vários polígonos de deslocamento para um polígono complicado:

E este é o esqueleto direto para outro polígono:

Como apontado em outros comentários, bem como, dependendo de quão longe você pretende "inflar / desinflar" seu polígono você pode acabar com conectividade diferente para a saída.

Do ponto de vista computacional: uma vez que você tem o esqueleto reto deve ser capaz de construir os polígonos compensado de forma relativamente fácil. A fonte aberto e (livre para não-comercial) CGAL biblioteca tem um pacote de implementação destas estruturas. Consulte este exemplo de código para calcular compensado polígonos usando CGAL. ??

O manual de pacotes deve dar-lhe uma boa ponto de partida sobre como construir essas estruturas, mesmo se você não estiver indo para usar CGAL, e contém referências aos papéis com as definições matemáticas e propriedades:

CGAL manual: 2D Hetero Esqueleto e Polygon Compensação

Parece-me que o que você quer é:

A partir de um vértice, cara anti-horário ao longo de uma borda adjacente.
Substitua a borda com uma borda nova, paralela colocada no d distância para a "esquerda" do antigo.
Repita o procedimento para todas as bordas.
Encontre as intersecções das novas arestas para obter os novos vértices.
Detectar se você se tornou um polígono cruzados e decidir o que fazer sobre isso. Provavelmente adicionar um novo vértice no ponto de passagem e se livrar de algumas das antigas. Eu não tenho certeza se há uma maneira melhor de detectar isso do que apenas comparar cada par de bordas não adjacentes para ver se as suas mentiras de intersecção entre os dois pares de vértices.

As mentiras polígono resultante à distância necessária do antigo polígono "suficientemente longe" dos vértices. Perto de um vértice, o conjunto de pontos em d distância do antigo polígono é, como você diz, não um polígono, por isso a exigência como indicado não pode ser cumprida.

Eu não sei se este algoritmo tem um nome, código de exemplo na web, ou uma otimização de diabólico, mas eu acho que descreve o que você quer.

Para estes tipos de coisas que eu costumo usar JTS . Para fins de demonstração eu criei este jsFiddle que usos JSTS (JavaScript porta de STC). Você só precisa converter as coordenadas que você tem que coordenadas JSTS:

function vectorCoordinates2JTS (polygon) {
  var coordinates = [];
  for (var i = 0; i < polygon.length; i++) {
    coordinates.push(new jsts.geom.Coordinate(polygon[i].x, polygon[i].y));
  }
  return coordinates;
}

O resultado é algo como isto:

Informações adicionais : Eu costumo usar este tipo de inflar / desinflar (um pouco modificado para os meus propósitos) para estabelecer limites de raio em polígonos que são desenhadas em um mapa (com mapas panfleto ou do Google) . Você apenas converter (LAT, LNG) pares de coordenadas JSTS e tudo o resto é o mesmo. Exemplo:

Cada linha deve dividir o avião para "dentro" e "esboço"; você pode descobrir isso usando o habitual método produto interno.

Mover todas as linhas para fora por alguma distância.

Considere todas par de linhas vizinhos (linhas, não segmento de linha), encontrar a interseção. Estes são o novo vértice.

Cleanup o novo vértice, removendo quaisquer partes que se cruzam. - temos um caso alguns aqui

(a) Caso 1:

 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2

Se você gasta-lo por um, você tem isso:

0----a----3
|    |    |
|    |    |
|    b    |
|         |
|         |
1---------2

7 e 4 sobreposição .. Se você ver isso, você remover este ponto e todos os pontos entre eles.

(b) caso 2

 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2

Se você gasta-lo por dois, você tem isso:

0----47----3
|    ||    |
|    ||    |
|    ||    |
|    56    |
|          |
|          |
|          |
1----------2

Para resolver isso, para cada segmento de linha, você tem que verificar se ele sobreposição com últimos segmentos.

       4--3
 0--X9 |  |
 |  78 |  |
 |  6--5  |
 |        |
 1--------2

expend em 1. este é um caso mais geral para o caso 1.

(d) caso 4

mesmo que case3, mas expend por dois.

Na verdade, se você pode lidar com caso 4. Todos os outros casos são caso apenas especial dele com alguma linha ou vértice sobreposição.

Para fazer caso 4, você mantém uma pilha de vértice .. você empurrar quando você encontrar linhas sobrepostas com última linha, pop-lo quando chegar a última linha. - assim como o que você faz em convexo de casco

Aqui está uma solução alternativa, veja se você gosta deste melhor.

Do uma triangulação , ele não tem que ser Delaunay -. qualquer triangulação faria
Encha cada triângulo - este deve ser trivial. se você armazenar o triângulo na ordem anti-horário, basta mover as linhas para-lado direito e fazer cruzamento.
Merge-los usando um Weiler-Atherton recorte algoritmo

No mundo do GIS um usa buffer negativo para esta tarefa: http://www-users.cs.umn.edu/~npramod/enc_pdf .pdf

O JTS biblioteca deve fazer isso para você. Consulte a documentação para a operação de buffer: http: / /tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/operation/buffer/package-summary.html

Para uma visão geral ver também o Guia do desenvolvedor: http://www.vividsolutions.com/jts/bin/JTS%20Developer % 20Guide.pdf

Um grande obrigado ao Angus Johnson para sua biblioteca clipper. Há amostras de código bom para fazer as coisas recorte na homepage clipper em http: // www .angusj.com / Delphi / clipper.php # código mas eu não vi um exemplo para polígono compensação. Então eu pensei que talvez seja de uso para alguém se eu postar meu código:

    public static List<Point> GetOffsetPolygon(List<Point> originalPath, double offset)
    {
        List<Point> resultOffsetPath = new List<Point>();

        List<ClipperLib.IntPoint> polygon = new List<ClipperLib.IntPoint>();
        foreach (var point in originalPath)
        {
            polygon.Add(new ClipperLib.IntPoint(point.X, point.Y));
        }

        ClipperLib.ClipperOffset co = new ClipperLib.ClipperOffset();
        co.AddPath(polygon, ClipperLib.JoinType.jtRound, ClipperLib.EndType.etClosedPolygon);

        List<List<ClipperLib.IntPoint>> solution = new List<List<ClipperLib.IntPoint>>();
        co.Execute(ref solution, offset);

        foreach (var offsetPath in solution)
        {
            foreach (var offsetPathPoint in offsetPath)
            {
                resultOffsetPath.Add(new Point(Convert.ToInt32(offsetPathPoint.X), Convert.ToInt32(offsetPathPoint.Y)));
            }
        }

        return resultOffsetPath;
    }

Uma outra opção é usar boost :: polígono - a documentação é um pouco carente, mas você deve achar que os métodos resize e bloat, e também o operador += sobrecarregado, o que realmente implementar buffering. Assim, por exemplo, aumentar o tamanho de um polígono (ou um conjunto de polígonos) por algum valor pode ser tão simples como:

poly += 2; // buffer polygon by 2

Com base no parecer de @ JoshO'Brian, parece que o pacote rGeos nos implementos língua R este algoritmo. Veja rGeos::gBuffer.

Há um par de bibliotecas pode-se usar (Também pode ser usado para conjuntos de dados 3D).

Pode-se também encontrar publicações para essas bibliotecas correspondente a entender os algoritmos em mais detalhes.

O último tem menos dependências e é auto-suficiente e pode ler em obj arquivos.

Os melhores cumprimentos, Stephan

Eu uso geometria simples: vetores e / ou Trigonometria

Em cada canto encontrar o vetor médio e ângulo médio. Intermédia vector é a média aritmética dos dois vectores unitários definidos pelas arestas de canto. Ângulo de idade é a metade do ângulo definido pelas bordas.
Se você precisa para expandir (ou contrato) seu polígono pela quantidade de d de cada margem; você deve sair (em) pelo montante d / sin (midAngle) para obter o novo ponto de canto.
Repita esse procedimento para todos os cantos

*** Tenha cuidado com a sua direcção. Faça CounterClockWise teste utilizando os três pontos que definem o canto; para descobrir o caminho que está fora ou dentro.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow