FindMatch

Find Match tries to match the last path selected against all the path in the document.

The algorithm first checks that the number of node points are the same. Then checks that the node commands match. If the commands match it will then do a correlation against the point positions. This allows the match to catch even those paths that have been scaled, rotated or flipped. The correlation threshold allows the match to be tuned. A 1.0 will match only those paths that haven't been transformed. There is also a check box to match on color or not.

Please leave comments and suggestions.

The Find Match inx file

---

<inkscape-extension>
  <_name>Find Match</_name>
  <id>org.find_match</id>
  <dependency type="executable" location="extensions">findmatch.py</dependency>
  <dependency type="executable" location="extensions">inkex.py</dependency>
  <param name="foundLayer" type="string" _gui-text="Name of layer to put found objects on?">Found</param>
  <param name="threshold" type="float" min="0.0" max="1.0" _gui-text="Correlation Threshold">0.8</param>
  <param name="matchcolor"    type="boolean" _gui-text="Colors should match">true</param>
  <effect>
    <object-type>all</object-type>
    <effects-menu>
       <submenu _name="Examples"/>
    </effects-menu>
  </effect>
  <script>
    <command reldir="extensions" interpreter="python">findmatch.py</command>
  </script>
</inkscape-extension>

---

The python file for Find Match

---

#!/usr/bin/env python

'''
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
'''
import sys
sys.path.append('/usr/share/inkscape/extensions')

# We will use the inkex module with the predefined Effect base class.
import inkex
from simplestyle import *
from simplepath import *
from math import sqrt

color_props_fill=('fill:','stop-color:','flood-color:','lighting-color:')
color_props_stroke=('stroke:',)
color_props = color_props_fill + color_props_stroke


def correlation(xList,yList):
    #print yList
    n = len(xList)
    sumX = 0
    sumXX = 0
    sumY = 0
    sumYY = 0
    sumXY = 0
    for i in range(0,n):
    	X = xList[i]
        sumX += X
        sumXX += X*X
        Y = yList[i]
        sumY += Y
        sumYY += Y*Y
        sumXY += X*Y
    corrnum = (n * sumXY)-(sumX * sumY)
    corrden = sqrt( (n * sumXX) - (sumX * sumX) ) * sqrt( (n * sumYY) - (sumY * sumY) )
    corr = corrnum/corrden
    return corr

def pathMatch(rPath,cPath):
    n = len(rPath)
    for i in range(0,n):
        rNode = rPath[i]
        cNode = cPath[i]
        [rCmd,rPoints] = rNode
        [cCmd,cPoints] = cNode
        if rCmd != cCmd:
            #print "not match"
            return 0
    #print "Command Match"
    return 1
    
def pathPullPoints(rPath,cPath):
    n = len(rPath)
    rPointList = []
    cPointList = []
    for i in range(0,n):
        rNode = rPath[i]
        cNode = cPath[i]
        [rCmd,rPoints] = rNode
        [cCmd,cPoints] = cNode
        rPointList.extend(rPoints)
        cPointList.extend(cPoints)
    return [rPointList,cPointList]


def getLayer(svg, layerName):
    for g in svg.xpath('//svg:g', namespaces=inkex.NSS):
        if (g.get(inkex.addNS('groupmode', 'inkscape')) == 'layer'
            and (g.get(inkex.addNS('label', 'inkscape'))
            == layerName)):
            return g
    # Create a new layer.
    newLayer = inkex.etree.SubElement(svg, 'g')
    newLayer.set(inkex.addNS('label', 'inkscape'), layerName)
    newLayer.set(inkex.addNS('groupmode', 'inkscape'), 'layer')
    return newLayer

def compareColors(refNode, compNode):
    pass

def getColor(node):
    col = {}
    if node.attrib.has_key('style'):
        style=node.get('style') # fixme: this will break for presentation attributes!
        if style!='':
            #inkex.debug('old style:'+style)
            styles=style.split(';')
            for i in range(len(styles)):
                for c in range(len(color_props)):
                    if styles[i].startswith(color_props[c]):
                        #print "col num %d" % c
                        #print styles[i][len(color_props[c]):]
                        col[c] =  styles[i][len(color_props[c]):]
    return col
    
def colorMatch(rNode,cNode):
    rCol = getColor(rNode)
    #print rCol
    cCol = getColor(cNode)
    #print cCol
    if (rCol == cCol):
        return 1
    return 0



class FindMatch(inkex.Effect):
    """
    Inkscape effect extension.
    Searches for paths that match and places them on the named layer.
    """
    def __init__(self):
        """
        Constructor.
        Defines the "--what" option of a script.
        """
        # Call the base class constructor.
        inkex.Effect.__init__(self)
          
        self.OptionParser.add_option('-f', '--foundLayer', action = 'store',
          type = 'string', dest = 'foundLayer', default = 'Found',
          help = 'Name of layer to put found objects on?')

        self.OptionParser.add_option("-t", "--threshold",
                        action="store", type="float", 
                        dest="threshold", default = 0.8,
                        help="threshold for correlation match")
        self.OptionParser.add_option("--matchcolor",
                        action="store", type="inkbool", 
                        dest="matchcolor", default=True,
                        help="If True, colors will be matched") 
                        


    def effect(self):
        """
        Effect behaviour.
        Search for all paths that match the selected path
        """
        foundLayer = self.options.foundLayer
        matchcolor = self.options.matchcolor

        # Get access to main SVG document element 
        svg = self.document.getroot()
        
        # get the layer where the found paths will be moved to
        layer = getLayer(svg, foundLayer)
        
        # get a list of all path nodes
        pathNodes = self.document.xpath('//svg:path',namespaces=inkex.NSS)

        # setup stderr so that we can print to it for debugging        
        saveout = sys.stdout
       
        sys.stdout = sys.stderr
        
        rPathLen = 0
        rPathList = []
        rPathNode = None
        
        if len(self.selected) == 0:
            print "Nothing Selected"
            sys.stdout = saveout
            return
        
        for id, node in self.selected.iteritems():
            #print dir(node)
            if node.tag == inkex.addNS('path','svg'):
                #print node.attrib['d']
                rPathList = parsePath(node.attrib['d'])
                rPathLen = len(rPathList)
                rPathNode = node
                #print rPathLen
                #print rPathList

        
        for cPathNode in pathNodes:
            cPathList = parsePath(cPathNode.attrib['d'])
            cPathLen = len(cPathList)
            #print cPathLen
            #print cPathList
            if rPathLen == cPathLen:
                #print " Found %d in %s" % (rPathLen,cPathNode)
                
                #print matchcolor
                colorMatchFlag = (colorMatch(rPathNode,cPathNode) == 1) or not matchcolor
                pathMatchFlag = pathMatch(rPathList,cPathList)==1
                
                if pathMatchFlag and colorMatchFlag:
                    [rList,cList] = pathPullPoints(rPathList,cPathList)
                    corVal = correlation(rList,cList)
                    #print "The correlation was %g" % corVal
                    if (corVal > 0.80):
                        layer.append(cPathNode)
        
        
        
        
        #print 
        #print 'This message will be logged instead of displayed'
        sys.stdout = saveout 



# Create effect instance and apply it.
effect = FindMatch()
effect.affect()

Comments

I can't say it really works for me:

Unknown option: --
usage: python [option] ... [-c cmd | -m mod | file | -] [arg] ...
Try `python -h' for more information.

I also had to fix extension namespace for trunk. Basically, the first line was replaced with

<?xml version="1.0" encoding="UTF-8"?>
<inkscape-extension xmlns="http://www.inkscape.org/namespace/inkscape/extension">

--Prokoudine 23:51, 7 January 2009 (UTC)