Text flow in and around irregular containers

1. A method for providing text flow around a non-rectangular graphic, comprising:

using a processor to find the intersection, if any, between a proposed text rectangle and the graphic; and

using the processor to identify as a valid text area within the proposed text rectangle a valid rectangle, if any, that is not within the bounds in the x-direction of an area of intersection between the proposed text rectangle and the graphic; and

further comprising, in the event no valid text area is found, using the processor to look ahead by:

extending the bottom of the proposed rectangle to the bottom of the graphic to form an extended rectangle;

uniting the graphic with the extended rectangle;

subtracting the graphic and the proposed rectangle from the union of the graphic with the extended rectangle;

skipping ahead in the y-direction by a distance equal to the bottom of the extended rectangle minus the bottom of the proposed rectangle if the result of subtracting the graphic and the proposed rectangle from the union of the graphic with the extended rectangle is empty; and

skipping ahead in the y-direction by a distance equal to the top of the result of subtracting the graphic and the proposed rectangle from the union of the graphic with the extended rectangle minus the bottom of the proposed rectangle if the result of subtracting the graphic and the proposed rectangle from the union of the graphic with the extended rectangle is not empty.

2. A method as recited in claim 1 , wherein finding the intersection, if any, between a proposed text rectangle and the graphic includes determining a polygon that at least approximates the graphic.

3. A method as recited in claim 1 , wherein identifying as a valid text area within the proposed text rectangle a valid rectangle, if any, that is not within the bounds in the x-direction of an area of intersection between the proposed text rectangle and the graphic includes determining the bounds in the x-direction of each area of intersection and considering each such area of intersection to be a hole within which text may not be included.

4. A method as recited in claim 1 , wherein identifying as a valid text area within the proposed text rectangle a valid rectangle, if any, that is not within the bounds in the x-direction of an area of intersection between the proposed text rectangle and the graphic includes identifying each such valid text area, if any.

5. A method as recited in claim 1 , wherein identifying as a valid text area within the proposed text rectangle a valid rectangle, if any, that is not within the bounds in the x-direction of an area of intersection between the proposed text rectangle and the graphic includes:

sorting two or more areas of intersection by their respective minimum x-coordinates;

combining overlapping or adjacent areas of intersection; and

using the sorted and combined, if applicable, areas of intersection to find any valid text areas.

6. A method as recited in claim 1 , wherein the graphic comprises an exclusion polygon determined by uniting with an original graphic a set of margin shapes calculated to extend the outer boundary of the original graphic by an amount equal to a desired margin between text flowing around the graphic, on the one hand, and the original graphic as and when rendered on the page, on the other hand.

7. A method as recited in claim 6 , further including defining the margin shapes.

8. A method as recited in claim 7 , wherein defining the margin shapes includes defining for each side of a polygon that at least approximates the graphic a rectangle that is twice as wide as the desired margin, encloses the side, and is bisected by the side; and defining for each vertex of the polygon that at least approximates the graphic a circle centered on the vertex and having a radius equal to the desired margin.

9. A method as recited in claim 1 , further comprising returning as a valid text area only those valid rectangles, if any, that exceed a prescribed minimum size.

10. A system for providing text flow around a non-rectangular graphic, comprising:

a processor configured to find the intersection, if any, between a proposed text rectangle and the graphic; and identify as a valid text area within the proposed text rectangle a valid rectangle, if any, that is not within the bounds in the x-direction of an area of intersection between the proposed text rectangle and the graphic; and in the event no valid text area is found, to look ahead by:

extending the bottom of the proposed rectangle to the bottom of the graphic to form an extended rectangle;

uniting the graphic with the extended rectangle;

subtracting the graphic and the proposed rectangle from the union of the graphic with the extended rectangle;

skipping ahead in the y-direction by a distance equal to the bottom of the extended rectangle minus the bottom of the proposed rectangle if the result of subtracting the graphic and the proposed rectangle from the union of the graphic with the extended rectangle is empty; and

skipping ahead in the y-direction by a distance equal to the top of the result of subtracting the graphic and the proposed rectangle from the union of the graphic with the extended rectangle minus the bottom of the proposed rectangle if the result of subtracting the graphic and the proposed rectangle from the union of the graphic with the extended rectangle is not empty; and

a memory configured to provide instructions to the processor.

11. A system as recited in claim 10 , wherein the processor is configured to find the intersection, if any, between the proposed text rectangle and the graphic at least in part by finding the intersection, if any, between a proposed text rectangle and the graphic includes determining a polygon that at least approximates the graphic.

12. A system as recited in claim 10 , wherein the processor is configured to identify as a valid text area within the proposed text rectangle a valid rectangle, if any, that is not within the bounds in the x-direction of an area of intersection between the proposed text rectangle and the graphic at least in part by determining the bounds in the x-direction of each area of intersection and considering each such area of intersection to be a hole within which text may not be included.

13. A system as recited in claim 10 , wherein the processor is configured to identify as a valid text area within the proposed text rectangle a valid rectangle, if any, that is not within the bounds in the x-direction of an area of intersection between the proposed text rectangle and the graphic at least in part by identifying each such valid text area, if any.

14. A system as recited in claim 10 , wherein the processor is configured to return as a valid text area only those valid rectangles, if any, that exceed a prescribed minimum size.

15. A computer program product for providing text flow around a non-rectangular graphic, the computer program product being embodied in a computer readable medium and comprising computer instructions for:

finding the intersection, if any, between a proposed text rectangle and the graphic; and

identifying as a valid text area within the proposed text rectangle a valid rectangle, if any, that is not within the bounds in the x-direction of an area of intersection between the proposed text rectangle and the graphic; and

further comprising computer instructions for looking ahead, in the event no valid text area is found, including by:

extending the bottom of the proposed rectangle to the bottom of the graphic to form an extended rectangle;

uniting the graphic with the extended rectangle;

subtracting the graphic and the proposed rectangle from the union of the graphic with the extended rectangle;

skipping ahead in the y-direction by a distance equal to the bottom of the extended rectangle minus the bottom of the proposed rectangle if the result of subtracting the graphic and the proposed rectangle from the union of the graphic with the extended rectangle is empty; and

skipping ahead in the y-direction by a distance equal to the top of the result of subtracting the graphic and the proposed rectangle from the union of the graphic with the extended rectangle minus the bottom of the proposed rectangle if the result of subtracting the graphic and the proposed rectangle from the union of the graphic with the extended rectangle is not empty.