<?
$DPI
=30;
$W=33.11*$DPI;
$H=46.81*$DPI;
$FILE="Saguaro_Sunset.jpg";
//$FILE="blood_red_sunset_panorama_by_mad_guns22-d35br2b.jpg";
//$FILE="Ferrera_Beach_2009_Panoramic_Photos_36.jpg";
$OUT="out-%d.jpg";
$MAP="map.jpg";
$NO=20;


function 
resizeVect($v$newlen) {
    
$div=sqrt($v["x"]*$v["x"] + $v["y"]*$v["y"])/$newlen;
    
$v["x"]/=$div;
    
$v["y"]/=$div;
    return 
$v;
}

function 
dotproduct($p1$p2) {
    return 
$p1["x"]*$p2["x"]+$p1["y"]*$p2["y"];
}

//Calculate the intersecting point of two lines. Source:
// http://www.cracktheinterview.net/adobe/322-line-segment-intersection.html
//(because my math is too rusty to trust the solution I worked out myself)
function getIntersectPoint($base1$dir1$base2$dir2) {
//    $dir1=resizeVect($dir1, 1);
//    $dir2=resizeVect($dir2, 1);
    
$p["x"]=-$dir1["y"]; $p["y"]=$dir1["x"];
    
$aminc["x"]=$base1["x"]-$base2["x"];
    
$aminc["y"]=$base1["y"]-$base2["y"];
    if (
abs(dotproduct($dir2$p))<.00001) return FALSE//probably parallel
    
$h=dotproduct($aminc$p)/dotproduct($dir2$p);
    
$res["h"]=$h;
    
$res["x"]=$base2["x"]+$dir2["x"]*$h;
    
$res["y"]=$base2["y"]+$dir2["y"]*$h;
    return 
$res;
}


function 
linesIntersect($a1$a2$b1$b2) {
    
$adir["x"]=$a2["x"]-$a1["x"];
    
$adir["y"]=$a2["y"]-$a1["y"];
    
$bdir["x"]=$b2["x"]-$b1["x"];
    
$bdir["y"]=$b2["y"]-$b1["y"];
    
$r=getIntersectPoint($a1$adir$b1$bdir);
    if (
$r==FALSE || $r["h"]<|| $r["h"]>1) return FALSE;
    
$r=getIntersectPoint($b1$bdir$a1$adir);
    if (
$r==FALSE || $r["h"]<|| $r["h"]>1) return FALSE;
    
$res["x"]=$r["x"]; $res["y"]=$r["y"];
    return 
$r;
}

function 
calcPolyArea($p) {
    
//Stolen from http://www.mathopenref.com/coordpolygonarea2.html
    
$area=0;
    
$j=count($p)-1;
    for (
$i=0$i<count($p); $i++) {
        
$area+=($p[$j]["x"]+$p[$i]["x"])*($p[$j]["y"]-$p[$i]["y"]);
        
$j=$i;
    }
    return 
abs($area);
}


function 
drawPoly($im$p$c) {
    
$pn=array();
    for (
$x=0$x<count($p); $x++) {
        
$pn[]=$p[$x]["x"];
        
$pn[]=$p[$x]["y"];
    }
    
imagepolygon($im$pncount($p), $c);
}

function 
areaOfIntersection($p1$p2) {
/*
    $im=imagecreate(5640, 5480);
    imagecolorallocate($im ,255, 255, 255);
    drawPoly($im, $p1, imagecolorallocate($im, 255, 0, 0));
    drawPoly($im, $p2, imagecolorallocate($im, 0, 0, 255));
    echo "AreaOfIntersection START\n";
*/
    
$areaTotal=calcPolyArea($p1)+calcPolyArea($p2);
    
$diff=array();
    
$p=0$which=0;
    
$last=$p1[count($p1)-1];
    
$foundIntersect=false;
    
$ovf=150//safety
    //Hell of a routine: walk the line until the two polygons intersect, then jump to the other
    //polygon and continue the walk. The walk we did is stored in $dist. This is either the outer
    //line of the combination (the union) or the intersection.
    
do {
        
$next=$which?$p2[$p]:$p1[$p];
        
$cnt=$which?count($p2):count($p1);
        
$l=$cnt-1;
        
$found=false;
        
$closest=-1;
        for (
$n=0$n<$cnt$n++) {
            if (
$which) {
                
$r=linesIntersect($last$next$p1[$l], $p1[$n]);
            } else {
                
$r=linesIntersect($last$next$p2[$l], $p2[$n]);
            }
            if (
$r!=FALSE && !(abs($r["x"]-$last["x"])<.1 && abs($r["y"]-$last["y"])<.1)) {
                
$dist=sqrt(pow($last["x"]-$r["x"], 2)+pow($last["y"]-$r["y"], 2));
                if (
$closest==-|| $dist<$closest) {
                    
$closest=$dist;
                    
$foundPnt=$r;
                    
$foundIdx=$n;
                    
$found=true;
                }
            }
            
$l=$n;
        }
        if (
$found) {
            
$diff[]=$foundPnt;
            
$last=$foundPnt;
            
$which=$which?0:1;
            
$p=$foundIdx;
            
$foundIntersect=true;
//            echo "Skip to $which. Line seg: ".$last["x"].",".$last["y"]."-".$foundPnt["x"].",".$foundPnt["y"]."\n";
        
} else {
            
$diff[]=$next;
            
$last=$next;
            
$p++;
            if (!
$which && $p==count($p1)) $p=0;
            if (
$which && $p==count($p2)) $p=0;
//            echo "Stay on $which. Line seg: ".$last["x"].",".$last["y"]."-".$next["x"].",".$next["y"]."\n";
        
}
        
$ovf--;
        if (
$ovf==0) {
            echo 
"Huh? Bug in area calculation code; ovf reached.\n";
//            drawPoly($im, $diff, imagecolorallocate($im, 0, 255, 0));
//            imagepng($im, "dbg.png");
//            imagedestroy($im);
//            exit(0);
            
return 999999999;
        }
    } while (
$p!=|| $which!=0);

    
//Return 0 if areas don't overlap. (Or are within eachother; we don't detect that here...)
    
if (!$foundIntersect) return 0;

//    imagedestroy($im);


    
$areaWalk=calcPolyArea($diff);
    if (
$areaWalk>$areaTotal-$areaWalk$areaWalk=$areaTotal-$areaWalk;
    return 
$areaWalk;

}

/*
$a[0]=array("x"=>0, "y"=>0);
$a[1]=array("x"=>200,  "y"=>0);
$a[2]=array("x"=>0, "y"=>200);

$b[0]=array("x"=>20, "y"=>20);
$b[1]=array("x"=>300, "y"=>20);
$b[2]=array("x"=>20, "y"=>300);

echo areaOfIntersection($a, $b); //should return 25600
exit(0);
*/


function translatePoly($p$t) {
    for (
$i=0$i<count($p); $i++) {
        
$r[]=array("x"=>$p[$i]["x"]+$t["x"], "y"=>$p[$i]["y"]+$t["y"]);
    }
    return 
$r;
}

function 
rotatePoly($p$a) {
    
$rad=($a*2*M_PI)/360;
    for (
$i=0$i<count($p); $i++) {
        
$nx=$p[$i]["x"]*cos($rad)-$p[$i]["y"]*sin($rad);
        
$ny=$p[$i]["x"]*sin($rad)+$p[$i]["y"]*cos($rad);
        
$r[]=array("x"=>$nx"y"=>$ny);
    }
    return 
$r;
}

//h, w: height and width of both squares
//pnx, pny: center of square n
//ax: angle of square x
function calcSquaresOverlappingArea($w$h$a1$a2$p1x$p1y$p2x$p2y) {
    
//Quick check: if middles are more than the diagonal of a square away, they don't overlap.
    
$diag=sqrt($h*$h+$w*$w);
    
$dist=sqrt(pow($p1x-$p2x2)+pow($p1y-$p2y2));
    if (
$dist>$diag) return 0;

    
$sq[0]=array("x"=>-$w/2"y"=>-$h/2);
    
$sq[1]=array("x"=>$w/2"y"=>-$h/2);
    
$sq[2]=array("x"=>$w/2"y"=>$h/2);
    
$sq[3]=array("x"=>-$w/2"y"=>$h/2);
    
$sq1=translatePoly(rotatePoly($sq$a1), array("x"=>$p1x"y"=>$p1y));
    
$sq2=translatePoly(rotatePoly($sq$a2), array("x"=>$p2x"y"=>$p2y));
    return 
areaOfIntersection($sq1$sq2);
}


function 
generatePlacementMap($iw$ih$sw$sh$maxno) {
    
$retriesMax=10000;
    
$retries=$retriesMax;
    
$no=0;
    while (
$no<$maxno) {
        
$mindist=sqrt($sw*$sw+$sh*$sh)*($retries/$retriesMax)*0.75;
        
$xpos[$no]=rand(0$iw);
        
$ypos[$no]=rand(0$ih);
        
$angle[$no]=rand(0360);
        
$tooclose=false;
        for (
$c=0$c<$no$c++) {
            
$ox=$xpos[$no]-$xpos[$c];
            
$oy=$ypos[$no]-$ypos[$c];
            if (
sqrt($ox*$ox+$oy*$oy)<$mindist$tooclose=true;
        }
        if (
$tooclose) {
            
$retries--;
            if (
$retries==0) break; //shouldn't happen
        
} else {
            
$no++;
        }
    }
    return array(
"xpos"=>$xpos"ypos"=>$ypos"angle"=>$angle);
}


function 
calculateTryArea($try$w$h) {
    
$area=0;
    for (
$i=0$i<count($try["xpos"]); $i++) {
        for (
$j=0$j<$i$j++) {
            
$area+=calcSquaresOverlappingArea($w$h$try["angle"][$i], $try["angle"][$j],
                
$try["xpos"][$i], $try["ypos"][$i],
                
$try["xpos"][$j], $try["ypos"][$j]);
        }
    }
    return 
$area;
}

function 
jiggleTry($bestTry$notries$w$h$iw$ih) {
    
//Try around a bit to get an even betterder fit.
    
$try=$bestTry;
    
$bestOverlap=-1;
    
$margin=(($w>$h)?$h:$w)/2;
    for (
$jiggle=0$jiggle<$notries$jiggle++) {
        for (
$n=0$n<count($try["xpos"]); $n++) {
            
$try["xpos"][$n]+=rand(-1010);
            
$try["ypos"][$n]+=rand(-1010);
            
$try["angle"][$n]+=rand(-1010);
            if (
$try["xpos"][$n]<$margin$try["xpos"][$n]=$margin;
            if (
$try["xpos"][$n]>$iw-$margin$try["xpos"][$n]=$iw-$margin;
            if (
$try["ypos"][$n]<$margin$try["ypos"][$n]=$margin;
            if (
$try["ypos"][$n]>$ih-$margin$try["ypos"][$n]=$ih-$margin;
            
$area=calculateTryArea($try$w$h);
            if (
$bestOverlap==-|| $area<$bestOverlap) {
                echo 
"Jiggled to $area.\n";
                
$bestTry=$try;
                
$bestOverlap=$area;
            } else {
                
$try["angle"][$n]=$bestTry["angle"][$n];
                
$try["xpos"][$n]=$bestTry["xpos"][$n];
                
$try["ypos"][$n]=$bestTry["ypos"][$n];
            }
        }
    }
    return 
$bestTry;
}

$orig=imagecreatefromjpeg($FILE);
$origw=imagesx($orig); $origh=imagesy($orig);
$rotsz=sqrt(($H*$H)+($W*$W));

echo 
"Calculating placement...\n";
$bestOverlap=-1;
for (
$tries=0$tries<500$tries++) {
    
$try=generatePlacementMap($origw$origh$W$H$NO);
//    $try=jiggleTry($try, 20, $W, $H);
    
echo "$try: placement map generated.\n";

    
$area=calculateTryArea($try$W$H);
    if (
$bestOverlap==-|| $bestOverlap>$area) {
        echo 
"Best area: $area\n";
        
$bestOverlap=$area;
        
$bestTry=$try;
        
$bestTry=jiggleTry($bestTry20$W$H$origw$origh);
    }
}

$bestTry=jiggleTry($bestTry500$W$H$origw$origh);



$angle=$bestTry["angle"]; $ypos=$bestTry["ypos"]; $xpos=$bestTry["xpos"];

for (
$no=0$no<$NO$no++) {
    
//Cut out image
    
echo "Cutting $no/$NO...";
    
$rotim=imagecreatetruecolor($rotsz$rotsz);
    
imagecopy($rotim$orig00$xpos[$no]-($rotsz/2), $ypos[$no]-($rotsz/2), $rotsz$rotsz);
    echo 
"cut...";
    
$bg=imagecolorallocatealpha($rotim2552552550);
    
$rotated=imagerotate($rotim$angle[$no], -1);
    echo 
"rotate...";
    
imagedestroy($rotim);
    
$a4=imagecreatetruecolor($W$H);
    
imagecopy($a4$rotated00, (imagesx($rotated)-$W)/2, (imagesy($rotated)-$H)/2$W$H);
    echo 
"copy...";
    
imagejpeg($a4sprintf($OUT$no), 90);
    echo 
"write.\n";
    
imagedestroy($a4);

}

//imagedestroy($orig);


$map=$orig//imagecreatetruecolor($origw, $origh);
//imagealphablending($map, true);

//Generate template of A4 that gets put on top of the map for each A4 cropped.
$a4tpl=imagecreatetruecolor($W$H);
imagealphablending($a4tplfalse);
$a4bg=imagecolorallocatealpha($map2550255127);
$a4col1=imagecolorallocatealpha($map002550);
$a4col2=imagecolorallocatealpha($map2552552550);
imagefilledrectangle($a4tpl,00$W$H$a4col1);
imagefilledrectangle($a4tpl,33$W-3$H-3$a4col2);
imagefilledrectangle($a4tpl,66$W-6$H-6$a4bg);
imagealphablending($a4tpltrue);

for (
$no=0$no<$NO$no++) {
    echo 
"Mapping $no/$NO...\n";
    
//Mark on map
    
$rottpl=imagerotate($a4tpl, -$angle[$no], 0xFFFFFFFF);
    
imagecopy($map$rottpl$xpos[$no]-imagesx($rottpl)/2$ypos[$no]-imagesy($rottpl)/200imagesx($rottpl), imagesy($rottpl));
}

imagejpeg($map$MAP);

?>