Picture positionig algorithm for non overlapping

Using PHP, I have to place photos over a map in a way, where picture don't overlap. From their scren position, I have to draw a line to a point on the map, which the foto represents. I am loking for an algorithm, which describes, how to calculate positions of the photos on the screen.
stropmAsked:
Who is Participating?
 
stropmConnect With a Mentor Author Commented:
So finally, I solved it by moving the pictures around until there i sa free space left. I start placing them above a point, which they are flagging and in case another picture should be placed on their possition, I shift both by half of their size.
0
 
GEM100Connect With a Mentor Commented:
Line drawing:
http://www.php.net/manual/en/function.imageline.php

Image creation:
http://www.php.net/manual/en/function.imagecreatefromjpeg.php

Use imagecopy() to combine images:
http://www.php.net/imagecopy

Here is sample code from web showing image combination:
<?
header ("Content-type: image/png");
$src = array ("http://img164.imageshack.us/img164/5175/toprb3.jpg","http://img123.imageshack.us/img123/9056/leftij4.jpg","http://miniprofile.xfire.com/bg/bg/type/1/blackburnperson.png", "http://img67.imageshack.us/img67/4786/rightnt1.jpg","http://img123.imageshack.us/img123/4891/bottomtp5.jpg");    
$imgBuf = array ();
foreach ($src as $link)
{
   switch(substr ($link,strrpos ($link,".")+1))
   {
       case 'png':
           $iTmp = imagecreatefrompng($link);
           break;
       case 'gif':
           $iTmp = imagecreatefromgif($link);
           break;                
       case 'jpeg':            
       case 'jpg':
           $iTmp = imagecreatefromjpeg($link);
           break;                
   }
   array_push ($imgBuf,$iTmp);
}
$iOut = imagecreatetruecolor ("450","131") ;
imagecopy ($iOut,$imgBuf[0],0,0,0,0,imagesx($imgBuf[0]),imagesy($imgBuf[0]));
imagedestroy ($imgBuf[0]);
imagecopy ($iOut,$imgBuf[1],0,54,0,0,imagesx($imgBuf[1]),imagesy($imgBuf[1]));
imagedestroy ($imgBuf[1]);
imagecopy ($iOut,$imgBuf[2],15,54,0,0,imagesx($imgBuf[2]),imagesy($imgBuf[2]));
imagedestroy ($imgBuf[2]);
imagecopy ($iOut,$imgBuf[3],292,54,0,0,imagesx($imgBuf[3]),imagesy($imgBuf[3]));
imagedestroy ($imgBuf[3]);
imagecopy ($iOut,$imgBuf[4],0,117,0,0,imagesx($imgBuf[4]),imagesy($imgBuf[4]));
imagedestroy ($imgBuf[4]);
imagepng($iOut);
?>

To prevent overlapping, you can use calculations with image height/width:
http://www.php.net/getimagesize
and calculating positions.
0
 
stropmAuthor Commented:
Thanks for the coding hint, but I am looking for an alogorithm, not for the list of image manipulation functions. The issues, which have to be addressed by the algorithm are:

1) Moved pictures cannot be too far from their original position
2) By moving, you cannot create a "spageti" picture
3) Moved pictures cannot overlap any line or position of any other picture
0
Cloud Class® Course: Amazon Web Services - Basic

Are you thinking about creating an Amazon Web Services account for your business? Not sure where to start? In this course you’ll get an overview of the history of AWS and take a tour of their user interface.

 
stropmAuthor Commented:
Thanks for the hint, but I don't think it solves the problem. The document describes, how to use a space in the most efficient way. But I am looking for something else - for sure, the document answers point 3, but points 1 and 2 are not addresed. These to points are key for the solution, because otherwise I would just create a huge picture, where each image would occupy one virtual row ....
0
 
ozoCommented:
How about Simulated Annealing with distance from the original position as part of the  energy function?
what is a "spageti" picture?
0
 
stropmAuthor Commented:
Sorry, but I don't know anything about "Simulated Annealing" ....
Spageti - it comes from Italian. It means something like mess of lines and pictures, where nobody can say, what leads to where ....
0
 
GEM100Commented:
Won't this require just two functions? One to check overlapping, and another one to move image in any direction.  Simulate move one px right, check overlap, if it does overlap, move one px down, check, one px left, check, one pix up, check, them repeat for moving by 2px, in all direction, then 3, etc. Move is of course simulated, not actual move. Once position is found with simulated move, and overlap returns false, do all needed image placements.
0
 
JimBrandleyCommented:
Annealing is the process of removing stress from objects to which stress has been added as the result of prior processing, such as machining. So, simulated annealing would involve simulating stress and developing a an algorithm to reduce that stress. As ozo mentioned, in this case, the simulated stress is proportional to  the deviation of the length of the line connecting the photo to the map point from some "ideal" length.
0
 
JimBrandleyCommented:
Assume a working definition of ""spageti" picture" as:
All the pictures fit in a general area, except one or two which were displaced long distances.

Then, let stress be proportional to the square of the deviation of the line lengths from ideal, and during the annealing process, consider both the stress of any individual photo as well as the total stress of all photos in the map. Then any photo movement that reduces total stress is beneficial, and the converse, any photo movement that increases total stress is a bad move. When calculating stress deltas, you only need to consider those photos involved in that set of moves, and can ignore any that did not move.

The algorithm can terminate when all photos are within the max you set in your definition of spagetti,
or when all attempts to reduce overall stress resulted in a net increase.
0
 
stropmAuthor Commented:
GEM100: definetly not, you could end up with total mess on your screen ...

Jim: Sounds like a good startup. It could probably solve "ideal" distance of a photo from its original position, but it still doesn't address an issue like which direction used for the initial movement (let's consider recursion is not the right method in this case). Let me think lettle bit about your idea, it's 9PM here, so probably it's not right time for me to develop tough ideas .... ;-)
0
 
JimBrandleyCommented:
Stropm - I think initial positioning might be more important in reducing the cost of manipulation later. For example, consider clusters. Points of interest do not tend to be randomly distributed on most maps. So the initial placement should probably locate clusters and work them first. Initial positions for the photos that correspond to the points in the cluster would give a good starting distribution if placed on a line through the center of the cluster and the point in question. Clusters near the boundary of the map will prove more interesting.

Jim
0
 
stropmAuthor Commented:
Jim: Before I go sleep, was thinking about your idea. What about to define a stress as distance from another photo instead of a length of a line? Overlap should bring some more stress than just a non-overlap distance (e.g. using square ...).
0
 
JimBrandleyConnect With a Mentor Commented:
I don't think that will work, because the function is discontinuous. Pictures that overlap are illegal, therefore have infinite(?) stress, because your rule is violated. Pictures that share a single point or possibly an edge have zero stress.

However, another measure of "goodness" of distribution could certainly consider the distance between image centers.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.