Ordering a plurality of objects

• US 6,782,141 B1
• Filed: 05/09/2000
• Issued: 08/24/2004
• Est. Priority Date: 05/10/1999
• Status: Expired due to Term

• Current Assignee: Canon Information Systems Research Australia Pty Limited (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Coleman, Nicolas Leslie, Bock, Oliver, Newham, Scott T., Herceg, Marija
• Primary Examiner(s): Johns, Andrew W.
• Application Number:
  US09/566,089
• Time in Patent Office: 1,568 Days
• Field of Search: 382/100, 382/284, 382/286, 382/291, 382/293, 382/294, 382/305, 345/629, 345/634, 345/637, 715/517, 715/523, 715/524
• US Class Current: 382/291
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: H04N 1/3873 defined only by a limited number of coordinate points or parameters, e.g. corners, centre; for trimming

Abstract

The method comprises a first determining step 104, a measuring step 110, a second determining step 112, and a re-ordering step 114. In the first determining step 104, the method determines a line between adjacent center points of the original images. In the measuring step 110, the method measures, for each line, the shortest distance from the insertion point of the new image inserted on the page to said line. In the second determining step 112, the method determines the minimum of the shortest distances. Finally, in the re-ordering step 114, the method re-orders the one-dimensional list by inserting the new image in the list of original images at that position in the list corresponding to the line having the minimum shortest distance.

Claims

1. A method of re-ordering a one-dimensional list of a number of original objects arranged in a space, upon the insertion of a new object in the space, the method comprising:

(i) determining, for each adjacent original object if any, a corresponding line between points of the adjacent original objects;

(ii) measuring, for each said line, the shortest distance from an insertion point of the new object to the said line;

(iii) determining the minimum of the shortest distances; and

(iv) re-ordering said one-dimensional list by inserting the new object in said list of original objects at that position in the list corresponding to that line having the minimum shortest distance.

2. A method as claimed in claim 1, wherein the objects are arranged in a two-dimensional space.

3. A method as claimed in claim 1, wherein the objects are arranged in a three-dimensional space.

4. A method as claimed in claim 1, wherein the said step (i) comprises the sub-steps of:

(i)(a) determining a corresponding line between a first boundary point surrounding the objects and said point of a first said original object;

(i)(b) determining a corresponding line between a second boundary point surrounding the objects and said point of a last said original object; and

(i)(c) determining, for each adjacent original object if any, a corresponding line between points of the adjacent original objects.

5. A method as claimed in claim 1 or 4, wherein said points of the objects are the center points.

6. A method as claimed in claim 1, wherein when an original object is moved to a new position in the space, the moved original object is treated as the new object and the old position of the original object that was moved is taken into account when re-ordering the list.

7. A method as claimed in claim 1, wherein said measuring step comprises the sub-steps of:

(ii)(a) measuring, for each line, the perpendicular distance from the insertion point to said line; and

if there is no perpendicular distance for that line

(ii)(b) measuring the distance between the insertion point and the closest point of the pair of end points forming said line.

8. A method of re-ordering a one-dimensional list of a number of original images arranged two-dimensionally on a page, upon the insertion of a new image on the page, the method comprising:

(i) determining, for each adjacent original images if any, a corresponding line between points of the adjacent original images;

(ii) determining a corresponding line between a first boundary point of the page and a said point of the first original image on the page;

(iii) determining a corresponding line between a second boundary point of the page and a said point of the last original image on the page;

(iv) measuring, for each said line, the shortest distance from an insertion point of the new image on the page to the said line;

(v) determining the minimum of the shortest distances; and

(vi) re-ordering said one-dimensional list by inserting the new image in said list of original images at that position in the list corresponding to that line having the minimum shortest distance.

9. A method as claimed in claim 8, wherein when an original image is moved to a new position on the page, the moved original image is treated as the new image and the old position of the original image that was moved is taken into account when re-ordering the list.

10. A method as claimed in claim 8, wherein the said points are center points and the method further comprises, prior to step (i), the following step:

(a) determining the center points of the one or more original images.

11. A method as claimed in claim 8, wherein the first and second boundary points are determined by

(a) averaging the x and y co-ordinates of the center points of a first half of the original images to determine a first point;

(b) averaging the x and y co-ordinates of the center points of a second half of the original images to determine a second point;

(c) generating a trend line between the first and second points; and

(d) generating the said first and second boundary points as those points on the boundary of the page which intersect the trend line.

12. A method as claimed in claim 11, wherein if there are an odd number of original images, then said first half and second half of original images comprise a middle image.

13. A method as claimed in claim 11, wherein if said first and second points are the same, then the trend line is generated from the top left of the page to the bottom right of the page.

14. A method as claimed in claim 11, wherein if said first and second points are the same, then the trend line is generated from the top right of the page to the bottom left of the page.

15. A method as claimed in claim 8, wherein if an image is deleted from a page, it is removed from the ordered list, whereby the image before it is now adjacent to the image after it.

16. A method as claimed in claim 8, wherein said measuring step comprises the sub-steps of:

(ii)(a) measuring, for each line, the perpendicular distance from the insertion point to said line; and

if there is no perpendicular distance for that line

(ii)(b) measuring the distance between the insertion point and the closest point of the pair of points forming said line.

17. An apparatus for re-ordering a one-dimensional list of a number of original objects arranged in a space, upon the insertion of a new object in the space, the apparatus comprising:

means for determining, for each adjacent original object if any, a corresponding line between points of the adjacent original objects;

means for measuring, for each said line, the shortest distance from an insertion point of the new object to the said line;

means for determining the minimum of the shortest distances; and

means for re-ordering said one-dimensional list by inserting the new object in said list of original objects at that position in the list corresponding to that line having the minimum shortest distance.

18. An apparatus for re-ordering a one-dimensional list of a number of original images arranged two-dimensionally on a page upon the insertion of a new image on the page, the apparatus comprising:

means for determining, for each adjacent original images if any, a corresponding line between points of the adjacent original images;

means for determining a corresponding line between a first boundary point of the page and the centre point of the first original image on the page;

means for determining a corresponding line between a second boundary point and the centre point of the last original image on the page;

means for measuring, for each said line, the shortest distance from an insertion point of the new image on the page to the said line;

means for determining the minimum of the shortest distances; and

means for re-ordering said one-dimensional list by inserting the new image in said list of original images at that position in the list corresponding to that line having the minimum shortest distance.

19. A computer program product including a computer readable medium having recorded thereon a computer program for re-ordering a one-dimensional list of a number of original objects arranged in a space, upon the insertion of a new object in the space, the computer program product comprising:

means for determining, for each adjacent original object if any, a corresponding line between points of the adjacent original objects;

means for measuring, for each said line, the shortest distance from an insertion point of the new object to the said line;

means for determining the minimum of the shortest distances; and

means for re-ordering said one-dimensional list by inserting the new object in said list of original objects at that position in the list corresponding to that line having the minimum shortest distance.

20. A computer program product including a computer readable medium having recorded thereon a computer program for re-ordering a one-dimensional list of a number of original images arranged two-dimensionally on a page upon the insertion of a new image on the page, the computer program product comprising:

means for determining, for each adjacent original images if any, a corresponding line between points of the adjacent original images;

means for determining a corresponding line between a first boundary point of the page and the centre point of the first original image on the page;

means for determining a corresponding line between a second boundary point and the centre point of the last original image on the page;

means for measuring, for each said line, the shortest distance from an insertion point of the new image on the page to the said line;

means for determining the minimum of the shortest distances; and

means for re-ordering said one-dimensional list by inserting the new image in said list of original images at that position in the list corresponding to that line having the minimum shortest distance.

21. A method of determining a one-dimensional order of a plurality of objects arranged N-dimensionally, where N is greater than or equal to 2 and the method comprises the following steps:

measuring, for each said object, the shortest distance from a predetermined point of the object to a predetermined N−

1 dimensional surface; and

determining a one-dimensional order of said objects according to the measured shortest distances.

22. A method as claimed in claim 21, wherein N is equal to two and the predetermined N−

1 dimensional surface is a predetermined line.

23. A method as claimed in claim 22, wherein said method further comprises, prior to the measuring step:

selecting said predetermined line according to user input.

24. A method as claimed in claim 22, wherein the predetermined line is straight.

25. A method as claimed in claim 21, wherein the predetermined point is the centre of the object.

26. A method as claimed in claim 23, wherein the selecting step comprises selecting the sign and angle of the predetermined line.

27. A method as claimed in claim 21, wherein said objects are images arranged two-dimensionally on a page.

28. A method as claimed in claim 22, wherein the predetermined line is positioned in such a manner that the smallest measured shortest distance will correspond to a said image in the top left corner of the page.

29. A method of forming a one-dimensional list of a plurality of images arranged two-dimensionally on a page, the method comprising the following steps of:

selecting a substantially linear line according to user input;

measuring, for each said image, the shortest distance from a predetermined point of the image to the substantially linear line; and

arranging the images in a one-dimensional list according to the measured shortest distances.

30. An apparatus for determining a one-dimensional order of a plurality of objects arranged two-dimensionally, the apparatus comprising:

means for measuring, for each said object, the shortest distance from a predetermined point of the object to a predetermined line; and

means for determining a one-dimensional order of said objects according to the measured shortest distances.

31. An apparatus for forming a one-dimensional list of a plurality of images arranged two-dimensionally on a page, the apparatus comprising:

means for selecting a substantially linear line according to user input;

means for measuring, for each said image, the shortest distance from a predetermined point of the image to the substantially linear line; and

means for arranging the images in a one-dimensional list according to the measured shortest distances.

32. A computer program product including a computer readable medium having recorded thereon a computer program for determining a one-dimensional order of a plurality of objects arranged two-dimensionally, the computer program product comprising:

means for measuring, for each said object, the shortest distance from a predetermined point of the object to a predetermined line; and

means for determining a one-dimensional order of said objects according to the measured shortest distances.

33. A computer program product including a computer readable medium having recorded thereon a computer program for forming a one-dimensional list of a plurality of images arranged two dimensionally on a page, the computer program product comprising:

means for selecting a substantially linear line according to user input;

means for measuring, for each said image, the shortest distance from a predetermined point of the image to the substantially linear line; and

means for arranging the images in a one-dimensional list according to the measured shortest distances.