Method and apparatus for automatically generating symbol images against a background image without collision utilizing distance-dependent attractive and repulsive forces in a computer simulation

• US 5,355,314 A
• Filed: 11/05/1993
• Issued: 10/11/1994
• Est. Priority Date: 03/26/1990
• Status: Expired due to Fees

• Current Assignee: Hammond World Atlas Corp. (Kappa Publishing Group, Inc.)
• Original Assignee: Hammond Incorporated
• Inventors: Feigenbaum, Mitchell
• Primary Examiner(s): Envall, Jr., Roy N.
• Assistant Examiner(s): BAI, ARI
• Application Number:
  US08/149,650
• Time in Patent Office: 340 Days
• Field of Search: 364/420, 364/449, 364/461, 434/142, 434/143, 340/286.14, 382/58
• US Class Current: 345/629
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves

Abstract

A method for automatically placing objects on a surface in proximity to corresponding predetermined locations without collision with such locations or other objects by defining a distance dependent attractive force between each object and the corresponding location which increases with increasing distance between the object and the location, and defining distance dependent repulsive force between each object and its neighboring objects and locations, such repulsive force decreasing with increasing distance. The initial position for each object is established in proximity with the corresponding location in accordance with predetermined criteria. Thereafter the motion of the objects under the influence of such forces and of a frictional retarding force are determined by marginally stable incremental integration of such motion. The objects are statically placed at a predetermined target distance from the corresponding location at the position around the location at which the sum of the absolute values of the magnitudes of the forces acting on the object is at a minimum.

Claims

1. A method for automatically producing images containing a background image and symbol images of variable position in proximity to corresponding symbol images at predetermined locations on said background image, without overlap of said variable symbol images and said predetermined symbol images, comprising the steps of:

inputting to a processor means and storing in a said first memory means signals corresponding to configurations and positions of said background image and said predetermined symbol images and configurations of said variable symbol images;

generating in said processor means signal sequences representing a distance-dependent attractive force between each variable symbol image and the corresponding predetermined symbol image, such attractive force increasing with the distance between such variable symbol image and such corresponding predetermined symbol image;

distance dependent repulsive forces between each variable symbol image and other variable symbol images and predetermined symbol images in proximity to such variable symbol image, such repulsive force decreasing with increasing distance between such variable symbol image and such other variable symbol images and predetermined symbol images; and

a retarding force between each such variable symbol image and the background image;

fixing and storing in a second memory means signals corresponding to an initial position of each such variable symbol image in proximity with the corresponding predetermined symbol image;

generating in said processor means signals corresponding to a non-overlapping position for each of such variable symbol images in proximity to such corresponding predetermined symbol images by simultaneously incrementally integrating the motion of such variable symbol images on such background image under the influence of said forces over an integration period made up of a plurality of such increments, and to update said initial position of such variable symbol images stored in said second memory means with the results of said such incremental integration;

outputting to an image generation means image generation signals corresponding to the configuration and position of said background image and said predetermined symbol images and the configuration and updated position of said variable symbol images; and

generating an output image including said background image, said variable symbol images and said predetermined symbol images in accordance with said image generation signals.

2. The method according to claim 1 further comprising the step of growing each of said variable symbol images about a centroid from a relatively small size to substantially full size during the incremental integration.

3. The method according to claims 1 or 2 wherein the position of each of said predetermined symbol images is fixed on said background image.

4. The method according to claim 2 wherein said retarding force is a frictional force.

5. The method according to claims 1 or 2 wherein said distance-dependent attractive force is a spring force and said distance-dependent repulsive forces are coulomb forces.

6. The method according to claim 5 wherein the repulsive coulomb force experienced by a variable symbol image becomes substantially increased and reversed in direction if such variable symbol image overlaps with a predetermined symbol image or other variable symbol images.

7. The method according to claims 1 or 2 wherein said predetermined symbol images have a predetermined symbol radius and wherein said repulsive forces include a force between each variable symbol image and such predetermined symbol image such that the object is repelled from such predetermined symbol image if it overlaps such radius.

8. The method according to claim 7 wherein said background image is a map, said predetermined symbol images having a predetermined symbol radius are representative of cities to be positioned on said map and said variable symbol images are in the form of field rectangles.

9. The method according to claim 2 wherein the configuration of said variable symbol images is anisotropic and the repulsive force between each variable symbol image and such other variable symbol images in proximity to such variable symbol image is calculated based on the positional relationship of such variable symbol image to such other variable symbol images and the anisotropic configuration of such variable symbol images.

10. The method according to claim 9 wherein the repulsive forces further include an average background force calculated by summing vectorially radial forces exerted on each variable symbol image by such other variable symbol images in proximity to such variable symbol image.

11. The method according to claims 1 or 2 wherein said position establishing step further includes performing a first static placement on each of said variable symbol images before such incremental integration, the steps of said static placement including:

determining a non-overlapping location for each of such variable symbol images in proximity to such corresponding predetermined symbol images by static placing of each of said variable symbol images at the location at a predetermined proximity around said corresponding predetermined symbol image where the sum of the absolute value of the magnitude of the forces acting on such variable symbol image is the minimum.

12. The method according to claim 11 wherein the steps of said static placement further includes:

calculating the sum of the absolute value of the magnitudes of the forces on the variable symbol image at each of a plurality of positions of predetermined proximity about its corresponding predetermined symbol image; and

placing the variable symbol image at the position where said calculated sum of the forces is lowest.

13. The method according to claim 12 further comprising the step of performing a local minimization at the position with the lowest calculated sum of the absolute value of the magnitude of the forces.

14. The method according to claim 12 wherein said first static placement further includes weighing the calculated sums for each of said positions by a factor reflecting the desirability of placing said variable symbol image in said position, and said placing step operates to place the variable symbol image where the weighted calculated sum is lowest.

15. The method according to claim 12 further including the step of:

calculating the sums of the absolute values of the magnitudes of the forces on each of said variable symbol images at their position immediately prior to said first static placement; and

wherein said first static placement is performed on such variable symbol images in the order of decreasing sums of such absolute values.

16. The method according to claim 12 further including the step of:

performing a second static placement on each of said variable symbol images after said incremental integration in the same manner as said first static placement.

17. The method according to claim 16 wherein said second static placement is performed in the order of decreasing sums of absolute value of the magnitude of the forces on such variable symbol images at the end of such first incremental integration.

18. The method according to claim 16 further comprising the steps of:

again positioning said variable symbol images on said background symbol image by simultaneously determining by incremental integration the motion of said variable symbol images on said background image under the influence of said forces over an integration period made up of a plurality of such increments from the initial positions determined by said second static placement step, wherein the increments of such second incremental integration are shorter than the increments of the first incremental integration;

Calculating the sums of the absolute values of the magnitudes of the forces on such variable symbol images at the end of such second incremental integration;

performing a third static placement on such variable symbol images in the same manner as said second static placement in the order of decreasing sums of absolute values calculated after said second incremental integration;

comparing the sums of the absolute values of the magnitude of the forces on each variable symbol image at the position established by said third static placement with the sum calculated at the position at the end of said second incremental integration; and

positioning said variable symbol images at the one of those two positions at which such sum of absolute values is lower, provided that such variable symbol image shall not be placed at the position determined by such second incremental integration if the distance between the predetermined symbol image and the variable symbol image at the end of such second integration is greater than a predetermined amount.

19. The method according to claim 18 wherein the increments of the first incremental integration are of a size sufficient to induce marginal convergence.

20. The method according to claim 18 further comprising the steps of:

performing a fourth static placement in the same manner of said third static placement for each variable symbol image which overlaps with another variable symbol image or which experiences a sum of absolute values of magnitude of force above a predetermined level at the position established by the third static placement; and

performing a fifth static placement in the same manner as said fourth static placement on the overlapping variable symbol image or the variable symbol image which is asserting the most force on such variable symbol image; and

then performing a final static placement on such variable symbol image.

21. The method according to claim 12 wherein the position of each of said plurality of positions is predetermined.

22. The method according to claims 1 or 2 wherein said background image further has on it a fractually curved line representing a linear feature on such background image, said line extending between endpoints on said background image and being defined by a plurality of sample points on said background image and wherein said variable symbol images include an articulated variable symbol image corresponding to such line, further comprising the steps of:

generating in said processor means signal sequences defining a second line substantially parallel to such first line within a predetermined proximity of said first line, said articulated variable symbol image being constrained to move along said second line;

generating in said processor means signal sequences defining a repulsive force between each end of said second line and said articulated variable symbol image, said repulsive force decreasing with increasing distance between each said end and said articulated variable symbol image;

generating in said processor means signal sequences defining an attractive force between a selected point along said second line and said articulated variable symbol image, said attractive force increasing with increasing distance between said articulated variable symbol image and said selected point; and

generating in said processor means signal sequences defining a repulsive force between said articulated variable symbol image and portions of such second line having relatively high curvature, such articulated variable symbol image being positioned along such second line during the incremental integration of the motion of the variable symbol images on the background image.

23. The method according to claims 1 or 2 wherein said background symbol image further has defined on it a bounded area representing a feature on such background symbol image and wherein said variable symbol images include a first variable symbol image corresponding to such bounded area, the boundary of said bounded area being represented as a set of sample points, further comprising the steps of:

generating in said processor means signal sequences representing a distance-dependent attractive force between such first variable symbol image and a center point of such bounded area, such attractive force increasing with the distance between such first variable symbol image and such center point;

generating in said processor means signal sequences representing a distance-dependent repulsive force between such first variable symbol image and such sample points of such bounded areas, such repulsive force decreasing with increasing distance between such first variable symbol image and such sample points; and

positioning such first variable symbol image in proximity to such bounded area during said incremental integration.

24. A method for automatically producing images containing a background image and symbol images of variable position in proximity to corresponding symbol images at predetermined locations on said background image, without overlap of said variable symbol images and said predetermined symbol images, comprising the steps of:

inputting to a processor means and storing in a memory means signals corresponding to said background image, said variable symbol images and said predetermined symbol images;

generating in said processor means signal sequences representing a distance-dependent repulsive forces between each variable symbol image and other variable symbol images and predetermined symbol images in proximity to such variable symbol image, such repulsive force decreasing with increasing distance between such variable symbol image and such other variable symbol images and predetermined symbol images;

generating signals corresponding to a non-overlapping position for each of such variable symbol images in proximity to such corresponding predetermined symbol images by static placing of each of said variable symbol images at a predetermined proximity around said corresponding predetermined symbol image when the weighted sum of the absolute value of the magnitude of the forces acting on such a variable symbol image is the minimum;

outputting to an image generation means image generation signals corresponding to the configuration and position of said background image, said variable symbol images and said predetermined symbol images; and

generating an output image including said background image, said variable symbol images and said predetermined symbol images in accordance with said image generation signals.

25. The method according to claim 24 wherein the steps of said static placement further includes:

calculating the sum of the absolute value of the magnitudes of the forces on the variable symbol image at each of a plurality of positions of predetermined proximity about its corresponding predetermined symbol image; and

placing the variable symbol image at the position where said calculated sum of the forces is lowest.

26. The method according to claim 25 further comprising the step of performing a local minimization at the position with the lowest calculated sum of the absolute value of the magnitudes of the forces.

27. An image generation system for automatically producing images including a background image and symbol images of variable position in proximity to corresponding symbol images at predetermined locations on said background image, without overlap of said variable symbol images and said predetermined symbol images, comprising:

interface means for generating digital image signals corresponding to a physical configuration and position of said variable symbol images, said predetermined symbol images and said background image;

first memory means for storing said digital signals corresponding to said background image, said variable symbol images and said predetermined symbol images;

processor means responsive to a control program for generating and transferring to an image generation means signals specifying the configuration and positions of said symbol and background images said processor means being adapted to generate signal sequences representing a distance-dependent attractive force between each variable symbol image and the corresponding predetermined symbol image, such attractive force increasing with the distance between such variable symbol image and such corresponding predetermined symbol image;

distance-dependent repulsive forces between each variable symbol image and other variable symbol images and predetermined symbol images in proximity to such variable symbol image, such repulsive force decreasing with increasing distance between such variable symbol image and such other variable symbol images and predetermined symbol images; and

a retarding force between each such variable symbol image and the background image;

second memory means for storing digital signals corresponding to an initial position of each said variable symbol image established by said processor means, said processor means being further adapted to generate signals corresponding to a non-overlapping position for each of such variable symbol image in proximity to such corresponding predetermined symbol images by simultaneously incrementally integrating the motion of such variable symbol images on such background image under the influence of said forces over an integration period made up of a plurality of such increments, and to update said initial position of such variable symbol images stored in said second memory means with the results of said such incremental integration; and

image generation means for producing said variable symbol images, said predetermined symbol images and said background image in response to signals generated by said processor means specifying the configuration and positions of said images.

28. The apparatus according to claim 27 wherein said background image, said variable symbol images and said predetermined symbol images are cartographic images.

29. The apparatus according to claim 28 wherein said cartographic images are features on a map.

30. The apparatus according to claims 27, 28 or 29 wherein said processor means includes means for growing each of said variable symbol images about a centroid from relatively small size to substantially full size during the incremental integration.