Estimation of overlap of polygons

• US 20040211071A1
• Filed: 04/25/2003
• Published: 10/28/2004
• Est. Priority Date: 04/25/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Su, Philip Ti-Fei
• Granted Patent: US 7,505,048 B2
• Time in Patent Office: Days
• US Class Current: 33/1AP
• 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 objects that are located within the area of the first polygon;

determining a second amount of objects that are located within an area of a second polygon; and

estimating an overlap of the first polygon with the second polygon based on the first amount of objects and the second amount of objects.

2. The method recited in claim 1, wherein

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

the second amount is a number of objects that are located within an area of a second polygon

3. The method recited in claim 2, wherein the objects are points.

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

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

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

7. The method recited in claim 1, further comprising providing the pattern of objects by:

determining a dimension of the first polygon;

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.

8. The method recited in claim 1, wherein

the first polygon is a bounding area for content, and

the second polygon is a bounding area for a selection lasso.

9. The method recited in claim 1, wherein

the first polygon is a bounding area for a selection lasso;

and

the second polygon is a bounding area for content.

10. The method recited in claim 1, wherein the overlap is estimated to be equivalent to a ratio of the second number of objects to the first number of objects.

11. 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.

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

13. A tool for estimating overlap between polygons, comprising:

an object creation module that creates a pattern of objects within an entire area of a first polygon; and

a point analysis module that

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

determines a second number of the objects located within the area of the second polygon; and

estimates an overlap of the first polygon with the second polygon based on the first number of objects and the second number of objects.

14. The tool recited in claim 13, wherein the object creation module is a point creation module for creating a pattern of points.

15. The tool recited in claim 13, wherein the object creation module creates the pattern of objects as a fixed number of objects independent of the area of the first polygon.

16. The tool recited in claim 13, wherein the object creation module

determines a dimension of the first polygon;

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.

17. The tool recited in claim 13, wherein the overlap is estimated to be equivalent to a ratio of the second number of objects to the first number of objects.