//This program automatically generates cut paths for jigsaw puzzles.
//Koji Ohashi 2024.12.10
//Morioka Japan
import megamu.mesh.*;
import processing.pdf.*;
// design constant
final float artboardWidth_mm = 210;
final float artboardHeight_mm=148;
final float finishWidth_mm=210;
final float finishHeight_mm=148;
final float FRAME_X_mm=15;
final float FRAME_Y_mm=15;
final float CellSize_mm=20;
final float minEdgeLength_mm =7;
final boolean draw_nucleous=true; // true or false
final float NucleusDiam_mm=8;
// end design constant
final float pixConv=72/25.4;
final float artboardWidth=artboardWidth_mm*pixConv;//(mm)
final float artboardHeight=artboardHeight_mm*pixConv;//(mm)
final float finishWidth=finishWidth_mm*pixConv;//(mm)
final float finishHeight=finishHeight_mm*pixConv;//(mm)
final float FRAME_X=FRAME_X_mm*pixConv ;
final float FRAME_Y=FRAME_Y_mm*pixConv ;
final float WIDTH = finishWidth-FRAME_X*2;
final float HEIGHT = finishHeight-FRAME_Y*2;
int voronoiCells = 150;
final float diskRadius=CellSize_mm*pixConv;
final float NucleusDiam=NucleusDiam_mm*pixConv;
final float minEdgeLength =minEdgeLength_mm*pixConv;
final float tightness=0.7;
final float strokeWidth = 0.313;//( 0.25pt ==> 0.313pxcel)
float[][] nucleus = new float[voronoiCells][2];
MPolygon[] Poly, mPoly;
float cross_x, cross_y;
int[] corner= new int[4];
float[][] cpos = {{0, 0},{WIDTH, 0},{0, HEIGHT},{WIDTH, HEIGHT}};
float[][] edgeInfo;
int all_edge;
float xs,xl,ys,yl;
void settings(){
int docWidth=(int)artboardWidth;
int docHeight=(int)artboardHeight;
println("docWidth: ",docWidth,"docHeight: ",docHeight);
size(docWidth,docHeight);
//loadNucleus(); //set nucleus( x, y)
diskNucleusPutRemove(diskRadius);
saveNucleus();
}
void setup(){
beginRecord(PDF, "my_PzlPiece_.pdf");
background(255,255,255);
noFill();
strokeWeight(strokeWidth);
//stroke(0, 0, 0);//Black
stroke(255, 0, 0);//Red
noLoop(); // Run once and stop
}
void draw(){
translate((artboardWidth-finishWidth)/2,(artboardHeight-finishHeight)/2);
translate(FRAME_X,FRAME_Y);
Voronoi volonoiPiece = new Voronoi(nucleus);
Poly = volonoiPiece.getRegions();
mPoly=new MPolygon[Poly.length];
findCornerCell(); // Cell number of corner(4) --> corner[i]
trimOutside();
addCorners();
edgeInfoArray();// before edge deletion
deleteShortEdge();// edge deletion
edgeInfoArray();// after edge deletion
DrawFinalSetup1();
DrawFinalSetup2();
DrawFinal(tightness);
if(draw_nucleous){
drawNucleus(NucleusDiam);
}
//translate(-FRAME_X,-FRAME_Y);
//translate(-(artboardWidth-finishWidth)/2,-(artboardHeight-finishHeight)/2);
//stroke(255, 0, 0);
//antiBend();
//stroke(0, 0, 255);
//finish();
endRecord();
}
// ---------------function----------------------
void antiBend(){
int lineCount=20;
float pitch=finishHeight/(lineCount+1);
float x0=0;
float x1=finishWidth-FRAME_X;
for(int i=0;i<lineCount;i++){
line(x0+2.5*pixConv,pitch*(i+1),x0+7.5*pixConv,pitch*(i+1));
}
for(int i=0;i<lineCount;i++){
line(x1+2.5*pixConv,pitch*(i+1),x1+7.5*pixConv,pitch*(i+1));
}
}
void drawFrame(){
line(0,0,WIDTH,0);
line(WIDTH,0,WIDTH,HEIGHT);
line(WIDTH,HEIGHT,0,HEIGHT);
line(0,HEIGHT,0,0);
}
void finish(){
line(0,0,finishWidth,0);
line(finishWidth,0,finishWidth,finishHeight);
line(finishWidth,finishHeight,0,finishHeight);
line(0,finishHeight,0,0);
}
void diskNucleusPutRemove(float r){
boolean[] remove = new boolean [voronoiCells];
float [][] rnd_point =new float [voronoiCells][2];
float [][] scattered =new float [voronoiCells][2];
for(int i=0;i<voronoiCells;i++){
rnd_point[i][0] = random(r/2, WIDTH-r/2);
rnd_point[i][1] = random(r/2, HEIGHT-r/2);
remove[i]=false;
}
for(int i=0;i<voronoiCells;i++){
for(int j=0;j<voronoiCells;j++){
if((i!=j)&&(remove[i]!=true)&&(remove[i]!=true)){
float dist=sqrt(sq(rnd_point[j][0]-rnd_point[i][0])+sq(rnd_point[j][1]-rnd_point[i][1]));
if(dist<r){
remove[j]=true;
}
}
}
}
int tempCells=0;
for(int i=0;i<voronoiCells;i++){
if(remove[i]!=true){
scattered[tempCells][0]=rnd_point[i][0];scattered[tempCells][1]=rnd_point[i][1];
tempCells++;
}
}
voronoiCells=tempCells;
nucleus = new float[voronoiCells][2];
for(int i=0;i<voronoiCells;i++){
nucleus[i][0]=scattered[i][0];nucleus[i][1]=scattered[i][1];
}
println("voronoiCells: ",voronoiCells);
}
void DrawFinalSetup1(){
int edge_index=0;
int neighbor;
for(int cell=0;cell<voronoiCells;cell++){
int n=mPoly[cell].count();
for(int i=0;i<n;i++){
if((edgeInfo[edge_index][6]!=-1)&&(edgeInfo[edge_index][9]==-1)){
neighbor=(int)edgeInfo[edge_index][8];
if(random(0,1)>=0.5){
edgeInfo[edge_index][9]=1;
edgeInfo[neighbor][9]=0;
} else{
edgeInfo[edge_index][9]=0;
edgeInfo[neighbor][9]=1;
}
}
edge_index++;
}
}
}
void DrawFinalSetup2(){
for(int edge_index=0;edge_index<all_edge;edge_index++){
if(edgeInfo[edge_index][6]==-1){
edgeInfo[edge_index][9]=0;
}
//print(edge_index,", ",edgeInfo[edge_index][0],", ",edgeInfo[edge_index][1],", ",edgeInfo[edge_index][2],", ",edgeInfo[edge_index][3],", ");
//println(edgeInfo[edge_index][4],", ",edgeInfo[edge_index][5],", ",edgeInfo[edge_index][6],", ",edgeInfo[edge_index][7],", ",edgeInfo[edge_index][8],", ",edgeInfo[edge_index][9]);
}
}
void DrawFinal(float t){
curveTightness(t);
int edge_index=0;
for(int cell=0;cell<voronoiCells;cell++){
float[][] AXY = mPoly[cell].getCoords();
int n=mPoly[cell].count();
for(int i=0;i<n;i++){
if(edgeInfo[edge_index][9]==1){
curve(AXY[(i-1+n)%n][0],AXY[(i-1+n)%n][1],AXY[i][0],AXY[i][1],AXY[(i+1)%n][0],AXY[(i+1)%n][1],AXY[(i+2)%n][0],AXY[(i+2)%n][1]);
}
edge_index++;
//ellipse(AXY[i][0],AXY[i][1], 10, 10);//draw edge points
}
}
drawFrame();
}
void edgeInfoArray(){
all_edge=0;
for(int i=0;i<voronoiCells;i++){
int count=mPoly[i].count();
all_edge=all_edge + count;
}
edgeInfo=new float [all_edge][12];
//println("all_edge: ",all_edge);
int edge_index=0;
for(int i=0;i<voronoiCells;i++){
float[][] AXY = mPoly[i].getCoords();
int count=mPoly[i].count();
for(int j=0;j<count;j++){
edgeInfo[edge_index][0]=AXY[j][0]; edgeInfo[edge_index][1]=AXY[j][1];
edgeInfo[edge_index][2]=AXY[(j+1)%count][0]; edgeInfo[edge_index][3]=AXY[(j+1)%count][1];
edgeInfo[edge_index][4]=i;edgeInfo[edge_index][5]=j;
edgeInfo[edge_index][6]=-1;edgeInfo[edge_index][7]=-1;//
edgeInfo[edge_index][8]=-1;edgeInfo[edge_index][9]=-1;
edgeInfo[edge_index][10]= sqrt(sq(AXY[(j+1)%count][0]-AXY[j][0])+sq(AXY[(j+1)%count][1]-AXY[j][1]));
edgeInfo[edge_index][11]=-1;
if(edgeInfo[edge_index][10]<minEdgeLength){
int pos=judgePos(AXY[j][0], AXY[j][1])+judgePos(AXY[(j+1)%count][0], AXY[(j+1)%count][1]);
if(pos==4){edgeInfo[edge_index][11]=2;}
if(pos==3){edgeInfo[edge_index][11]=1;}
if(pos==2){edgeInfo[edge_index][11]=0;}
}
edge_index++;
}
}
float x0,y0,x1,y1,x2,y2,x3,y3;
for(int i=0;i<all_edge;i++){
x0=edgeInfo[i][0]; y0=edgeInfo[i][1];
x1=edgeInfo[i][2]; y1=edgeInfo[i][3];
for(int j=0;j<all_edge;j++){
if(i!=j){
x2=edgeInfo[j][0]; y2=edgeInfo[j][1];
x3=edgeInfo[j][2]; y3=edgeInfo[j][3];
if(((((abs(x0-x2)<1)&&(abs(y0-y2)<1))&&(abs(x1-x3)<1)&&(abs(y1-y3)<1))||(((abs(x0-x3)<1)&&(abs(y0-y3)<1))&&(abs(x1-x2)<1)&&(abs(y1-y2)<1)))){
edgeInfo[i][6]=edgeInfo[j][4];edgeInfo[i][7]=edgeInfo[j][5];
edgeInfo[i][8]=j;
}
}
}
//print(i,", ",edgeInfo[i][0],", ",edgeInfo[i][1],", ",edgeInfo[i][2],", ",edgeInfo[i][3],", ");
//print(edgeInfo[i][4],", ",edgeInfo[i][5],", ",edgeInfo[i][6],", ",edgeInfo[i][7]);
//println(", ",edgeInfo[i][8],", ",edgeInfo[i][9],", ",edgeInfo[i][10],", ",edgeInfo[i][11]);
}
}
/*
0:x0, 1:y0, 2:x1, 3:y1, 4:this cell, 5:edge Num, 6:neibor cell, 7:edge Num, 8:row, 9:draw/not draw, 10:edge length, 11:edge position
*/
void deleteShortEdge(){
for(int i=0;i<all_edge;i++){
if(edgeInfo[i][11]>=0){
int sameEdge = (int)edgeInfo[i][8];
if(sameEdge>=0){
edgeInfo[sameEdge][11]=-1;
}
}
if(edgeInfo[i][11]==0){
changeCellPoint(edgeInfo[i][0],edgeInfo[i][1],edgeInfo[i][2],edgeInfo[i][3]);
}
if(edgeInfo[i][11]==1){
if(judgePos(edgeInfo[i][0], edgeInfo[i][1])!=2){
changeCellPoint(edgeInfo[i][0],edgeInfo[i][1],edgeInfo[i][2],edgeInfo[i][3]);
} else{
changeCellPoint(edgeInfo[i][2],edgeInfo[i][3],edgeInfo[i][0],edgeInfo[i][1]);
}
}
if(edgeInfo[i][11]==2){
changeCellPoint(edgeInfo[i][0],edgeInfo[i][1],edgeInfo[i][2],edgeInfo[i][3]);
}
}
}
void changeCellPoint(float delPx,float delPy,float repPx,float repPy){
for(int i=0;i<voronoiCells;i++){
float[][] AXY = mPoly[i].getCoords();
int delP=-1;
int repP=-1;
int count=-1;
for(int j=0;j<mPoly[i].count();j++){
if((AXY[j][0]==delPx) && (AXY[j][1]==delPy)){
delP=j;
}
if((AXY[j][0]==repPx) && (AXY[j][1]==repPy)){
repP=j;
}
}
if(delP>=0 && repP==-1){
count=mPoly[i].count();
AXY[delP][0]=repPx; AXY[delP][1]=repPy;
}
if(delP>=0 && repP>=0){
count=mPoly[i].count()-1;
for(int j=delP;j<count;j++){
AXY[j][0]=AXY[j+1][0]; AXY[j][1]=AXY[j+1][1];
}
}
if (count>0){
mPoly[i]=new MPolygon(count);
for(int j=0;j<count;j++){
mPoly[i].add(AXY[j][0],AXY[j][1]);
}
}
}
}
void addCorners(){
for(int i=0;i<4;i++){
int ins_pos=-1;
int cn=corner[i];
float[][] AXY = mPoly[cn].getCoords();
int points=mPoly[cn].count();
// find corner point
for(int j=0;j<points;j++){
if(judgePos(AXY[j][0],AXY[j][1])==2 && judgePos(AXY[(j+1)%points][0],AXY[(j+1)%points][1])==2){
ins_pos=j;
}
}
int newCount=points+1;
mPoly[cn]=new MPolygon(newCount);
for(int j=0;j<newCount-1;j++){
if(j==ins_pos){
mPoly[cn].add(AXY[j][0],AXY[j][1]);
mPoly[cn].add(cpos[i][0],cpos[i][1]);
}
else{
mPoly[cn].add(AXY[j][0],AXY[j][1]);
}
}
}
}
void trimOutside(){
for(int i=0;i<Poly.length;i++){
float[][] AXY = Poly[i].getCoords();
int count=Poly[i].count();
float[][] temp_AXY =new float[count+1][2];//+1 means : cross 2 points when single point outside
int mp_count=0;
for(int j=0;j<count; j++){
//if(i==5){println("5: x=",AXY[j][0],", y=",AXY[j][1]);}
if(judgePos(AXY[j][0],AXY[j][1])>0){
temp_AXY[mp_count][0]=AXY[j][0];temp_AXY[mp_count][1]=AXY[j][1];
mp_count=mp_count+1;
}
//if(i==5){println("5: mp_count= ",mp_count);}
if(checkCross( AXY[j][0],AXY[j][1],AXY[(j+1)%count][0],AXY[(j+1)%count][1] )){
temp_AXY[mp_count][0]=cross_x;temp_AXY[mp_count][1]=cross_y;
mp_count=mp_count+1;
}
}
mPoly[i]=new MPolygon(mp_count);
for(int j=0;j<mp_count;j++){
mPoly[i].add(temp_AXY[j][0],temp_AXY[j][1]);
}
}
}
void drawNucleus(float r){
//fill(255,0,0);
//stroke(255,0,0);
for(int i=0;i<voronoiCells;i++){
ellipse(nucleus[i][0], nucleus[i][1], r, r);
}
}
void findCornerCell(){
for(int i=0;i<4;i++){
corner[i]=closestCell(cpos[i][0], cpos[i][1]);
}
}
int closestCell(float x, float y){
float closestDist=10000000;
int closestPoint=-1;
for(int i=0;i<voronoiCells; i++){
float dist=sqrt((nucleus[i][0]-x)*(nucleus[i][0]-x)+(nucleus[i][1]-y)*(nucleus[i][1]-y));
if(dist<closestDist){
closestDist=dist;
closestPoint=i;
}
}
return closestPoint;
}
boolean checkCross(float x0,float y0,float x1,float y1){
float xs,xl,ys,yl,cr;
if((judgePos(x0, y0)>0) == (judgePos(x1, y1)>0)){
return false;}
if((judgePos(x0, y0)==2) || (judgePos(x1, y1)==2)){
return false;}
if (x0>x1){xs=x1;xl=x0;
} else{xs=x0;xl=x1;}
if (y0>y1){ys=y1;yl=y0;
} else{ys=y0;yl=y1;}
float a=(y1-y0)/(x1-x0);
cr=(-y0)/a+x0;
if(cr>=xs && cr<= xl && cr>=0 && cr<=WIDTH){
cross_x=cr; cross_y=0.0; return true;
}
cr=(HEIGHT-y0)/a+x0;
if(cr>=xs && cr<= xl && cr>=0 && cr<=WIDTH){
cross_x=cr; cross_y=HEIGHT; return true;
}
cr=(-x0)*a+y0;
if(cr>=ys && cr<= yl && cr>=0 && cr<=HEIGHT){
cross_x=0.0; cross_y=cr; return true;
}
cr=(WIDTH-x0)*a+y0;
if(cr>=ys && cr<= yl && cr>=0 && cr<=HEIGHT){
cross_x=WIDTH; cross_y=cr; return true;
}
//println("cross_error");
return false;
}
int judgePos(float x, float y){
int judge=-1;
if(x>=0 && x<=WIDTH && y>=0 && y<=HEIGHT){
judge=1;
if(x==0 || x==WIDTH || y==0 || y==HEIGHT){
judge=2;
}
}
return judge;
}
void loadNucleus(){
String[] lines;
lines = loadStrings("Nucleus.txt");
for (int row = 0; row < lines.length; row++){
String[] pieces = split(lines[row], '\t');
nucleus[row][0]=float(pieces[0]);
nucleus[row][1]=float(pieces[1]);
}
}
void saveNucleus(){
String[] lines=new String[voronoiCells];
for (int row = 0; row < voronoiCells; row++){
lines[row]=str(nucleus[row][0])+'\t'+str(nucleus[row][1]);
}
saveStrings("Nucleus.txt",lines);
}