Method and apparatus for automated real-time detection of overlapping painted markup elements

• US 9,367,938 B2
• Filed: 02/28/2013
• Issued: 06/14/2016
• Est. Priority Date: 02/28/2013
• Status: Active Grant

• Current Assignee: Nokia Technologies Oy (Nokia Corporation)
• Original Assignee: Nokia Technologies Oy (Nokia Corporation)
• Inventors: Brenzel, Aaron, Sernatinger, Paul, Werwath, James
• Primary Examiner(s): Baderman, Scott
• Assistant Examiner(s): Velez-Lopez, Mario M
• Application Number:
  US13/780,843
• Publication Number:
  US 20140245127A1
• Time in Patent Office: 1,202 Days
• US Class Current: 1/1
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text

Abstract

Various methods are provided for automated real-time detection of overlapping painted html elements.

Claims

1. A method comprising:

loading a spatial tree with one or more elements specified by a web source,

wherein loading includes determining node placement in accordance with a Hilbert Curve and assigning each of one or more elements to a node in the spatial tree; and

identifying an overlap of elements by searching the spatial tree using a plurality of points, the plurality of points representing specified points of the one or more elements, wherein, when the search returns more than one element, an overlap is determined to exist.

2. The method of claim 1, wherein the spatial tree is a packed Hilbert R-Tree.

3. The method of claim 1, wherein the one or more elements are specified by a markup language of a webpage.

4. The method of claim 1 further comprising configuring a default search mode as an exhaustive search.

5. The method of claim 1 further comprising configuring the spatial tree to accept point queries.

6. The method of claim 1, wherein the specified points of each of the one or more elements is dependent on a shape of the element.

7. The method of claim 6, further comprising determining the specified points of the one or more elements, wherein, in an instance when an element is a rectangle, the specified points are the vertices of the rectangle, wherein in an instance when the element is a line, the specified points are resulting endpoints obtained by dividing the line into a plurality of segments, and wherein in an instance when the element is a circle, the specified points are obtained utilizing a center point and a radius of the circle.

8. An apparatus comprising at least one processor and at least one memory including computer program code, the at least one memory and the computer program code configured to, with the processor, cause the apparatus to at least:

load a spatial tree with one or more elements specified by a web source,

wherein loading includes determining node placement in accordance with a Hilbert Curve and assigning each of one or more elements to a node in the spatial tree; and

identify an overlap of elements by searching the spatial tree using a plurality of points, the plurality of points representing specified points of the one or more elements, wherein, when the search returns more than one element, an overlap is determined to exist.

9. An apparatus according to claim 8, wherein the spatial tree is a packed Hilbert R-Tree.

10. An apparatus according to claim 8, wherein the one or more elements are specified by a markup language of a webpage.

11. An apparatus according to claim 8, wherein the at least one memory and the computer program code are further configured to, with the processor, cause the apparatus to configure a default search mode as an exhaustive search.

12. An apparatus according to claim 8, wherein the at least one memory and the computer program code are further configured to, with the processor, cause the apparatus to configure the packed Hilbert R-Tree to accept point queries.

13. An apparatus according to claim 8, wherein the specified points of each of the one or more elements is dependent on a shape of the element.

14. An apparatus according to claim 13, wherein the at least one memory and the computer program code are further configured to, with the processor, cause the apparatus to:

determine the specified points of the one or more elements, wherein, in an instance when an element is a rectangle, the specified points are the vertices of the rectangle, wherein in an instance when the element is a line, the specified points are resulting endpoints obtained by dividing the line into a plurality of segments, and wherein in an instance when the element is a circle, the specified points are obtained utilizing a center point and a radius of the circle.

15. A computer program product comprising at least one non-transitory computer-readable storage medium having computer-executable program code portions stored therein, the computer-executable program code portions comprising program code instructions for:

loading a spatial tree with one or more elements specified by a web source,

wherein loading includes determining node placement in accordance with a Hilbert Curve and assigning each of one or more elements to a node in the spatial tree; and

identifying an overlap of elements by searching the spatial tree using a plurality of points, the plurality of points representing specified points of the one or more elements, wherein, when the search returns more than one element, an overlap is determined to exist.

16. A computer program product according to claim 15, wherein the spatial tree is a packed Hilbert R-Tree.

17. A computer program product according to claim 15, wherein the one or more elements are specified by a markup language of a webpage.

18. A computer program product according to claim 15, wherein the computer-executable program code portions further comprise program code instructions for:

configuring a default search mode as an exhaustive search.

19. A computer program product according to claim 15, wherein the computer-executable program code portions further comprise program code instructions for configuring the packed Hilbert R-Tree to accept point queries.

20. A computer program product according to claim 15, wherein the specified points of each of the one or more elements is dependent on a shape of the element.

21. A computer program product according to claim 16, wherein the computer-executable program code portions further comprise program code instructions for:

determining the specified points of the one or more elements, wherein, in an instance when an element is a rectangle, the specified points are the vertices of the rectangle, wherein in an instance when the element is a line, the specified points are resulting endpoints obtained by dividing the line into a plurality of segments, and wherein in an instance when the element is a circle, the specified points are obtained utilizing a center point and a radius of the circle.