biblioteca tessellation C ++ 2D?

Question

Eu tenho alguns polígonos convexos armazenados como um vetor de STL de pontos (mais ou menos). Quero tessellate -los muito rapidamente, de preferência em pedaços de forma bastante equilibrada porte, e sem "lascas" .

Vou usá-lo para explodir alguns objetos em pequenos pedaços. Alguém sabe de uma boa biblioteca para polígonos Tessellate (partição-los em uma malha de polígonos ou triângulos convexas menores)?

Eu olhei para alguns que eu encontrei on-line já, mas eu não posso mesmo levá-los para compilar. Estes tipo acadêmico não dão muita consideração pela facilidade de uso.

Answer 1

CGAL tem pacotes para resolver este problema. O melhor seria provavelmente para usar a 2D Polygon Partitioning pacote. Por exemplo, você poderia gerar partição y-monótona de um polígono (obras para polígonos não-convexos, bem) e você terá algo parecido com isto:

O tempo runnning é O (N log N).

Em termos de facilidade de utilização este é um pequeno exemplo de código gerar um polígono aleatória e dividindo-o (com base em neste exemplo o manual ):

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Partition_traits_2<K>                         Traits;
typedef Traits::Point_2                                     Point_2;
typedef Traits::Polygon_2                                   Polygon_2;
typedef std::list<Polygon_2>                                Polygon_list;
typedef CGAL::Creator_uniform_2<int, Point_2>               Creator;
typedef CGAL::Random_points_in_square_2<Point_2, Creator>   Point_generator;   


int main( )
{
   Polygon_2    polygon;
   Polygon_list partition_polys;

   CGAL::random_polygon_2(50, std::back_inserter(polygon),
                      Point_generator(100));

   CGAL::y_monotone_partition_2(polygon.vertices_begin(),
                                polygon.vertices_end(),
                                std::back_inserter(partition_polys));

   // at this point partition_polys contains the partition of the input polygons
   return 0;
}

Para instalar CGAL, se você estiver no Windows, você pode usar o instalador para obter a biblioteca pré-compilada, e há instalações guias para todas as plataformas em desta página . Pode não ser o mais simples de instalar, mas você começa a biblioteca geometria computacional mais utilizado e robusto existe lá fora, e o CGAL lista de discussão é muito útil para responder a perguntas ...

Answer 2

poly2tri parece um muito bom leve biblioteca C ++ para 2D Delaunay triangulação.

Answer 3

Como balint.miklos mencionado em um comentário anterior, do Shewchuk triângulo pacote é muito bom. Eu usei-me muitas vezes; ele integra-se bem em projectos e existe o href="http://www.compgeom.com/~piyush/scripts/triangle/" rel="nofollow noreferrer"> ++ C interface de

Answer 4

Se você não quiser construir toda a GCAL em seu aplicativo -. Esta é provavelmente mais simples de implementar

http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml

Answer 5

Eu apenas comecei olhando para esse mesmo problema e eu estou considerando voronoi tessellation. O polígono original será obter uma dispersão de pontos aleatórios meias que serão os centros das células Voronoi, o mais uniformemente distribuídos são o mais regular tamanho das células será, mas eles não devem ser em uma grade perfeita caso contrário, os polígonos interiores serão todos têm a mesma aparência. Então a primeira coisa é ser capaz de gerar os pontos- centro celular gerando-los sobre a caixa delimitadora do polígono de origem e um interior test / exterior não deve ser muito difícil.

As bordas de Voronoi são as linhas pontilhadas nesta imagem, e são uma espécie de complemento da triangulação de Delaunay. Todos os pontos do triângulo afiadas tornar-se embotada:

Impulso tem algumas funcionalidades voronoi: http://www.boost.org/doc/ libs / 1_55_0 / libs / polígono / doc / voronoi_basic_tutorial.htm

O próximo passo é criar os polígonos de Voronoi. Voro ++ http://math.lbl.gov/voro++/ está 3D orientada, mas sugere-se em outro lugar que aproximadamente estrutura 2d vai funcionar, mas ser muito mais lento do que o software orientado para voronoi 2D. O outro pacote que parece ser muito melhor do que um projeto órfãos Início acadêmica aleatória é https://github.com/ aewallin / openvoronoi .

Parece que OpenCV utilizados para apoiar fazer algo nesse sentido, mas foi preterido (mas o c-api ainda funciona?). cv :: distTransform ainda é mantida, mas opera em pixels e gera saída de pixel, não vértices e estruturas de dados borda do polígono, mas pode ser suficiente para as minhas necessidades, se não o seu.

Vou atualizar isso uma vez eu aprendi mais.

Answer 6

Um pouco mais detalhes sobre sua entrada e saída desejada pode ser útil.

Por exemplo, se você está apenas tentando obter os polígonos em triângulos, um ventilador triângulo provavelmente funcionaria. Se você está tentando cortar um polígono em pequenos pedaços, você poderia implementar algum tipo de marcha quadrados.

---

Ok, eu fiz uma má suposição - eu assumi que praças marchando seria mais semelhante ao marchando cubos. Acontece que é muito diferente, e não o que eu quis dizer ..: |

Em qualquer caso, para responder diretamente sua pergunta, eu não sei de qualquer biblioteca simples que faz o que você está procurando. Concordo sobre a usabilidade do CGAL. ??

O algoritmo que eu estava pensando era basicamente polígonos divisão com linhas, onde as linhas são uma grade, para que a maioria obter quads. Se você tivesse um cruzamento-line polígono, a implementação seria simples. Outra maneira de colocar este problema está tratando o polígono 2d como uma função, e sobrepor uma grade de pontos. Então você acabou de fazer algo semelhante ao marchando cubos .. se todos os 4 pontos estão no polígono, fazer um quad, se 3 estão em fazer um triângulo, 2 estão em fazer um retângulo, etc. provavelmente um exagero. Se você queria ligeiramente polígonos irregulares de aparência você pode embaralhar as localizações dos pontos de grade.

Por outro lado, você poderia fazer uma subdivisão estilo Catmull-Clark, mas omitir o alisamento. O algoritmo é basicamente você adicionar um ponto no centróide e no ponto médio de cada borda. Então, para cada canto do polígono original que você fazer um novo polígono menor que liga o ponto médio borda anterior para o canto, o canto, o próximo ponto médio de ponta, e o baricentro. Esta telhas do espaço, e terá ângulos semelhantes a seu polígono de entrada.

Então, muitas opções, e eu gosto soluções de brainstorming, mas eu ainda não tenho idéia o que você está pensando em usar isso para. É este para criar malhas destrutíveis? Você está fazendo algum tipo de processamento de malha que requer elementos menores? Tentando evitar artefatos de sombreamento Gouraud? Isto é algo que funciona como um pré-processo ou em tempo real? Quão importante é a exatidão? Mais informações resultaria em melhores sugestões.

Answer 7

Se você tem polígonos convexos, e você não está muito preso a qualidade, então este é realmente simples - basta fazer recorte ouvido . Não se preocupe, não é O (n ^ 2) para polígonos convexos. Se você fizer isso, ingenuamente (ou seja, você cortar as orelhas como encontrá-los), então você vai ter um ventilador triângulo, que é um pouco de drag se você está tentando evitar lascas. Duas heurísticas triviais que podem melhorar a triangulação devem

1. Separar os ouvidos, ou se isso é muito lento
2. Escolha uma orelha ao acaso.

Se você quiser um triangulador mais robusto baseado em corte de orelha, veja FIST .