Estimation of overlap of polygons

• US 7,505,048 B2
• Filed: 04/25/2003
• Issued: 03/17/2009
• Est. Priority Date: 04/25/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Su, Philip Ti-Fei
• Primary Examiner(s): Chauhan; Ulka
• Assistant Examiner(s): Chow; Jeffrey J
• Application Number:
  US10/423,533
• Publication Number:
  US 20040211071A1
• Time in Patent Office: 2,153 Days
• Field of Search: 345620-639, 345/441
• US Class Current: 345/629
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G06T 15/40 Hidden part removal

Abstract

Various techniques are disclosed for easily and accurately estimating the amount of overlap between two or more polygons. With various examples of these techniques, a pattern of objects, such as points, is provided over the entire area of the first polygon. The amount of objects within the first polygon then is determined, as is the amount of objects within the first polygon that also are located within the second polygon. The ratio of the amount of objects located within both the first polygon and the second polygon to the total amount of objects located within the first polygon then provides an estimate of the amount of the first polygon overlapped by the second polygon.

Claims

1. A method of estimating overlap between polygons, comprising:

providing a pattern of objects over an entire area of a first polygon;

determining a first amount of the objects that are located within the area of the first polygon;

determining a second amount of the objects that are located within both the area of the first polygon and an area of a second polygon,

the first polygon being a bounding area for content and the second polygon being a bounding area for a selection lasso, or the first polygon being a bounding area for a selection lasso and the second polygon being a bounding area for content;

wherein the bounding area for content and the bounding area for the selection lasso are displayed on a display device;

determining a ratio of the amount of objects that have been determined by a processor to be within the area of the first polygon to the amount of objects located within both the area of the first polygon and the area of the second polygon;

estimating an overlap of the first polygon with the second polygon based on the determined ratio;

determining a dimension of the first polygon; and

providing one or more parallel lines spaced along the dimension of the first polygon, such that the lines intersect the polygon; and

for each line,

identifying each intersection of the line with the polygon, and locating objects on the line between odd intersections of the line with the polygon and even intersections of the line with the polygon.

2. The method recited in claim 1, wherein

the first amount is a number of points that are located within the area of the first polygon, and

the second amount is a number of points that are located within both the area of the first polygon and the area of the second polygon.

3. The method recited in claim 1, wherein the pattern is a regular pattern.

4. The method recited in claim 1, wherein the pattern is a random pattern.

5. The method recited in claim 1, wherein the pattern of objects extends outside of the first polygon.

6. The method recited in claim 1, further comprising providing the pattern of objects as a fixed number of objects independent of the area of the first polygon.

7. The method recited in claim 1, further comprising determining whether the content is selected based upon the estimated overlap of the first polygon with the second polygon.

8. The method recited in claim 1, further comprising selecting the content based upon the estimated overlap of the first polygon with the second polygon.

9. The method recited in claim 1, further comprising providing the pattern of objects as a number of objects based upon a size of the first polygon.

10. An apparatus for estimating overlap between polygons, comprising:

a processor that

creates a pattern of objects within an entire area of a first polygon;

determines a dimension of the first polygon; and

provides one or more parallel lines spaced along the dimension of the first polygon, such that the lines intersect the polygon; and

for each line,

identifies each intersection of the line with the polygon, and locates objects on the line between odd intersections of the line with the polygon and even intersections of the line with the polygon;

determines a first amount of the objects located within the area of the first polygon;

determines a second amount of the objects located within both the area of the first polygon and an area of a second polygon,

the first polygon being a bounding area for content and the second polygon being a bounding area for a selection lasso, or the first polygon being a bounding area for a selection lasso and the second polygon being a bounding area for content;

wherein the bounding area for content and the bounding area for the selection lasso are displayed on a display device;

determines a ratio of the amount of objects that have been determined to be within the area of the first polygon to the amount of objects located within both the area of the first polygon and the area of the second polygon; and

estimates an overlap of the first polygon with the second polygon based on the determined ratio.

11. The apparatus recited in claim 10, wherein the processor creates a pattern of points.

12. The apparatus recited in claim 10, wherein the processor creates the pattern of objects as a fixed number of objects independent of the area of the first polygon.

13. The apparatus recited in claim 10, wherein

the first amount is a number of points that are located within the area of the first polygon, and

the second amount is a number of points that are located within both the area of the first polygon and the area of the second polygon.

14. The apparatus recited in claim 10, wherein the pattern is a regular pattern.

15. The apparatus recited in claim 10, wherein the pattern in a random pattern.

16. The apparatus recited in claim 10, wherein the pattern of object is a fixed number of objects independent of the area of the first polygon.

17. A computer-readable storage medium having stored thereon computer-executable instructions for estimating overlap between polygons, the computer instructions when executed causes a processor to perform the following steps:

identifying a pattern of objects arranged over an entire area of a first polygon;

determining a first amount of the objects that are located within the area of the first polygon;

determining a second amount of the objects that are located within both the area of the first polygon and an area of a second polygon,

the first polygon being a bounding area for content and the second polygon being a bounding area for a selection lasso, or the first polygon being a bounding area for a selection lasso and the second polygon being a bounding area for content;

wherein the bounding area for content and the bounding area for the selection lasso are displayed on a display device; and

determining a ratio of the amount of objects that have been determined to be within the area of the first polygon to the amount of objects located within both the area of the first polygon and the area of the second polygon;

estimating an overlap of the first polygon with the second polygon based on the determined ratio;

determining a dimension of the first polygon; and

providing one or more parallel lines spaced along the dimension of the first polygon, such that the lines intersect the polygon; and

for each line,

identifying each intersection of the line with the polygon, and locating objects on the line between odd intersections of the line with the polygon and even intersections of the line with the polygon.

18. The computer-readable storage medium recited in claim 17, having further computer-executable instructions for providing the pattern of objects arranged over the entire area of the first polygon.

19. The computer-readable storage medium recited in claim 17, having further computer-executable instructions for

determining the first amount as a number of points that are located within the area of the first polygon, and

determining the second amount as a number of points that are located within both the area of the first polygon and the area of a second polygon.

20. The computer-readable storage medium recited in claim 17, having further computer-executable instructions for

selecting the content based upon the estimated overlap of the first polygon with the second polygon.