Method for determining whether a point lies along a curve in a multidimensional space

• US 9,459,095 B2
• Filed: 11/12/2015
• Issued: 10/04/2016
• Est. Priority Date: 06/30/2014
• Status: Active Grant

• Current Assignee: YE Hub Armenia LLC
• Original Assignee: Yandex Europe AG (Yandex N.V.)
• Inventors: Korzunov, Anton Vasilyevich
• Primary Examiner(s): Satanovsky, Alexander
• Assistant Examiner(s): KUAN, JOHN CHUNYANG
• Application Number:
  US14/939,117
• Publication Number:
  US 20160076883A1
• Time in Patent Office: 327 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G01B 21/00 Measuring arrangements or details thereof, where the measuring technique is not covered by the other groups of this subclass, unspecified or not relevant
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06T 11/20 Drawing from basic elements, e.g. lines or circles
• CPC Class Codes: G06T 7/60 Analysis of geometric attributes
• CPC Class Codes: G06V 10/25 Determination of region of interest [ROI] or a volume of interest [VOI]
• CPC Class Codes: G06V 10/757 Matching configurations of points or features

Abstract

There is disclosed a computer-implemented method for determining whether a point lies along a first curve in a multidimensional space and program instructions executable for carrying out the method. The method comprises appreciating first curve coordinates defining each of a position and a form of the first curve in the multidimensional space; identifying regions of the multidimensional space each encompassing a respective portion of the first curve while generating a second curve approximating the first curve; and storing, in a non-transitory computer-readable medium, region coordinates of at least one of the regions; whereby an analysis of the region coordinates and point coordinates defining a position of the point in the multidimensional space is executable to provide to a user either an indication that the point lies along the first curve or an indication that the point does not lie along the first curve. Some implementations comprise executing said analysis and providing said indication.

Claims

1. A computer-implemented method for determining whether a point lies along a first curve in a multidimensional space, the method executable by a processor of an electronic device, the point and the first curve being presented on a display interface of the electronic device, the point on the display interface corresponding to a click from a user of the electronic device, the method comprising:

determining first curve coordinates defining each of a position and a form of the first curve generated in the multidimensional space and presented on the display interface;

based on the first curve coordinates, identifying regions of the multidimensional space each encompassing a respective portion of the first curve while generating a second curve approximating the first curve, the identifying the regions including;

identifying a first set of the regions while generating a first version of the second curve, the first version of the second curve being a first polygonal chain, and

identifying a second set of the regions while generating a second version of the second curve, the second version of the second curve being a second polygonal chain having more line segments than the first polygonal chain;

storing, in a non-transitory computer-readable medium, region coordinates of at least one of the regions;

analyzing the region coordinates and point coordinates defining a position of the point in the multidimensional space, the analyzing being configured for providing, on the display interface, one of;

an indication that the point lies along the first curve, the indication that the point lies along the first curve being an indication that the user has clicked on the first curve; and

an indication that the point does not lie along the first curve, the indication that the point does not lie along the first curve being an indication that the user has not clicked on the first curve.

2. The method of claim 1, wherein:

identifying the first set of the regions comprises determining that at least one member of the first set of the regions has a boundary distance greater than a threshold value; and

identifying the second set of the regions comprises determining that no member of the second set of the regions has a boundary distance greater than the threshold value.

3. The method of claim 1, wherein generating the second curve approximating the first curve comprises executing a Ramer-Douglas-Peucker algorithm.

4. The method of claim 1, further comprising:

determining the point coordinates defining the position of the point in the multidimensional space;

executing the analysis of the region coordinates and the point coordinates; and

providing, to a user of the electronic device, either the indication that the point lies along the first curve or the indication that the point does not lie along the first curve based on the analysis.

5. The method of claim 4, wherein providing either the indication that the point lies along the first curve or the indication that the point does not lie along the first curve based on the analysis of the point coordinates and the region coordinates comprises providing the indication that the point does not lie along the first curve after determining that the point lies inside none of the regions.

6. The method of claim 4, wherein providing either the indication that the point lies along the first curve or the indication that the point does not lie along the first curve based on the analysis of the point coordinates and the region coordinates comprises providing the indication that the point does not lie along the first curve after:

determining that the point lies inside a region being a member of a first set of the regions having been identified during generation of a first version of the second curve, the first version of the second curve being a first polygonal chain; and

determining that the point lies inside no region being a member of a second set of the regions having been identified during generation of a second version of the second curve, the second version of the second curve being a second polygonal chain having more line segments than the first polygonal chain.

7. The method of claim 4, wherein providing either the indication that the point lies along the first curve or the indication that the point does not lie along the first curve based on the analysis of the point coordinates and the region coordinates comprises providing the indication that the point lies along the first curve after:

determining that the point lies inside a region being one of the regions; and

determining that a boundary distance of the region is no greater than a threshold value, the boundary distance of the region being a shortest distance to a most distant point inside the region from a line approximating the respective portion of the first curve of the region.

8. The method of claim 4, wherein providing either the indication that the point lies along the first curve or the indication that the point does not lie along the first curve based on the analysis of the point coordinates and the region coordinates comprises providing the indication that the point does not lie along the first curve after:

determining that the point lies inside a region being a member of a first set of the regions having been identified during generation of a first version of the second curve, the first version of the second curve being a first polygonal chain, at least one member of the first set of the regions having a boundary distance greater than a threshold value; and

determining that the point lies inside no region being a member of a second set of the regions having been identified during generation of a second version of the second curve, the second version of the second curve being a second polygonal chain having more line segments than the first polygonal chain, no member of the second set of the regions having a boundary distance greater than the threshold value.

9. The method of claim 4, wherein provision of either the indication that the point lies along the first curve or the indication that the point does not lie along the first curve based on the analysis of the point coordinates and the region coordinates comprises provision of the indication that the point does not lie along the first curve after:

determination that the point lies inside a region being a member of a first set of the regions having been identified during generation of a first version of the second curve, the first version of the second curve being a first polygonal chain, at least one member of the first set of the regions having a boundary distance greater than a threshold value; and

determination that the point lies inside no region being a member of a second set of the regions having been identified during generation of a second version of the second curve, the second version of the second curve being a second polygonal chain having more line segments than the first polygonal chain, no member of the second set of the regions having a boundary distance greater than the threshold value.

10. The method of claim 1, wherein each one of the regions consists of all points no further than a boundary distance from a line approximating the respective portion of the first curve of the one of the regions, the boundary distance being a shortest distance from the line to a point most distant from the line on the respective portion of the first curve.

11. The method of claim 10, wherein the multidimensional space has only two dimensions, and each one of the regions is a respective area of the multidimensional space.

12. The method of claim 1, wherein the multidimensional space has only two dimensions, and each one of the regions is a respective area of the multidimensional space consisting of:

all points no further than a first boundary distance away from a first side of a line approximating the respective portion of the first curve of the one of the regions, the first boundary distance being a shortest distance away from the first side of the line to a point most distant from the first side of the line on the respective portion of the first curve; and

all points no further than a second boundary distance away from a second side of the line, the second boundary distance being a shortest distance away from the second side of the line to a point most distant from the second side of the line on the respective portion of the first curve.

13. A non-transitory computer-readable medium storing program instructions for determining whether a point lies along a first curve in a multidimensional space, the program instructions being executable by a processor of an electronic device, the point and the first curve being presented on a display interface of the electronic device, the point on the display interface corresponding to a click from a user of the electronic device, to effect:

determining first curve coordinates defining each of a position and a form of the first curve generated in the multidimensional space;

based on the first curve coordinates, identifying regions of the multidimensional space each encompassing a respective portion of the first curve while generating a second curve approximating the first curve, the identifying the regions including;

identifying a first set of the regions during generation of a first version of the second curve, the first version of the second curve being a first polygonal chain, and

identifying a second set of the regions during generation of a second version of the second curve, the second version of the second curve being a second polygonal chain having more line segments than the first polygonal chain;

storing, in a non-transitory computer-readable medium, of region coordinates of at least one of the regions; and

analyzing the region coordinates and point coordinates defining a position of the point in the multidimensional space, the analyzing being configured for providing, on the display interface, one of;

an indication that the point lies along the first curve, the indication that the point lies along the first curve being an indication that the user has clicked on the first curve; and

an indication that the point does not lie along the first curve, the indication that the point does not lie along the first curve being an indication that the user has not clicked on the first curve.

14. The medium of claim 13, wherein:

identification of the first set of the regions comprises determining that at least one member of the first set of the regions has a boundary distance greater than a threshold value; and

identification of the second set of the regions comprises determining that no member of the second set of the regions has a boundary distance greater than the threshold value.

15. The medium of claim 13, wherein generation of the second curve approximating the first curve comprises execution of a Ramer-Douglas-Peucker algorithm.

16. The medium of claim 13, the program instructions being further executable by the processor to effect:

determining the point coordinates defining the position of the point in the multidimensional space;

execution of the analysis of the region coordinates and the point coordinates; and

provision, to a user of the electronic device, of either the indication that the point lies along the first curve or the indication that the point does not lie along the first curve based on the analysis.

17. The medium of claim 16, wherein provision of either the indication that the point lies along the first curve or the indication that the point does not lie along the first curve based on the analysis of the point coordinates and the region coordinates comprises provision of the indication that the point does not lie along the first curve after determining that the point lies inside none of the regions.

18. The medium of claim 16, wherein provision of either the indication that the point lies along the first curve or the indication that the point does not lie along the first curve based on the analysis of the point coordinates and the region coordinates comprises provision of the indication that the point does not lie along the first curve after:

determination that the point lies inside a region being a member of a first set of the regions having been identified during generation of a first version of the second curve, the first version of the second curve being a first polygonal chain; and

determination that the point lies inside no region being a member of a second set of the regions having been identified during generation of a second version of the second curve, the second version of the second curve being a second polygonal chain having more line segments than the first polygonal chain.

19. The medium of claim 16, wherein provision of either the indication that the point lies along the first curve or the indication that the point does not lie along the first curve based on the analysis of the point coordinates and the region coordinates comprises provision of the indication that the point lies along the first curve after:

determination that the point lies inside a region being one of the regions; and

determination that a boundary distance of the region is no greater than a threshold value, the boundary distance of the region being a shortest distance to a most distant point inside the region from a line approximating the respective portion of the first curve of the region.

20. The medium of claim 13, wherein each one of the regions consists of all points no further than a boundary distance from a line approximating the respective portion of the first curve of the one of the regions, the boundary distance being a shortest distance from the line to a point most distant from the line on the respective portion of the first curve.

21. The medium of claim 20, wherein the multidimensional space has only two dimensions, and each one of the regions is a respective area of the multidimensional space.

22. The medium of claim 13, wherein the multidimensional space has only two dimensions, and each one of the regions is a respective area consisting of:

all points no further than a first boundary distance away from a first side of a line approximating the respective portion of the first curve of the one of the regions, the first boundary distance being a shortest distance away from the first side of the line to a point most distant from the first side of the line on the respective portion of the first curve; and

all points no further than a second boundary distance away from a second side of the line, the second boundary distance being a shortest distance away from the second side of the line to a point most distant from the second side of the line on the respective portion of the first curve.

23. A computer-implemented method for determining whether a point lies along a first curve in a multidimensional space, the method executable by a processor of an electronic device, the point and the first curve being presented on a display interface of the electronic device, the point on the display interface corresponding to a click from a user of the electronic device, the method comprising:

reading, from a non-transitory computer-readable medium, region coordinates of at least one of a plurality of regions of the multidimensional space each encompassing a respective portion of the first curve generated, the plurality of regions having been identified based on coordinates of the first curve during generation of a second curve approximating the first curve, the identification of the plurality of regions including;

identifying a first set of the regions while generating a first version of the second curve, the first version of the second curve being a first polygonal chain, and

identifying a second set of the regions while generating a second version of the second curve, the second version of the second curve being a second polygonal chain having more line segments than the first polygonal chain;

determining point coordinates defining a position of the point in the multidimensional space;

analyzing the region coordinates and the point coordinates; and

providing one of;

an indication that the point lies along the first curve, the indication that the point lies along the first curve being an indication that the user has clicked on the first curve; and

an indication that the point does not lie along the first curve based on the analysis, the indication that the point does not lie along the first curve being an indication that the user has not clicked on the first curve.

24. The method of claim 23, wherein the providing one of the indication that the point lies along the first curve or the indication that the point does not lie along the first curve further comprises presenting the indication on the display interface of the electronic device.

25. A non-transitory computer-readable medium storing program instructions for determining whether a point lies along a first curve in a multidimensional space, the program instructions being executable by a processor of an electronic device, the point and the first curve being presented on a display interface of the electronic device, the point on the display interface corresponding to a click from a user of the electronic device, to effect:

reading, from a memory of the electronic device, of region coordinates of at least one of a plurality of regions of the multidimensional space each encompassing a respective portion of the first curve generated, the plurality of regions having been identified based on coordinates of the first curve while generating a second curve approximating the first curve, the identification of the plurality of regions including;

identifying a first set of the regions while generating a first version of the second curve, the first version of the second curve being a first polygonal chain, and

identifying a second set of the regions while generating a second version of the second curve, the second version of the second curve being a second polygonal chain having more line segments than the first polygonal chain;

determining point coordinates defining a position of the point in the multidimensional space;

analyzing the region coordinates and the point coordinates; and

providing, on the display interface of the electronic device, based on the analysis, one of;

an indication that the point lies along the first curve, the indication that the point lies along the first curve being an indication that the user has clicked on the first curve; and

an indication that the point does not lie along the first curve, the indication that the point does not lie along the first curve being an indication that the user has not clicked on the first curve.