Fold-and-cut com disk packing

Como funciona

1. Discos nos vértices. Cada vértice do polígono (e cada canto da folha) recebe um disco com raio igual à metade da distância até a aresta não incidente mais próxima.
2. Discos nas arestas. O trecho descoberto de cada aresta é subdividido ao meio enquanto o disco de diâmetro dele “apertar” outro disco; depois cada trecho vira um disco. Toda aresta fica coberta por raios de discos tangentes.
3. Preenchimento. Repetidamente, o maior disco que cabe num gap com cinco ou mais lados é inserido (é o disco centrado num vértice do diagrama de Voronoi). Termina quando só restam gaps de três ou quatro lados.
4. Moléculas. Ligando os centros de discos tangentes, a folha vira triângulos e quadriláteros cujos lados medem exatamente a soma dos raios. Triângulos recebem a molécula rabbit ear (bissetrizes até o incentro, perpendiculares a partir dos pontos de tangência). Quadriláteros recebem a molécula gusset de Robert Lang.
5. Montanha e vale. Bissetrizes são montanha dentro do polígono e vale fora; os demais vincos recebem o oposto. Depois, uma árvore geradora dos vértices e a árvore dual das moléculas escolhem exatamente um vinco por vértice para inverter, o que garante o teorema de Maekawa em todo vértice. A página confere Maekawa e Kawasaki em cada vértice interno antes de exibir.

Na prática: dobre todas as montanhas e vales de modo que o polígono fique inteiro num “livro de abas” acima do plano da folha e o resto fique abaixo; a borda do polígono é a única coisa que fica no plano. Corte um fio de cabelo abaixo desse plano para a figura sair inteira. Padrões com muitas dobras pequenas são difíceis de dobrar à mão; polígonos com poucos vértices e sem cantos muito agudos ficam mais amigáveis.

Referências: Bern, Demaine, Eppstein e Hayes, A Disk-Packing Algorithm for an Origami Magic Trick (OSME 2001); página do Erik Demaine sobre fold-and-cut. Código em src/lib/foldcut/ do repositório deste site.

Fontes consultadas

Registro do que o Claude efetivamente leu durante a sessão, para quem quiser auditar a implementação.

• Lido na íntegra (única fonte externa usada): Bern, Demaine, Eppstein e Hayes, A Disk-Packing Algorithm for an Origami Magic Trick (PDF, OSME 2001; página do paper). Dali saíram as regras de raio dos discos, a subdivisão de arestas “crowded”, o preenchimento por vértices de Voronoi, as moléculas rabbit ear e gusset e o esquema de montanha/vale com as árvores TC e TM (§2 a §4). O fattening (§5) e os atalhos práticos (§6) ficaram de fora.
• Apareceram na busca, mas não foram abertos: JOrigami (implementação em Java do mesmo algoritmo), Recent Results in Computational Origami (Demaine e Demaine), Quadrilateral Meshing by Circle Packing (Bern e Eppstein), e as cópias do paper no Semantic Scholar, Academia.edu e ResearchGate. Uma tentativa de abrir o paper no arXiv com um identificador chutado deu 404.
• Da memória de treinamento, sem consulta: a molécula universal e o gusset de Robert Lang (TreeMaker, 1996), os teoremas de Maekawa e Kawasaki, o problema de Apollonius e o livro Geometric Folding Algorithms (Demaine e O’Rourke). A fórmula do raio reduzido no inset, r_i(h) = r_i − h·cot(θ_i/2), e a equação da diagonal ativa foram derivadas durante a sessão e conferidas por testes numéricos.
• Nenhuma implementação foi consultada durante a escrita do código. Candidatos via Delaunay, face walking do grafo de contato, ponte entre as componentes do quadrado e do polígono e as três correções de casos degenerados encontradas no stress test são decisões próprias desta implementação.
• Consultado depois, para comparação: o código do JOrigami (Paulo Silveira, Rafael Cosentino, José Coelho e Deise Aoki, IME-USP, 2007), obtido no snapshot do CVS no SourceForge e no release 1.0beta. É a implementação Java do mesmo paper; a comparação de estratégias está na seção seguinte.

Comparação com o JOrigami (2007)

O JOrigami é uma implementação em Java do mesmo algoritmo, feita no IME-USP em 2007 por Paulo Silveira, Rafael Cosentino, José Coelho e Deise Aoki (o CVS tem 207 revisões entre janeiro e maio de 2007, 196 delas do Paulo). David Eppstein, coautor do paper, comentou o projeto no blog dele na época. O polígono de exemplo desta página, o “fatfish”, é o mesmo do site do JOrigami, com as coordenadas exatas de examples/fatfish.txt em papel 600×600, reduzidas à metade. Abaixo, o padrão gerado por cada implementação para esse polígono.

Onde as duas implementações fazem a mesma coisa

• Discos de vértice com raio igual à metade da distância à aresta não incidente mais próxima (Packer.coverVertexes).
• Discos de diâmetro nas arestas, divididas ao meio enquanto o disco intersecta outro (Packer.coverEdges).
• Molécula do triângulo idêntica: incentro, bissetrizes montanha, tangentes vale.
• Molécula gusset com os mesmos oito vincos extras (quatro arestas do gusset e quatro segmentos até o pé da diagonal), incluindo o par que precisa ser invertido junto (extras 4 e 5 no JOrigami, partner aqui).
• O matching de montanha e vale: busca em largura dos vértices a partir de um vértice na borda do papel pulando os demais vértices de borda (TreeFaces.cut), meia-aresta do filho invertida; busca em largura das moléculas a partir de uma face vizinha da face externa, tangente do filho invertida e uma tangente extra na raiz (Assigner). É a mesma estrutura, quase linha a linha.

Onde divergem

O que o JOrigami fez melhor

• Triplas só de discos não consecutivos. Garante que cada disco inserido reduz o número de lados do gap, que é o argumento de terminação do paper. Esta página permite triplas consecutivas e depende de a área encolher.
• Heurísticas medidas. Statistics e ComplexityProof existem para comparar a qualidade dos padrões. Na estrela do site, a escolha da heurística varia o número de segmentos de 1184 (biggest neighbor) para 564 (middle disk) e 474 (packing inicial manual).
• Polígonos com buracos e vários componentes, que o paper prevê e esta página não implementa.

O que parece problema no JOrigami

Dito com o cuidado de quem leu o código, mas não o executou.

• A folga de 2 unidades aceita discos sobrepostos em até 2 unidades e chama de tangentes discos a 2 unidades de distância. Foi esse tipo de folga que, nesta implementação, quebrava Kawasaki nos gussets quase degenerados com tolerância de apenas 1e-7.
• Sem a inversão dentro/fora e com a borda do polígono dobrada, todos os lados de todas as moléculas caem no mesmo plano no estado dobrado. O corte nesse plano separa todas as moléculas, e não só o polígono do resto. A seção 4 do paper existe para isso.

O repositório também guarda um módulo de straight skeleton com triangulação cinética (MovingTriangulation, polígonos do Aichholzer), que parece uma primeira tentativa pelo outro método do Demaine, e em DiskPrimitives uma implementação comentada da transformação de Kim, Kim e Sugihara para o diagrama de Voronoi de círculos. O Voronoi aditivo de verdade foi tentado antes de cair no Apollonius por força bruta, o mesmo atalho desta página.

Bastidores

Esta página foi implementada pelo Claude (Fable 5.1) numa única sessão de Claude Code, a partir de um pedido de um parágrafo e do polígono de exemplo desenhado numa folha. O algoritmo é TypeScript puro (única dependência: delaunator, para gerar candidatos de triplas de discos), com testes em vitest que checam packing válido, Maekawa e Kawasaki em centenas de polígonos aleatórios. A sessão levou cerca de 65 minutos e consumiu aproximadamente 260 mil tokens, incluindo a leitura do paper original para acertar a molécula gusset e a atribuição montanha/vale.