Link to home
Start Free TrialLog in
Avatar of stropm
stropm

asked on

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.
SOLUTION
Avatar of GEM100
GEM100

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of stropm
stropm

ASKER

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
Avatar of ozo
Avatar of stropm

ASKER

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 ....
How about Simulated Annealing with distance from the original position as part of the  energy function?
what is a "spageti" picture?
Avatar of stropm

ASKER

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 ....
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.
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.
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.
Avatar of stropm

ASKER

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 .... ;-)
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
Avatar of stropm

ASKER

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 ...).
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
ASKER CERTIFIED SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial