Systems, methods, and computer-readable media for fast neighborhood determinations in dynamic environments

• US 20060210172A1
• Filed: 03/17/2005
• Published: 09/21/2006
• Est. Priority Date: 03/17/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ye, Ming, Sutanto, Herry, Raghupathy, Sashi
• Granted Patent: US 7,522,771 B2
• Time in Patent Office: Days
• US Class Current: 382/229
• CPC Class Codes: G06V 30/347 Sampling; Contour coding; Stroke extraction

Abstract

Methods, systems, and computer-readable media for ascertaining neighborhood information in a dynamically changing environment, such as an electronic ink environment may include: (a) receiving data representing plural electronic ink strokes; (b) defining a first vertex associated with a first ink stroke; and (c) determining neighboring vertices to the first vertex, wherein the neighboring vertices are associated with ink stroke(s) other than the first ink stroke. Additional systems, methods, and computer-readable media may include: (a) receiving data representing plural electronic ink strokes; (b) defining plural vertices associated with the ink strokes; (c) receiving input indicating a selection of an ink component; and (d) determining at least one neighboring component by determining which ink component(s) located outside of the selection include one or more ink strokes having vertices that neighbor vertices included in the selection.

Claims

1. A method, comprising:

receiving data representing plural electronic ink strokes including at least a first electronic ink stroke;

defining at least a first vertex associated with the first electronic ink stroke; and

determining at least a first neighbor vertex to the first vertex, wherein the first neighbor vertex is associated with an electronic ink stroke other than the first electronic ink stroke.

2. A method according to claim 1, further comprising:

storing information identifying the first neighbor vertex and associating the first neighbor vertex with at least one of the first vertex or the first electronic ink stroke.

3. A method according to claim 1, wherein the first neighbor vertex is determined using triangulation.

4. A method according to claim 3, wherein the first neighbor vertex is determined using Delaunay triangulation.

5. A computer-readable medium including computer-executable instructions stored thereon for performing the method of claim 1.

6. A method, comprising:

receiving data representing plural electronic ink strokes, wherein at least some of the plural electronic ink strokes are grouped in a hierarchical manner to form a hierarchical association of plural electronic ink components;

for at least some of the plural electronic ink strokes, defining plural vertices associated with the respective electronic ink strokes;

receiving input data indicating a selection of at least one electronic ink component; and

determining at least one electronic ink component that neighbors the electronic ink component or components included in the selection by determining which electronic ink component or components located outside of the selection include one or more electronic ink strokes having one or more vertices that are neighbors to one or more vertices included in the selection.

7. A method according to claim 6, further comprising:

outputting information identifying the electronic ink component or components determined to neighbor the electronic ink component or components in the selection.

8. A method according to claim 6, wherein the determination as to which electronic ink component or components located outside of the selection include one or more electronic ink strokes having one or more vertices that are neighbors to one or more vertices included in the selection is made using triangulation.

9. A method according to claim 8, wherein the triangulation includes Delaunay triangulation.

10. A method according to claim 6, wherein the hierarchical association of the plural electronic ink components includes plural electronic ink strokes grouped into plural electronic ink words and plural electronic ink words grouped into at least one of electronic ink lines or electronic ink paragraphs.

11. A method according to claim 10, wherein the selection includes at least one electronic ink word, and the determining includes determining which electronic ink word or words located outside of the selection include one or more electronic ink strokes having one or more vertices that are neighbors to one or more vertices included in the electronic ink word or words in the selection.

12. A method according to claim 10, wherein the hierarchical association includes the plural electronic ink words grouped into plural electronic ink lines, wherein the selection includes a first electronic ink line, and the determining includes determining which electronic ink line or lines located outside of the selection include one or more electronic ink strokes having one or more vertices that are neighbors to one or more vertices included in the first electronic ink line.

13. A computer-readable medium including computer-executable instructions stored thereon for performing the method according to claim 6.

14. A system, comprising:

an input system for receiving input data representing plural electronic ink strokes including at least a first electronic ink stroke; and

a processing system programmed and adapted to;

(a) define at least a first vertex associated with the first electronic ink stroke, and (b) determine at least a first neighbor vertex to the first vertex, wherein the first neighbor vertex is associated with an electronic ink stroke other than the first electronic ink stroke.

15. A system according to claim 14, further comprising:

a storage system for storing information identifying the first neighbor vertex and associating the first neighbor vertex with at least one of the first vertex or the first electronic ink stroke.

16. A system according to claim 14, wherein the first neighbor vertex is determined using triangulation.

17. A system according to claim 14, wherein the processing system further is programmed and adapted to group at least some of the plural electronic ink strokes in a hierarchical manner to form a hierarchical association of plural electronic ink components;

wherein, for at least some of the plural electronic ink strokes, the processing system is programmed and adapted to define plural vertices associated with the respective electronic ink strokes;

wherein the input system is further for receiving input data indicating a selection of at least one electronic ink component; and

wherein the processing system further is programmed and adapted to determine at least one electronic ink component that neighbors the electronic ink component or components included in the selection by determining which electronic ink component or components located outside of the selection include one or more electronic ink strokes having one or more vertices that are neighbors to one or more vertices included in the selection.

18. A system according to claim 17, wherein the processing system further is programmed and adapted to output information identifying the electronic ink component or components determined to neighbor the electronic ink component or components in the selection.

19. A system according to claim 17, wherein the hierarchical association of the plural electronic ink components includes plural electronic ink strokes grouped into plural electronic ink words and plural electronic ink words grouped into at least one of electronic ink lines or electronic ink paragraphs.

20. A system according to claim 19, wherein the selection includes at least one electronic ink word, and the processing system is programmed and adapted to determine which electronic ink word or words located outside of the selection include one or more electronic ink strokes having one or more vertices that are neighbors to one or more vertices included in the electronic ink word or words in the selection.