Um algoritmo para inflar / desinflar (compensar, tamponar) polígonos

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

O requisito é que as arestas / pontos do novo polígono (inflado) estejam todos à mesma distância constante dos antigos (original) polígono (na figura de exemplo que não são), pois seria necessário usar arcos para vértices inflados, mas vamos esqueça isso por enquanto;)).

O termo matemático para o que estou procurando é, na verdade, compensação de polígono interno / externo . +1 a balint por apontar isso. A nomeação alternativa é o buffer de polígono .

Resultados da minha pesquisa:

Aqui estão alguns links:

• Uma pesquisa sobre estratégias de compensação de polígonos
• Deslocamento de polígono, PROBLEMA
• Buffer de dados poligonais

Pensei em mencionar brevemente minha própria biblioteca de recorte e compensação de polígonos - Clipper .

Embora o Clipper seja projetado principalmente para operações de recorte de polígono, ele também compensa o polígono. A biblioteca é um freeware de código aberto escrito em Delphi, C ++ e C # . Tem um impulso muito livre licença , permitindo que ela seja usada em aplicativos freeware e comerciais gratuitamente.

O deslocamento de polígono pode ser realizado usando um dos três estilos de deslocamento - quadrado, redondo e esquadrado.

O polígono que você está procurando é chamado de polígono de deslocamento interno / externo na geometria computacional e está intimamente relacionado ao esqueleto reto .

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

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

Como apontado em outros comentários, também, dependendo de quão longe você planeja "inflar / desinflar" seu polígono, você pode ter conectividade diferente para a saída.

Do ponto de vista da computação: uma vez que você tenha o esqueleto reto, deverá poder construir os polígonos de deslocamento de maneira relativamente fácil. A biblioteca de código-fonte aberto e (gratuita para não-comercial) da CGAL possui um pacote implementando essas estruturas. Veja este exemplo de código para calcular polígonos de deslocamento usando CGAL.

O manual do pacote deve fornecer um bom ponto de partida sobre como construir essas estruturas, mesmo se você não usar o CGAL, e contém referências aos artigos com as definições e propriedades matemáticas:

Manual da CGAL: Deslocamento 2D de esqueleto reto e polígono

Para esses tipos de coisas, geralmente uso o JTS . Para fins de demonstração, criei este jsFiddle que usa JSTS (porta JavaScript do JTS). Você só precisa converter as coordenadas que você tem em 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 normalmente uso esse tipo de inflamento / desinflação (um pouco modificado para meus propósitos) para definir limites com raio nos polígonos desenhados em um mapa (com mapas do Leaflet ou do Google). Você acabou de converter pares (lat, lng) em coordenadas JSTS e tudo o resto é o mesmo. Exemplo:

Parece-me que o que você quer é:

• Começando em um vértice, olhe no sentido anti-horário ao longo de uma borda adjacente.
• Substitua a borda por uma nova borda paralela colocada à distância dà "esquerda" da antiga.
• Repita para todas as arestas.
• Encontre as interseções das novas arestas para obter os novos vértices.
• Detecte se você se tornou um polígono cruzado e decida o que fazer. Provavelmente adicione um novo vértice no ponto de cruzamento e livre-se de alguns antigos. Não tenho certeza se existe uma maneira melhor de detectar isso do que apenas comparar todos os pares de arestas não adjacentes para ver se a interseção delas está entre os dois pares de vértices.

O polígono resultante fica à distância necessária do polígono antigo "suficientemente longe" dos vértices. Perto de um vértice, o conjunto de pontos à distância ddo polígono antigo não é, como você diz, um polígono; portanto, o requisito conforme indicado não pode ser cumprido.

Não sei se esse algoritmo tem um nome, código de exemplo na web ou uma otimização diabólica, mas acho que descreve o que você deseja.

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

A biblioteca JTS deve fazer isso por 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, consulte também o Guia do desenvolvedor: http://www.vividsolutions.com/jts/bin/JTS%20Developer%20Guide.pdf

Cada linha deve dividir o plano para "dentro" e "contorno"; você pode descobrir isso usando o método usual do produto interno.

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

Considere todo par de linhas vizinhas (linhas, não segmento de linha), encontre a interseção. Estes são o novo vértice.

Limpe o novo vértice removendo as peças que se cruzam. - nós temos alguns casos aqui

a) Caso 1:

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

se você gastá-lo por um, você conseguiu o seguinte:

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

7 e 4 se sobrepõem. Se você vir isso, remova esse ponto e todos os pontos intermediários.

b) caso 2

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

se você gastá-lo por dois, você conseguiu o seguinte:

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

Para resolver isso, para cada segmento de linha, você deve verificar se ele se sobrepõe aos últimos segmentos.

c) caso 3

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

despesa de 1. este é um caso mais geral para o caso 1.

d) caso 4

igual ao case3, mas gasta em dois.

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

No caso 4, você mantém uma pilha de vértices. Você pressiona quando encontra linhas sobrepostas à última linha e a abre quando obtém a última linha. - exatamente como você faz no casco convexo.

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

1. Faça uma triangulação , não precisa ser delaunay - qualquer triangulação faria.

2. Encha cada triângulo - isso deve ser trivial. se você armazenar o triângulo na ordem anti-horária, mova as linhas para o lado direito e faça a interseção.

3. Mesclá-los usando um algoritmo de recorte Weiler-Atherton modificado

Muito obrigado a Angus Johnson por sua biblioteca de clipper. Existem bons exemplos de código para fazer o material de recorte na página inicial do clipper em http://www.angusj.com/delphi/clipper.php#code, mas não vi um exemplo de compensação de polígono. Então, pensei que talvez seja útil 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 o boost :: polygon - a documentação está um pouco ausente, mas você deve encontrar os métodos resizee bloat, e também o +=operador sobrecarregado , que realmente implementam o buffer. Assim, por exemplo, aumentar o tamanho de um polígono (ou um conjunto de polígonos) em algum valor pode ser tão simples quanto:

poly += 2; // buffer polygon by 2

Com base nos conselhos do @ JoshO'Brian, parece que o rGeospacote na Rlinguagem implementa esse algoritmo. Veja rGeos::gBuffer.

Existem algumas bibliotecas que podem ser usadas (também utilizáveis ​​para conjuntos de dados 3D).

1. https://github.com/otherlab/openmesh
2. https://github.com/alecjacobson/nested_cages
3. http://homepage.tudelft.nl/h05k3/Projects/MeshThickeningProj.htm

Também é possível encontrar publicações correspondentes para essas bibliotecas para entender os algoritmos com mais detalhes.

O último possui menos dependências e é independente e pode ler em arquivos .obj.

Muitas felicidades, Stephan

Uso geometria simples: Vetores e / ou Trigonometria

1. Em cada canto, encontre o vetor médio e o ângulo médio. Vetor médio é a média aritmética dos dois vetores unitários definidos pelas arestas do canto. Ângulo médio é a metade do ângulo definido pelas arestas.

2. Se você precisar expandir (ou contrair) seu polígono pela quantidade de d de cada aresta; você deve sair (in) pela quantidade d / sin (midAngle) para obter o novo ponto de canto.

3. Repita isso para todos os cantos

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