Jogo de quebra-cabeça: recorte de polígonos não convexos nas figuras

7

Eu tenho uma figura original no arquivo SVG. Preciso dividi-lo aleatoriamente em partes, um exemplo especificado abaixo:
imagem de amostra
Eu tenho uma idéia, para usar para particionar o diagrama de Voronoi (algoritmo da Fortune). Posso então alterar a linha de interseção das figuras para dar uma curvatura? Pode ser obtido para identificar cada forma como um caminho? Para criar um jogo, usarei o cocos2d-x.

Crazy D0G
fonte

Respostas:

2

Acho que você teve a ideia certa, mas a execução será imensamente desafiadora. Eu presumo que quando você diz 'em um arquivo SVG', você quer dizer que a forma é definida por um (ou mais - seu número de amostra tem um furo interno!) Caminhos de traçado. Infelizmente, os caminhos SVG podem ser notavelmente complicados, com curvas de Bezier quadráticas e cúbicas e segmentos de arco elíptico. A interseção de uma linha com qualquer uma delas é um problema resolvido, mas altamente não trivial, e até a questão de parametrizar as curvas de Bezier para dividi-las em duas no ponto de interseção é um pouco complicada - basicamente, o que você procura é complexo o suficiente para levar um pequeno livro para responder, não uma postagem no fórum! Dito isto, existem várias excelentes referências por aí; o curto curtoA versão da resposta é que você deseja usar a subdivisão recursiva junto com a chamada propriedade 'diminuição da variação' da curva de Bezier (essencialmente, a propriedade que uma curva de Bezier está contida no casco convexo de seus pontos de controle) para diminuir os possíveis locais de uma interseção (e observe que uma linha pode ter vários pontos de interseção, e esse é outro caso especial que você deve levar em consideração). E, depois de resolver o problema de interseção, você ainda terá um longo caminho pela frente - terá uma tonelada de contabilidade para acompanhar os segmentos de curva e linha e particioná-los corretamente em pedaços. Isso não é para desencorajar você; apenas esteja ciente da magnitude do que você está tentando fazer!

Felizmente, sua outra pergunta - 'posso mudar a linha de interseção das figuras para dar curvatura?' - tem uma resposta mais fácil: absolutamente. Como você já está em terreno SVG, eu usaria as curvas de Bezier aqui também: primeiro, escolha cinco pontos p1..p5 ao longo do segmento de linha que você deseja 'curvar', provavelmente um pouco aleatório em intervalos aproximadamente igualmente espaçados ; desloque-os a uma pequena distância aleatória da linha e use-os como pontos de controle de duas curvas de Bezier separadas, uma usando os pontos p0, p1, p2, p3 e a outra usando os pontos p3, p4, p5 e p6 (onde p0 e p6 aqui estão os dois pontos finais do segmento de linha original). Você também pode tirar proveito da propriedade do casco convexo da curva de Bezier, certificando-se de que seus pontos deslocados não t deslocar muito longe, de modo que as duas regiões dos dois lados da (s) curva (s) ainda sejam regiões simples. Isso deve fornecer o tipo de limite curvo que você procura.

Steven Stadnicki
fonte
Obrigado pela resposta. Decidi usar o arquivo SVG porque as imagens SVG e seus comportamentos são definidos nos arquivos de texto XML, e talvez eu possa quebrar a figura usando as informações internas da figura. Suspeito que essa não seja a melhor solução, mas essa área de conhecimento é nova para mim. Como você acha que se eu substituir o arquivo SVG por outra coisa, ele simplificará a solução? Talvez você conheça outras maneiras de particionar formas não convexas com curvas na lateral?
Louco d0g
Eu acho que o SVG é bom como um formato - como você observa, é um formato de texto bem definido que pode ser analisado diretamente. O SVG não é o que dificulta o problema - são os principais problemas do trabalho com splines e coisas do tipo. Mas acho que nenhum outro formato pode expressar figuras como a do seu exemplo de maneira concisa. É apenas um problema inerentemente desafiador.
Steven Stadnicki
... dito isto, não é intransponível; é até relativamente simples (embora haja muitos pequenos detalhes com que se preocupar). Você só precisa criar (ou encontrar) uma boa biblioteca de Bezier. A única questão que não foi levantada, que pode ser um pouco complicada, é como escolher os pontos em sua figura para a construção do diagrama de Vornoi.
Steven Stadnicki
A colocação dos pontos pode ser feita aleatoriamente, para que caiam na área da figura ou especifique várias linhas e, além disso, escolha um ponto aleatório.
Louco d0g