Matching two vector paths

Question

I have several vector paths and a query path and now I am trying to get the path which is most similar to the query path. I can access length(perimeter) of each path, and width and height of their bounding boxes. I am using python and using pyx library for rendering SVG paths and calculating their bounding boxes. Pseudo code looks like...

THRESHOLD = //some value
qpath = //my query path
similar_paths = []

for path in path_list:
    if (comparable width and comparable height and comparable perimeters):
        similar_paths.append(path)

But It does not seem to give nice results. Any ideas on how to improve the results?

Answer 1

Lets use a simple PyX graph to generate some paths:

The paths could also come from an SVG file read in parsed mode.

Once you have PyX paths, you can use PyX features to get further information about the paths. In the following simple version I calculate a few points along each path and the sum up their distance. (I do it using method names ending by _pt, which work in PostScript points. It is a little faster than using PyX units. Also I converted all paths to normpaths explicitely in the beginning. While this is not necessary, it helps reduces some function calls internally.)

Here is the full code (including the graph to generate the sample paths):

import math
from pyx import *

# create some data (and draw it)
g = graph.graphxy(width=10, x=graph.axis.lin(min=0, max=2*math.pi))
qpi = g.plot(graph.data.function("y(x)=sin(x)"))
opi1 = g.plot(graph.data.function("y(x)=sin(x)+0.1*sin(10*x)"))
opi2 = g.plot(graph.data.function("y(x)=sin(x)+0.2*sin(20*x)", points=1000))
g.writePDFfile()

# get the corresponding PyX paths
qpath = qpi.path.normpath()
opath1 = opi1.path.normpath()
opath2 = opi2.path.normpath()

# now analyse it
POINTS = 10

qpath_arclen_pt = qpath.arclen_pt()
qpath_points_pt = qpath.at_pt([qpath_arclen_pt*i/(POINTS-1) for i in range(POINTS)])

for opath in [opath1, opath2]:
    opath_arclen_pt = opath.arclen_pt()
    opath_points_pt = opath.at_pt([opath_arclen_pt*i/(POINTS-1) for i in range(POINTS)])
    print(sum(math.sqrt((qpoint_x_pt-opoint_x_pt)**2 + (qpoint_y_pt-opoint_y_pt)**2)
              for (qpoint_x_pt, qpoint_y_pt), (opoint_x_pt, opoint_y_pt) in zip(qpath_points_pt, opath_points_pt)))

The program just prints out:

25.381154890630064
56.44386644062556

which indicates, that the dashed lines is closer to the solid one than the dotted line.

You may also compare tangents, curvatures, the arclen itself etc. ... there are plenty of options depending on your needs.