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

202

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

texto alternativo

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:

Igor Brejc
fonte
17
Esta não é uma questão trivial: se a deflação / inflação for pequena, nada de grave acontecerá, mas em algum momento os vértices desaparecerão. Provavelmente isso já foi feito antes, então eu diria: use o algoritmo de outra pessoa, não crie seu próprio.
287 Martijn
1
De fato, se o seu polígono é côncava para começar (como no exemplo acima), você tem que decidir o que deve acontecer no ponto onde o algoritmo ingênuo quer fazer uma auto-interseção 'polígono' ...
AakashM
Sim, o principal problema são as partes côncavas do polígono, é aí que reside a complexidade. Ainda acho que não deveria ser um problema calcular quando um determinado vértice deve ser eliminado. A questão principal é que tipo de complexidade assintótica isso exigiria.
Igor Brejc
Olá, esse também é meu problema, exceto que eu preciso fazer isso em 3D. Existe uma alternativa para a abordagem de esqueletos retos de poliedros tridimensionais descrita no artigo arxiv.org/pdf/0805.0022.pdf ?
stephanmg

Respostas:

138

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.

Polygon offsetting styles

Angus Johnson
fonte
2
Muito legal! Onde você estava há 2 anos? :) No final, tive que implementar minha própria lógica de compensação (e perdi muito tempo nela). Qual algoritmo você está usando para a compensação de polígono, BTW? Eu usei grama. Você lida com furos em polígonos?
Igor Brejc
2
Há 2 anos, eu estava procurando uma solução decente para o recorte de polígono que não estava sobrecarregada com problemas complicados de licença :). O deslocamento da aresta é obtido gerando unidades normais para todas as arestas. As junções de aresta são organizadas pelo meu cortador de polígonos, pois as orientações dessas interseções sobrepostas são opostas à orientação dos polígonos. Os furos são certamente manipulados, assim como os polígonos com auto-interseção, etc. Não há restrições para seu tipo ou número. Consulte também "Polígono Compensação pela computação Números Winding" aqui: me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf
Angus Johnson
Uau! Por um segundo, não pense que esta questão está "esquecida"! Eu olhei aqui na semana passada - eu não esperava voltar a isso! Muitíssimo obrigado!
Chris Burt-Brown
Os documentos do Clipper sobre buffer de polietileno estão aqui: angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/…
Drew Noakes
5
Para quem quer fazer isso, outra alternativa é usar o GEOS e, se você estiver usando python, o wrapper do GEOS, Shapely. Um exemplo muito bonito: toblerity.github.com/shapely/manual.html#object.buffer
Pelson
40

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

balint.miklos
fonte
12

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:

insira a descrição da imagem aqui

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:

insira a descrição da imagem aqui

Marko Letic
fonte
9

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.

Steve Jessop
fonte
5

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.

J-16 SDiZ
fonte
você conhece algum algoritmo psedo para isso?
EmptyData 14/02
5

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

J-16 SDiZ
fonte
como você infla os triângulos exatamente? Sua saída depende da triangulação? Com essa abordagem, você pode lidar com o caso ao reduzir o polígono?
balint.miklos
Tem certeza de que essa abordagem realmente funciona para a inflação de polígonos? O que acontece quando as partes côncavas do polígono são infladas a tal ponto que alguns vértices precisam ser eliminados. A questão é: quando você olha o que acontece com triângulos depois de poli. inflação, os triângulos não são inflados, mas distorcidos.
Igor Brejc
1
Igor: O algoritmo de clipping Weiler-Atherton pode lidar com o caso "alguns vértices precisam ser eliminados" corretamente;
J-16 SDiZ
@ Balint: inflar um triângulo é trivial: se você armazenar o vertrex na ordem normal, o lado direito será sempre "externo". Apenas trate esse segmento de linha como linhas, mova-os para fora e encontre a interação - eles são o novo vértice. Para a própria triangulação, pensando bem, a triangulação delaunay pode dar um resultado melhor.
J-16 SDiZ
4
Eu acho que essa abordagem pode facilmente dar maus resultados. Mesmo para um exemplo simples como quad triangulado usando uma diagonal. Para os dois triângulos aumentados, você obtém: img200.imageshack.us/img200/2640/counterm.png e a união deles não é exatamente o que você está procurando. Não vejo como esse método é útil.
balint.miklos
3

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;
    }
PainElemental
fonte
2

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
Paul R
fonte
Eu não entendo como você deve fazer algo com boost :: polygon, pois ele suporta apenas coordenadas inteiras? Digamos que tenho um polígono geral (coordenadas de ponto flutuante) e desejo expandi-lo - o que devo fazer?
David Doria
@ DavidDoria: depende de qual resolução / precisão e faixa dinâmica você precisa para suas coordenadas, mas você pode usar um int de 32 ou 64 bits com um fator de escala apropriado. Aliás, eu usei (acidentalmente) o boost :: polygon com coordenadas flutuantes no passado e parece funcionar bem, mas pode não ser 100% robusto (os documentos alertam contra isso!).
Paul R
Eu ficaria bem com "vai dar certo na maior parte do tempo" :). Eu tentei o seguinte: ideone.com/XbZeBf, mas não compila - algum pensamento?
David Doria
Não vejo nada obviamente errado, mas no meu caso eu estava usando as especializações retilíneas (polygon_90), então não sei se isso faz diferença. Já faz alguns anos desde que eu brinquei com isso.
Paul R
OK - está voltando para mim agora - você só pode usar +=com um conjunto de polígonos , não com polígonos individuais. Experimente com um vetor std :: de polígonos. (É claro que o vetor precisa conter apenas um polígono).
Paul R
1

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

Carl Witthoft
fonte
0

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

stephanmg
fonte
0

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.

user2800464
fonte