Systems and methods for wrapping a closed polygon around an object

• US 5,805,170 A
• Filed: 05/07/1996
• Issued: 09/08/1998
• Est. Priority Date: 05/07/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Burch, Warren Lee
• Primary Examiner(s): Fetting, Anton
• Assistant Examiner(s): MANCUSO, HUEDUNG XUAN CAO
• Application Number:
  US08/646,129
• Time in Patent Office: 854 Days
• Field of Search: 345/441, 345/434, 345/118, 345/429, 345/443
• US Class Current: 345/619
• CPC Class Codes: G06T 11/00 2D [Two Dimensional] image generation

Abstract

A system and methods for wrapping a closed polygon around an object represented in a computer system, where the closed polygon is substantially adjacent to the object without intersecting or clipping the object. The system and methods are especially useful for fitting text close to the object in a word processor or page layout system. The method involves dividing the object into a number of horizontal threshold bands. Four points are sequentially positioned within each threshold band along the edge of the object in the band. The first and last points are located proximate to the object on the horizontal boundaries of the threshold band, but do not intersect the object. The middle points are located at the intersections of three defined lines. In this configuration, line segments between any of the four points do not and cannot intersect the object. The step of placing four points along the side of the object within a threshold band is repeated within each of the threshold bands along both sides of the object to form a set of polygon points. This set of polygon points is then sequentially connected to form the closed polygon that wraps around the object. Text can then be flowed around the object without any clipping of the object.

Claims

1. An improved method for wrapping a closed polygon around an object, the object represented in a computer memory as a plurality of set points in a two-dimensional coordinate system, comprising the computer-implemented steps of:

dividing said object into a plurality of horizontal threshold bands, each of said plurality of horizontal threshold bands having two horizontal boundaries;

sequentially positioning four polygon points within one of said plurality of threshold bands,

a first one and a last one of said four polygon points being respectively positioned on each of said horizontal boundaries horizontally proximate to one of the plurality of set points but not intersecting said object and

a pair of middle polygon points of said four polygon points being respectively positioned at intersections of a horizontal line containing said first polygon point, a horizontal line containing said last polygon point, and a vertical line extending between said horizontal boundaries that is proximate to but not intersecting a set point representing the outer most edge of said object within said one of said plurality of threshold bands, a line segment between any two consecutive polygon points of said four polygon points not intersecting said object;

repeating said positioning step for each of said plurality of threshold bands along all sides of said object to form a list of polygon points; and

sequentially connecting said polygon points defined by said list to form said closed polygon, said closed polygon being substantially adjacent to said object without intersecting said object.

2. The method of claim 1, further comprising the step, in response to sequentially positioning said four polygon points, of individually adjusting the position of each of said pair of middle polygon points by incrementally moving each of said pair of middle polygon points toward the other of said pair of middle polygon points along said vertical line until the line segment between any two consecutive polygon points of said four polygon points is about to intersect said object.

3. The method claim 2, further comprising the step of simultaneously adjusting the position of both of said pair of middle polygon points by incrementally moving one of said pair of middle polygon points directly toward said first polygon point while incrementally moving the other of said pair of middle polygon points directly toward said last polygon point until the line segment between any two consecutive polygon points of said four polygon points is about to intersect said object.

4. The method of claim 1, further comprising the step of wrapping text around said closed polygon in order to position said text around said object.

5. The method of claim 1, further comprising the step, in response to repeating said positioning step, of removing a center polygon point of any three consecutive polygon points within said list of polygon points that are substantially collinear if a line segment between the two remaining polygon points does not intersect said object.

22. A computer-readable medium on which is stored computer-executable instructions for performing the steps of claim 1.

23. The computer-readable medium of claim 22, wherein said computer-executable instructions further perform the step, in response to repeating said positioning step, of removing a center polygon point of any three consecutive polygon points within said list of polygon points that are substantially collinear if a line segment between the two remaining polygon points does not intersect said object.

6. An improved method for wrapping a closed polygon around an object, the object represented in a computer memory as a plurality of set points in a two-dimensional coordinate system, comprising the computer-implemented steps of:

dividing said object into a plurality of horizontal threshold bands, each of said plurality of horizontal threshold bands having two horizontal boundaries;

identifying a left-side and a right-side of said object;

sequentially positioning four polygon points within one of said plurality of threshold bands along said left-side of said object,

a first and a last of said four polygon points being respectively positioned on each of said horizontal boundaries proximate to one of the plurality of set points but not intersecting said object, and

a pair of middle polygon points of said four polygon points being respectively positioned at intersections of a horizontal line containing said first polygon point, a horizontal line containing said last polygon point, and a vertical line extending between said horizontal boundaries that is proximate to but not intersecting a set point representing the outer most edge of said object within said one of said plurality of threshold bands, a line segment between any two consecutive polygon points of said four polygon points not intersecting said object;

forming a left-side set of polygon points by repeating said positioning step for each of said plurality of threshold bands along said left-side of said object;

forming a right-side set of polygon points by repeating said positioning step but starting along said right-side of said object for each of said plurality of threshold bands along said right-side of said object; and

sequentially connecting said left-side set of polygon points and said right-side set of polygon points to form said closed polygon, said closed polygon being substantially adjacent to said object without intersecting said object.

7. The method of claim 6, further comprising the step, in response to sequentially positioning said four polygon points, of individually adjusting the position of each of said pair of middle polygon points by incrementally moving each of said pair of middle polygon points toward the other of said pair of middle polygon points along said vertical line until the line segment between any two consecutive polygon points of said four polygon points is about to intersect said object.

8. The method claim 7, further comprising the step of simultaneously adjusting the position of both of said pair of middle polygon points by incrementally moving one of said pair of middle polygon points toward said first polygon point while incrementally moving the other of said pair of middle polygon points toward said last polygon point until the line segment between any two consecutive polygon points of said four polygon points is about to intersect said object.

9. The method of claim 6, further comprising the steps of:

in response to forming said left-side set of polygon points, removing a center left-side polygon point of any three consecutive left-side polygon points that are substantially collinear if a line segment between the two remaining left-side polygon points does not intersect said object; and

in response to forming said right-side set of points, removing a center right-side polygon point of any three consecutive right-side polygon points that are substantially collinear if a line segment between the two remaining right-side polygon points does not intersect said object.

10. The method of claim 6, further comprising the steps of:

in response to forming said left-side set of polygon points, removing a center left-side polygon point of any three consecutive left-side polygon points that are substantially collinear if the line segment between the two remaining polygon points does not intersect said object; and

in response to forming said right-side set of points, removing a center polygon point of any three consecutive polygon points within a combination of polygon points remaining in said left-side set of points and said right-side set of points that are substantially collinear if the line segment between the two remaining polygon points in said combination of polygon points does not intersect said object.

11. The method of claim 6, further comprising the step of, in response to forming said right-side set of points, removing a center polygon point of any three consecutive polygon points within a combination of polygon points remaining in said left-side set of polygon points and said right-side set of polygon points that are substantially collinear if the line segment between the two remaining polygon points in said combination of polygon points does not intersect said object.

12. An improved method for wrapping a closed polygon around an object, the object represented in a computer memory as a plurality of set points in a two-dimensional coordinate system, comprising the computer-implemented steps of:

identifying a top most set point and a bottom most set point of said object;

dividing said object into a plurality of horizontal bands;

generating a set of polygon points for the left side of the object from said top most set point to said bottom most set point by

(1) defining a current horizontal band of said object to contain said top most set point,

(2) positioning a first polygon point (A) proximate to said top most set point within said current horizontal band, said first polygon point (A) not intersecting said object,

(3) positioning a second polygon point (B) on a horizontal line containing said first polygon point (A) and to the left of a left most set point defining a left most edge of said object within said current horizontal band, said second polygon point (B) not intersecting said object,

(4) positioning a third polygon point (C) on a horizontal line containing a set point defining a bottom most part of said object within said current horizontal band and to the left of said left most edge of said object within said current horizontal band, said third polygon point (C) not intersecting said object,

(5) positioning a fourth polygon point (D) proximate to the set point defining the bottom most part of said object within said current horizontal band, said fourth polygon point (D) not intersecting said object,

(6) defining a first vector (AB) between said first polygon point (A) and said second polygon point (B), a second vector (BC) between said second polygon point (B) and said third polygon point (C), and a third vector (CD) between said third polygon point (C) and said fourth polygon point (D),

(7) adjusting said second polygon point (B) along said second vector (BC) until said first vector (AB) is substantially proximate to but not intersecting said object,

(8) adjusting said third polygon point (C) along said second vector (BC) until said third vector (CD) is substantially proximate to but not intersecting said object,

(9) simultaneously adjusting said second polygon point (B) toward said first polygon point (A) along said first vector (AB) and said third polygon point (C) toward said fourth polygon point (D) along the third vector (CD) until either said second vector (BC) is substantially proximate to but not intersecting said object or said second polygon point (B) is located in substantially the same location as said first polygon point (A) or said third polygon point (C) is located in substantially the same location as said fourth polygon point (D),

(10) adding the two-dimensional coordinates of said first, second, third, and fourth polygon points to said left-side set of points,

(11) redefining said current horizontal band by selecting said horizontal band located immediately below said current band,

(12) conducting steps (2) through (11) for each of the remaining horizontal bands;

generating a set of polygon points for the right side of the object from said bottom most set point to said top most set point by redefining said current horizontal band of said object to contain said bottom most set point, and repeating steps (1) through (12) for each of the remaining horizontal bands exchanging orientation references of "left" with "right", "up" with "down", and "top" with "bottom"; and

connecting adjacent polygon points within said left-side set of polygon points and said right-side set of polygon points to form said closed polygon, said closed polygon being substantially adjacent to said object without intersecting said object.

13. The method of claim 12, further comprising the steps of:

in response to generating said left-side set of polygon points, removing a center left-side polygon point of any three consecutive left-side polygon points that are substantially collinear if a line segment between the two remaining left-side polygon points does not intersect said object; and

in response to generating said right-side set of polygon points, removing a center right-side polygon point of any three consecutive right-side polygon points that are substantially collinear if a line segment between the two remaining right-side polygon points does not intersect said object.

14. The method of claim 12, further comprising the steps of:

in response to generating said left-side set of polygon points, removing a center left-side polygon point of any three consecutive left-side polygon points that are substantially collinear if the line segment between the two remaining left-side polygon points does not intersect said object; and

in response to generating said right-side set of polygon points, removing a center polygon point of any three consecutive polygon points within a combination of polygon points remaining in said left-side set of polygon points and said right-side set of polygon points that are substantially collinear if the line segment between the two remaining polygon points in said combination of polygon points does not intersect said object.

15. The method of claim 12, further comprising the step of, in response to generating said right-side set of points, removing a center polygon point of any three consecutive polygon points within a combination of polygon points remaining in said left-side set of polygon points and said right-side set of polygon points that are substantially collinear if the line segment between the two remaining polygon points in said combination of polygon points does not intersect said object.

16. A computer system for wrapping a closed polygon around an object, the object represented in a computer memory as a plurality of set points in a two-dimensional coordinate system, the computer system comprising:

a central processing unit (CPU);

an input device coupled to said CPU for selecting said object;

a pixel-based display device coupled to said CPU for displaying said object and said closed polygon; and

said CPU being operative to;

draw said object on said display device,

divide said object into a plurality of horizontal threshold bands, each of said plurality of horizontal bands having two horizontal boundaries,

position four polygon points in a sequential manner along the edge of said object within each of said plurality of horizontal bands to form a plurality of polygon points,

a first one and a last one of said four polygon points being respectively positioned on each of said horizontal boundaries horizontally proximate to one of the plurality of set points but not intersecting said object,

a pair of middle polygon points of said four polygon points being respectively positioned at intersections of a horizontal line containing said first polygon point, a horizontal line containing said last polygon point, and a vertical line extending between said horizontal boundaries that is proximate to but not intersecting a set point representing the outer most edge of said object within said one of said plurality of threshold bands, a line segment between any two consecutive polygon points of said four polygon points not intersecting said object,

verify that the line segment between any two consecutive polygon points of said plurality of polygon points does not intersect said object, and

connect said plurality of polygon points to form said closed polygon, said closed polygon being substantially adjacent to said object without intersecting said object.

17. The system of claim 16, wherein said CPU is further operative to remove a center polygon point of any three consecutive polygon points within said plurality of polygon points that are substantially collinear if a line segment between the two remaining polygon points does not intersect said object.

18. A computer system for wrapping a closed polygon around an object, the object represented in a computer memory as a plurality of set points in a two-dimensional coordinate system, the computer system comprising:

a central processing unit (CPU);

an input device coupled to said CPU for selecting said object;

a pixel-based display device coupled to said CPU for displaying said object; and

said CPU being operative to;

draw said object on said display device, said object having a left-side and a right-side,

divide said object into a plurality of horizontal threshold bands, each of said plurality of horizontal bands having two horizontal boundaries,

position four left-side polygon points in a sequential manner along said left-side of said object within each of said plurality of horizontal bands to form a left-side set of polygon points,

a first one and a last one of said four left-side polygon points being respectively positioned on each of said horizontal boundaries horizontally proximate to one of the plurality of set points but not intersecting said object and;

a pair of middle left-side polygon points of said four left-side polygon points being respectively positioned at intersections of a horizontal line containing said first left-side polygon point, a horizontal line containing said last left-side polygon point, and a vertical line extending between said horizontal boundaries that is proximate to but not intersecting a set point representing the outer most edge of said object within said one of said plurality of threshold bands, a line segment between any two consecutive left-side polygon points of said four left-side polygon points not intersecting said object,

position four right-side polygon points in a sequential manner along said right-side of said object within each of said plurality of horizontal bands to form a right-side set of polygon points, said four right-side polygon points being positioned in the same manner along said right-side of said object as said four left-side polygon points are positioned along said left-side of said object, and

connect said left-side set of polygon points and said right-side set of polygon points to form said closed polygon, said closed polygon being substantially adjacent to said object without intersecting said object.

19. The system of claim 18, wherein said CPU is further operative to remove a center left-side polygon point of any three consecutive left-side polygon points that are substantially collinear if a line segment between the two remaining left-side polygon points does not intersect said object.

20. The system of claim 18, wherein said CPU is further operative to remove a center right-side polygon point of any three consecutive right-side polygon points that are substantially collinear if a line segment between the two remaining right side polygon points does not intersect said object.

21. The system of claim 18, wherein said CPU is further operative to remove a center polygon point of any three consecutive polygon points within a combined list of polygon points formed by said left-side set of left-side polygon points and said right-side set of right-side polygon points that are substantially collinear if a line segment between the two remaining polygon points does not intersect said object.