def svg_path_to_polygons(path_data):
    """Return a list of polygons that collectively approximate the SVG path whose string is `path_data`.
    This handles just enough cases to parse the map files.
    Examples:
    >>> svg_path_to_polygons('m 10 20 30 40')
    [[(10.0, 20.0), (40.0, 60.0)]]
    >>> svg_path_to_polygons('m 10 20 30 40 z')
    [[(10.0, 20.0), (40.0, 60.0), (10.0, 20.0)]]
    >>> svg_path_to_polygons('m 10 20 30 40 z m 100 200 10 20')
    [[(10.0, 20.0), (40.0, 60.0), (10.0, 20.0)], [(110.0, 220.0), (120.0, 240.0)]]
    """

    # `svg.path` treats the Move command as though it were Line.
    # Split the path data, in order to collect one Path per contour.
    path_strings = [s for s in path_data.split('m') if s]
    path_prefix = 'm'

    polygons = []
    for path_string in path_strings:
        if path_string[0] not in 'M':
            path_string = path_prefix + path_string
        path = parse_path(path_string)
        polygons.append(path_to_points(path))
        end_pt = path[-1].end
        path_prefix = 'M %f,%f m' % (end_pt.real, end_pt.imag)

    return polygons

    def __init__(self, selected_element, extra_output_log):
        # The id is just an internal name for the element. Used currently for console output.
        self.id = selected_element.attrib['id']
        # The path is the geometric boundary of an electrode.
        self.path = parse_path(selected_element.attrib['d'])
        # All Patches share a common overall scaling, while each has a translation transformation also associated with
        # its relative position in the trap.  The combination of both is represented by the Patch's transform attribute.
        self.transform = get_matrix(parent_map[selected_element])
        # Boolean flag indicating that the Patch has been matched with an electrode identity.
        self.matched = False

        # Extract the style element and grab the stroke information with a regular expression search.
        style = selected_element.attrib['style']
        stroke_regex = r'stroke\s*:\s*#(?P<color>\w+)\s*;'
        stroke_match = re.search(stroke_regex, style)
        # The patch elements are either black ('000000') or blue ('0000ff') which indicates the height
        # of the electrode in the trap. Grab this information from the stroke info and set the height of the patch.
        self.color = stroke_match.group('color')
        # TODO: Figure out why the z value is set to -4.5. The svg is to scale, but I don't know what the scaling is.
        self.z = -4.5 if self.color == '0000ff' else 0.0

        if PRINT_EXTRA_OUTPUT:
            print('Creating patch for', self.id)
        if LOG_EXTRA_OUTPUT:
            extra_output_log.write('Creating patch for ' + self.id + '\n')

def addpathid(root, curr):
    if 'path' in curr.tag:
        if int(curr.attrib['structure_id']) == int(root['id']):
            
            #add/update path id attribute
            path_area = parse_path( curr.attrib["d"] ).area()
            slice_id = "p" + curr.getparent().getparent()[0].attrib["id"]

            if 'path_ids' in root:
                root['path_ids'].append(curr.attrib['id'])
                root['path_areas'].append(path_area)
                root['path_routes'].append(getpathroute(curr))
                root['slice_ids'].append(slice_id)
                root['ave_area'] = sum([a for a in root['path_areas']]) / len(root['path_ids'])
                root['volume'] += path_area
            else:
                root['path_ids'] = [curr.attrib['id']]
                root['path_routes'] = [getpathroute(curr)]
                root['path_areas'] = [path_area]
                root['slice_ids'] = [slice_id]
                root['ave_area'] = path_area
                root['volume'] = path_area


            root['largest_area'] = max( enumerate(root['path_areas']), key=lambda x: x[1] )

    for child in curr:
        addpathid(root, child)

 def read_svg(self,content, **kwargs):
     """appends svg content to drawing
     :param content: string, either filename or svg content
     """
     #from http://stackoverflow.com/questions/15857818/python-svg-parser
     from xml.dom import minidom
     try:
         doc = minidom.parse(content)  # parseString also exists
     except IOError:
         doc = minidom.parseString(content.encode('utf-8'))
         
     trans=Trans()
     trans.f=-1 #flip y axis
     for path in doc.getElementsByTagName('path'):
         #find the color... dirty, but simply understandable
         color=path.getAttribute('fill') #assign filling color to default stroke color
         alpha=1
         style=path.getAttribute('style')
         for s in style.split(';'):
             item=s.split(':')
             if item[0]=='opacity':
                 alpha=float(item[1])
             elif item[0]=='stroke':
                 color=item[1]
         if not color or alpha==0 : #ignore picture frame
             continue
         # process the path
         d=path.getAttribute('d')
         from svg.path import parse_path
         e=Entity.from_svg(parse_path(d),color)
         e=trans*e
         self.append(e)
     doc.unlink()
     return self

def get_points(path):
    path = parse_path(path)
    points = []
    for p in path:
        points.append([p.start.real, p.start.imag])
        points.append([p.end.real, p.end.imag])
    return points 

def computeLength(shape):
	if shape.tagName == 'path':
		path = parse_path(shape.getAttribute('d'));
		return path.length(); # this is by far is the program most costly instruction
	if shape.tagName == 'line':
		return hypot(float(shape.getAttribute('x2')) - float(shape.getAttribute('x1')),
		             float(shape.getAttribute('y2')) - float(shape.getAttribute('y1')));
	if shape.tagName == 'polyline':
		length = 0.0;
		points = _parsePoints(shape);
		px = py = None;
		for x,y in points:
			if px is not None:
				length += hypot(x-px, y-py);
			px, py = x, y;
		return length;
	if shape.tagName == 'polygon':
		length = 0.0;
		points = _parsePoints(shape);
		px = py = fx = fy = None;
		for x,y in points:
			if fx is None:
				fx, fy = x, y;
			if px is not None:
				length += hypot(x-px, y-py);
			px, py = x, y;
		length += hypot(fx-px, fy-py);
		return length;
	print("Unsupported shape \"%s\" will not be animated."%shape.tagName);

def main():
    lines = []
    while True:
        line = sys.stdin.readline()
        if line == '\n':
            break
        lines.append(line)
    path_strings = parse_svg("".join(lines))
    # print >> sys.stderr, path_strings

    points = []
    while True:
        line = sys.stdin.readline().strip()
        if not line:
            break
        x, y = line.split(',')
        points.append((float(x), float(y)))
    # print >> sys.stderr, points

    compound = parse_path(path_strings)
    # print >> sys.stderr, "compound", compound
    compound_segments = [((segment.start.real, segment.start.imag),
                          (segment.end.real, segment.end.imag))
                         for segment in compound]
    # print >> sys.stderr, "segments", compound_segments
    for p in points:
        if point_in_poly(p, compound_segments):
            print "true"
        else:
            print "false"

def initialize(svg_filename='Blank_US_Map.svg'):
    """Initialize the `states` global variable."""

    with open(svg_filename, 'r') as svg:
        soup = BeautifulSoup(svg.read(), selfClosingTags=['defs'])
        paths = soup.findAll('path')

    global states
    states = {}
    for p in paths:
        state_name = p.get('id', None)
        path_string = p.get('d', None)
        if not state_name or not path_string:
            continue
        # `svg.path` treats the Move command as though it were Line.
        # Split the path data, in order to collect one Path per contour.
        path_strings = [s for s in path_string.split('m') if s]
        polygons = []
        path_prefix = 'm'
        for path_string in path_strings:
            if path_string[0] not in 'M':
                path_string = path_prefix + path_string
            path = parse_path(path_string)
            polygons.append(path_to_points(path))
            end_pt = path[-1].end
            end_pt = path[0].start
            path_prefix = 'M %f,%f m' % (end_pt.real, end_pt.imag)
        states[state_name] = polygons

    states = OrderedDict(sorted(states.items()))

def Measurement():
	str_S1 = '<?xml version="1.0" encoding="UTF-8" standalone="no"?> <svg ' + 'xmlns="http://www.w3.org/2000/svg" ' + 'xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" width="600" height="500" viewBox="-50 0 500 500" > '
	str_S2 = '<path d = "'
	str_S3 = '" inkscape:connector-curvature="0" '+ 'style="fill:none;stroke:#000000;stroke-width:3" />' 
	str_S4 = '</svg>'

	doc = minidom.parse('temp.svg')  

	path_strings = [path.getAttribute('d') for path
                in doc.getElementsByTagName('path')]

	path1 = parse_path(path_strings[0])
	path2 = parse_path(path_strings[1])

	#print "Path1: "+str(path1)
	#print "Path2: "+str(path2)

	str_Text = gen_text(path1, path2)
	fin_svg = str(str_S1) + str ('\n') + str(str_S2) + str(path1.d()) + str ('\n') + str(str_S3) + str ('\n')  + str(str_S2) + str(path2.d()) + str(str_S3) + str(str_Text) + str(str_S4)
 	
	cursor = db.cursor()
	sql = "select count(*) from svg_table;"
	cursor.execute(sql)
	c = int(cursor.fetchone()[0])
 	i = c+1
	sql = "insert into svg_table (id, svg) values( " + str(i) + ", '" + fin_svg + "');"
	cursor.execute(sql)
	comma = str(", ")
	str_sql = "INSERT INTO `rear_table`(`ID`, `SPointX`, `SPointY`, `LegOpenX`, `LegOpenY`, `LegOpenLen`, `OutseamX`, `OutseamY`, `OutseamCPX`, `OutseamCPY`, `OutseamLen`, `WaistX`, `WaistY`, `WaistLen`, `BackriseX`, `BackriseY`, `BackriseCPX`, `BackriseCPY`, `BackriseLen`, `InseamX`, `InseamY`, `InseamCPX`, `InseamCPY`, `InseamLen`) VALUES (" 
	str_sql1 = str(i) + comma + str(path1[0].start.real) + comma + str(path1[0].start.imag) + comma + str(path1[0].end.real) + comma + str(path1[0].end.imag) + comma + str(path1[0].length()) + comma 
	str_sql2 = str(path1[1].end.real) + comma + str(path1[1].end.imag) + comma + str(path1[1].control.real) + comma + str(path1[1].control.imag) + comma + str(path1[1].length()) + comma				
	str_sql3 = str(path1[2].end.real) + comma + str(path1[2].end.imag) + comma + str(path1[2].length()) + comma
	str_sql4 = str(path1[3].end.real) + comma + str(path1[3].end.imag) + comma + str(path1[3].control.real) + comma + str(path1[3].control.imag) + comma + str(path1[3].length()) + comma
	str_sql5 = str(path1[4].end.real) + comma + str(path1[4].end.imag) + comma + str(path1[4].control.real) + comma + str(path1[4].control.imag) + comma + str(path1[4].length()) + str(');')
	sql = str_sql + str_sql1 + str_sql2+ str_sql3+ str_sql4+ str_sql5
	#print "sql string = ",sql
	cursor.execute(sql)
	str_sql = "INSERT INTO `front_table`(`ID`, `SPointX`, `SPointY`, `LegOpenX`, `LegOpenY`, `LegOpenLen`, `OutseamX`, `OutseamY`, `OutseamCPX`, `OutseamCPY`, `OutseamLen`, `WaistX`, `WaistY`, `WaistLen`, `FrontriseX`, `FrontriseY`, `FrontriseCPX`, `FrontriseCPY`, `FrontriseLen`, `InseamX`, `InseamY`, `InseamCPX`, `InseamCPY`, `InseamLen`) VALUES ("
	str_sql1 = str(i) + comma + str(path2[0].start.real) + comma + str(path2[0].start.imag) + comma + str(path2[0].end.real) + comma + str(path2[0].end.imag) + comma + str(path2[0].length()) + comma 
	str_sql2 = str(path2[1].end.real) + comma + str(path2[1].end.imag) + comma + str(path2[1].control.real) + comma + str(path2[1].control.imag) + comma + str(path2[1].length()) + comma				
	str_sql3 = str(path2[2].end.real) + comma + str(path2[2].end.imag) + comma + str(path2[2].length()) + comma
	str_sql4 = str(path2[3].end.real) + comma + str(path2[3].end.imag) + comma + str(path2[3].control.real) + comma + str(path2[3].control.imag) + comma + str(path2[3].length()) + comma
	str_sql5 = str(path2[4].end.real) + comma + str(path2[4].end.imag) + comma + str(path2[4].control.real) + comma + str(path2[4].control.imag) + comma + str(path2[4].length()) + str(');')
	sql = str_sql + str_sql1 + str_sql2+ str_sql3+ str_sql4+ str_sql5
	cursor.execute(sql)
	db.commit()
	print i

def path_delta_move(pat, delta):
    text = get_full_match(pat)
    match = pat.group(1)
    path = parse_path(match)
    for primitive in path:
        path_primitive_move(primitive, delta)
    new_d = path.d()
    return text.replace(match, new_d)

 def _getSVGPathsFromMinidom(self, pMinidom):
     paths = []
     for path in pMinidom.getElementsByTagName("path"):
         dAttributeOfPath = path.getAttribute('d')
         parsedPath = parse_path(dAttributeOfPath)
         paths.append(self._castMinidomParsedPath(parsedPath))
     if logger.isEnabledFor(logging.DEBUG):
         logger.debug("Parsed SVG paths are {}".format(paths))
     return paths

def parse_svg(filepath):
    doc = minidom.parse(filepath)
    paths = []
    ids = []
    for path in doc.getElementsByTagName('path'):
        ids.append(path.getAttribute('id'))
        parsed_path = parse_path(path.getAttribute('d'))
        paths.append(parsed_path)

    return np.array(ids), np.array(paths)

def filter_svg(svg_doc, paths):
    svg_root = svg_doc.getElementsByTagName('svg')[0]
    # copy only the root node
    new_svg = svg_root.cloneNode(False)
    for element in svg_doc.getElementsByTagName('path'):
        parsed_path = parse_path(element.getAttribute('d'))
        if parsed_path in paths:
            element.setAttribute('class', 'highlight')
            new_svg.appendChild(element)

    return new_svg

def build_lines(svgfile, line_length_threshold=10.0, min_points_per_path=1, max_points_per_path=3):
    # we don't draw lines less than line_length_threshold
    path_strings = get_path_strings(svgfile)

    lines = []

    for path_string in path_strings:
        try:
            full_path = parse_path(path_string)
        except:
            import pdb
            pdb.set_trace()
            print "e"
        for i in range(len(full_path)):
            p = full_path[i]
            if type(p) != Line and type(p) != CubicBezier:
                print "encountered an element that is not just a line or bezier "
                print "type: ", type(p)
                print p
            else:
                x_start = p.start.real
                y_start = p.start.imag
                x_end = p.end.real
                y_end = p.end.imag
                line_length = np.sqrt(
                    (x_end - x_start) * (x_end - x_start) + (y_end - y_start) * (y_end - y_start))
                # len_data.append(line_length)
                points = []
                if type(p) == CubicBezier:
                    x_con1 = p.control1.real
                    y_con1 = p.control1.imag
                    x_con2 = p.control2.real
                    y_con2 = p.control2.imag
                    n_points = int(line_length / line_length_threshold) + 1
                    n_points = max(n_points, min_points_per_path)
                    n_points = min(n_points, max_points_per_path)
                    points = cubicbezier(x_start, y_start, x_con1, y_con1, x_con2, y_con2, x_end, y_end,
                                         n_points)
                else:
                    points = [(x_start, y_start), (x_end, y_end)]
                if i == 0:  # only append the starting point for svg
                    lines.append([points[0][0], points[0][1], 0, 0])  # put eoc to be zero
                for j in range(1, len(points)):
                    eos = 0
                    if j == len(points) - 1 and i == len(full_path) - 1:
                        eos = 1
                    lines.append([points[j][0], points[j][1], eos, 0])  # put eoc to be zero
    lines = np.array(lines, dtype=np.float32)
    # make it relative moves
    lines[1:, 0:2] -= lines[0:-1, 0:2]
    lines[-1, 3] = 1  # end of character
    lines[0] = [0, 0, 0, 0]  # start at origin
    return lines[1:]

def svg_to_path(file_obj, file_type=None):
    def complex_to_float(values):
        return np.array([[i.real, i.imag] for i in values])

    def load_line(svg_line):
        points = complex_to_float([svg_line.point(0.0),
                                   svg_line.point(1.0)])
        if not starting: points[0] = vertices[-1]
        entities.append(Line(np.arange(2)+len(vertices)))
        vertices.extend(points)

    def load_arc(svg_arc):
        points = complex_to_float([svg_arc.start, 
                                   svg_arc.point(.5), 
                                   svg_arc.end])
        if not starting: points[0] = vertices[-1]
        entities.append(Arc(np.arange(3)+len(vertices)))
        vertices.extend(points)
    def load_quadratic(svg_quadratic):
        points = complex_to_float([svg_quadratic.start, 
                                   svg_quadratic.control, 
                                   svg_quadratic.end])
        if not starting: points[0] = vertices[-1]
        entities.append(Bezier(np.arange(3)+len(vertices)))
        vertices.extend(points)
    def load_cubic(svg_cubic):
        points = complex_to_float([svg_cubic.start, 
                                   svg_cubic.control1, 
                                   svg_cubic.control2, 
                                   svg_cubic.end])
        if not starting: points[0] = vertices[-1]
        entities.append(Bezier(np.arange(4)+len(vertices)))
        vertices.extend(points)
    
    # first, we grab all of the path strings from the xml file
    xml   = parse_xml(file_obj.read())
    paths = [p.attributes['d'].value for p in xml.getElementsByTagName('path')]

    entities = deque()
    vertices = deque()  
    loaders  = {'Arc'             : load_arc,
                'Line'            : load_line,
                'CubicBezier'     : load_cubic,
                'QuadraticBezier' : load_quadratic}

    for svg_string in paths:
        starting = True
        for svg_entity in parse_path(svg_string):
            loaders[svg_entity.__class__.__name__](svg_entity)
            #starting = False

    return {'entities' : np.array(entities),
            'vertices' : np.array(vertices)}

def parse_paths(paths, min_edge_size):
    segments = []
    index = 0
    for path in paths:
        index += 1
        print str(float(index) / len(paths) * 100) + ' %'
        if 'd' not in path.attributes.keys():
            raise Exception, 'There is no attribute "d" in path element'
        svg_path = parse_path(path.attributes['d'].value)
        common_attributes = extract_attributes(path)
        segments.append(tuple([svg_path_to_segment_list(svg_path, min_edge_size), common_attributes]))
    return segments

 def get_corners(self):
     transform = get_matrix( parent_map[self.element] )        
     corners = []
     for p in parse_path( self.element.attrib['d']):
         coords = np.matrix([ [1,0,p.start.real],[0,1,p.start.imag],[0,0,1] ])
         res = transform*coords
         if len(corners):
             dx = corners[-1][0] - res[0,2]
             dy = corners[-1][1] - res[1,2]
             if dx*dx + dy*dy < 0.01:
                 continue
         corners.append( (res[0,2], res[1,2]) )
     return corners

def get_path_from_svg(svg_path):
    n_pts = 100
    all_coords = []
    svg_image = minidom.parse(svg_path)
    path_strings = [path.getAttribute('d') for path in svg_image.getElementsByTagName('path')]
    for i in range(len(path_strings)):
        path_strings[i] = parse_path(str(path_strings[i]))
    svg_image.unlink()

    for current_path in path_strings:
        for element in current_path:
            all_coords.append(get_coords_from_shape(element))

    return all_coords

def get_svg_path(wc):
    config = get_config()
    svgd = get_absolute_path(config.get('KWS', 'locations'))
    svgs = glob(os.path.join(svgd, '*.svg'))
    dids = [os.path.basename(x).replace('.svg', '') for x in svgs]
    svgp = svgs[dids.index(wc.doc_id)]

    dom = minidom.parse(svgp)
    path = None
    for element in dom.getElementsByTagName('path'):
        if element.getAttribute('id') == wc.id:
            path = parse_path(element.getAttribute('d'))

    return path

def simplify_points(path_d):
    path = parse_path(path_d)

    for bezier in path:

        if isinstance(bezier, CubicBezier):
            for attr in ('start', 'control1', 'control2', 'end'):
                setattr(bezier, attr, gfc(getattr(bezier, attr)))

        elif isinstance(bezier, Line):
            for attr in ('start', 'end'):
                setattr(bezier, attr, gfc(getattr(bezier, attr)))

    return path