Solved

# Picture positionig algorithm for non overlapping

Posted on 2007-07-22
Medium Priority
456 Views
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.
0
Question by:stropm
• 6
• 4
• 2
• +1

LVL 8

Assisted Solution

GEM100 earned 200 total points
ID: 19542337
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:
<?
\$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 ();
{
{
case 'png':
break;
case 'gif':
break;
case 'jpeg':
case 'jpg':
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

Author Comment

ID: 19542530
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

LVL 85

Expert Comment

ID: 19542549
0

Author Comment

ID: 19542630
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

LVL 85

Expert Comment

ID: 19542686
How about Simulated Annealing with distance from the original position as part of the  energy function?
what is a "spageti" picture?
0

Author Comment

ID: 19542958
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

LVL 8

Expert Comment

ID: 19543175
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

LVL 22

Expert Comment

ID: 19543184
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

LVL 22

Expert Comment

ID: 19543263
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

Author Comment

ID: 19543530
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

LVL 22

Expert Comment

ID: 19543559
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

Author Comment

ID: 19543587
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

LVL 22

Assisted Solution

JimBrandley earned 400 total points
ID: 19543600
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

Accepted Solution

stropm earned 0 total points
ID: 21348088
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

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

3 proven steps to speed up Magento powered sites. The article focus is on optimizing time to first byte (TTFB), full page caching and configuring server for optimal performance.
Many old projects have bad code, but the budget doesn't exist to rewrite the codebase. You can update this code to be safer by introducing contemporary input validation, sanitation, and safer database queries.
The viewer will learn how to create a basic form using some HTML5 and PHP for later processing. Set up your basic HTML file. Open your form tag and set the method and action attributes.: (CODE) Set up your first few inputs one for the name and â€¦
Use Wufoo, an online form creation tool, to make powerful forms. Learn how to choose which pages of your form are visible to your users based on their inputs. The page rules feature provides you with an opportunity to create if:then statements for yâ€¦
###### Suggested Courses
Course of the Month16 days, 2 hours left to enroll