def _compute_convex_hull(self):
        """Extract the convex hull from the triangulation information.

        The output will be a list of point_id's in counter-clockwise order
        forming the convex hull of the data set.
        """
        border = (self.triangle_neighbors == -1)

        edges = {}
        edges.update(dict(zip(self.triangle_nodes[border[:, 0]][:, 1],
                               self.triangle_nodes[border[:, 0]][:, 2])))
        edges.update(dict(zip(self.triangle_nodes[border[:, 1]][:, 2],
                               self.triangle_nodes[border[:, 1]][:, 0])))
        edges.update(dict(zip(self.triangle_nodes[border[:, 2]][:, 0],
                               self.triangle_nodes[border[:, 2]][:, 1])))

        # Take an arbitrary starting point and its subsequent node
        hull = list(edges.popitem())
        while edges:
            hull.append(edges.pop(hull[-1]))

        # hull[-1] == hull[0], so remove hull[-1]
        hull.pop()

        return hull

    def add_lines(self, levels, colors, linewidths, erase=True):
        '''
        Draw lines on the colorbar.

        *colors* and *linewidths* must be scalars or
        sequences the same length as *levels*.

        Set *erase* to False to add lines without first
        removing any previously added lines.
        '''
        y = self._locate(levels)
        igood = (y < 1.001) & (y > -0.001)
        y = y[igood]
        if cbook.iterable(colors):
            colors = np.asarray(colors)[igood]
        if cbook.iterable(linewidths):
            linewidths = np.asarray(linewidths)[igood]
        N = len(y)
        x = np.array([0.0, 1.0])
        X, Y = np.meshgrid(x, y)
        if self.orientation == 'vertical':
            xy = [list(zip(X[i], Y[i])) for i in xrange(N)]
        else:
            xy = [list(zip(Y[i], X[i])) for i in xrange(N)]
        col = collections.LineCollection(xy, linewidths=linewidths)

        if erase and self.lines:
            for lc in self.lines:
                lc.remove()
            self.lines = []
        self.lines.append(col)
        col.set_color(colors)
        self.ax.add_collection(col)
        self.stale = True

 def do_3d_projection(self, renderer):
     s = self._segment3d
     xs, ys, zs = list(zip(*s))
     vxs, vys,vzs, vis = proj3d.proj_transform_clip(xs, ys, zs, renderer.M)
     self._path2d = mpath.Path(list(zip(vxs, vys)), self._code3d)
     # FIXME: coloring
     self._facecolor2d = self._facecolor3d
     return min(vzs)

    def get_grid_positions(self, fig):
        """
        return lists of bottom and top position of rows, left and
        right positions of columns.
        """
        nrows, ncols = self.get_geometry()

        subplot_params = self.get_subplot_params(fig)
        left = subplot_params.left
        right = subplot_params.right
        bottom = subplot_params.bottom
        top = subplot_params.top
        wspace = subplot_params.wspace
        hspace = subplot_params.hspace
        totWidth = right-left
        totHeight = top-bottom

        # calculate accumulated heights of columns
        cellH = totHeight/(nrows + hspace*(nrows-1))
        sepH = hspace*cellH

        if self._row_height_ratios is not None:
            netHeight = cellH * nrows
            tr = float(sum(self._row_height_ratios))
            cellHeights = [netHeight*r/tr for r in self._row_height_ratios]
        else:
            cellHeights = [cellH] * nrows

        sepHeights = [0] + ([sepH] * (nrows-1))
        cellHs = np.add.accumulate(np.ravel(list(zip(sepHeights, cellHeights))))


        # calculate accumulated widths of rows
        cellW = totWidth/(ncols + wspace*(ncols-1))
        sepW = wspace*cellW

        if self._col_width_ratios is not None:
            netWidth = cellW * ncols
            tr = float(sum(self._col_width_ratios))
            cellWidths = [netWidth*r/tr for r in self._col_width_ratios]
        else:
            cellWidths = [cellW] * ncols

        sepWidths = [0] + ([sepW] * (ncols-1))
        cellWs = np.add.accumulate(np.ravel(list(zip(sepWidths, cellWidths))))



        figTops = [top - cellHs[2*rowNum] for rowNum in range(nrows)]
        figBottoms = [top - cellHs[2*rowNum+1] for rowNum in range(nrows)]
        figLefts = [left + cellWs[2*colNum] for colNum in range(ncols)]
        figRights = [left + cellWs[2*colNum+1] for colNum in range(ncols)]


        return figBottoms, figTops, figLefts, figRights

 def _edges(self, X, Y):
     '''
     Return the separator line segments; helper for _add_solids.
     '''
     N = X.shape[0]
     # Using the non-array form of these line segments is much
     # simpler than making them into arrays.
     if self.orientation == 'vertical':
         return [list(zip(X[i], Y[i])) for i in xrange(1, N - 1)]
     else:
         return [list(zip(Y[i], X[i])) for i in xrange(1, N - 1)]

    def get_glyphs_with_font(self, font, s, glyph_map=None,
                             return_new_glyphs_only=False):
        """
        convert the string *s* to vertices and codes using the
        provided ttf font.
        """

        # Mostly copied from backend_svg.py.

        lastgind = None

        currx = 0
        xpositions = []
        glyph_ids = []

        if glyph_map is None:
            glyph_map = dict()

        if return_new_glyphs_only:
            glyph_map_new = OrderedDict()
        else:
            glyph_map_new = glyph_map

        # I'm not sure if I get kernings right. Needs to be verified. -JJL

        for c in s:
            ccode = ord(c)
            gind = font.get_char_index(ccode)
            if gind is None:
                ccode = ord('?')
                gind = 0

            if lastgind is not None:
                kern = font.get_kerning(lastgind, gind, KERNING_DEFAULT)
            else:
                kern = 0

            glyph = font.load_char(ccode, flags=LOAD_NO_HINTING)
            horiz_advance = (glyph.linearHoriAdvance / 65536.0)

            char_id = self._get_char_id(font, ccode)
            if char_id not in glyph_map:
                glyph_map_new[char_id] = self.glyph_to_path(font)

            currx += (kern / 64.0)

            xpositions.append(currx)
            glyph_ids.append(char_id)

            currx += horiz_advance

            lastgind = gind

        ypositions = [0] * len(xpositions)
        sizes = [1.] * len(xpositions)

        rects = []

        return (list(zip(glyph_ids, xpositions, ypositions, sizes)),
                     glyph_map_new, rects)

 def f():
     for (xy, a), l in zip(
         self.grid_info[lon_or_lat]["tick_locs"][axis_side],
         self.grid_info[lon_or_lat]["tick_labels"][axis_side],
     ):
         angle_normal = a
         yield xy, angle_normal, angle_tangent, ""

            def __call__(self, column):
                ind = []
                dsu = []
                for rownum, thisiter in enumerate(self.parent.iters):
                    val = model.get_value(thisiter, self.i)
                    try: val = float(val.strip().rstrip('%'))
                    except ValueError: pass
                    if mlab.safe_isnan(val): val = npy.inf # force nan to sort uniquely
                    dsu.append((val, rownum))
                dsu.sort()
                if not self.num%2: dsu.reverse()

                vals, otherind = list(zip(*dsu))
                ind.extend(otherind)

                self.parent.model.reorder(ind)
                newiters = []
                for i in ind:
                    newiters.append(self.parent.iters[i])
                self.parent.iters = newiters[:]
                for i, thisiter in enumerate(self.parent.iters):
                    key = tuple([self.parent.model.get_value(thisiter, j) for j in range(len(colheaders))])
                    self.parent.rownumd[i] = key

                self.num+=1

    def set_3d_properties(self, verts, zs=0, zdir='z'):
        if not iterable(zs):
            zs = np.ones(len(verts)) * zs

        self._segment3d = [juggle_axes(x, y, z, zdir) \
                for ((x, y), z) in zip(verts, zs)]
        self._facecolor3d = Patch.get_facecolor(self)

    def get_line(self, axes):
        self.update_lim(axes)
        x, y = self.grid_info["line_xy"]

        if self._get_line_path is None:
            return Path(list(zip(x, y)))
        else:
            return self._get_line_path(axes, x, y)

    def add_lines(self, levels, colors, linewidths):
        '''
        Draw lines on the colorbar. It deletes preexisting lines.
        '''
        del self.lines

        N = len(levels)
        x = np.array([1.0, 2.0])
        X, Y = np.meshgrid(x,levels)
        if self.orientation == 'vertical':
            xy = [list(zip(X[i], Y[i])) for i in xrange(N)]
        else:
            xy = [list(zip(Y[i], X[i])) for i in xrange(N)]
        col = collections.LineCollection(xy, linewidths=linewidths,
                                         )
        self.lines = col
        col.set_color(colors)
        self.ax.add_collection(col)

    def get_line(self, axes):

        self.update_lim(axes)
        from matplotlib.path import Path
        k, v = dict(left=("lon_lines0", 0),
                    right=("lon_lines0", 1),
                    bottom=("lat_lines0", 0),
                    top=("lat_lines0", 1))[self._side]

        xx, yy = self.grid_info[k][v]
        return Path(list(zip(xx, yy)))

    def _arc(self, quadrant=0, cw=True, radius=1, center=(0, 0)):
        """
        Return the codes and vertices for a rotated, scaled, and translated
        90 degree arc.

        Optional keyword arguments:

          ===============   ==========================================
          Keyword           Description
          ===============   ==========================================
          *quadrant*        uses 0-based indexing (0, 1, 2, or 3)
          *cw*              if True, clockwise
          *center*          (x, y) tuple of the arc's center
          ===============   ==========================================
        """
        # Note:  It would be possible to use matplotlib's transforms to rotate,
        # scale, and translate the arc, but since the angles are discrete,
        # it's just as easy and maybe more efficient to do it here.
        ARC_CODES = [Path.LINETO,
                     Path.CURVE4,
                     Path.CURVE4,
                     Path.CURVE4,
                     Path.CURVE4,
                     Path.CURVE4,
                     Path.CURVE4]
        # Vertices of a cubic Bezier curve approximating a 90 deg arc
        # These can be determined by Path.arc(0,90).
        ARC_VERTICES = np.array([[1.00000000e+00, 0.00000000e+00],
                                 [1.00000000e+00, 2.65114773e-01],
                                 [8.94571235e-01, 5.19642327e-01],
                                 [7.07106781e-01, 7.07106781e-01],
                                 [5.19642327e-01, 8.94571235e-01],
                                 [2.65114773e-01, 1.00000000e+00],
                                 # Insignificant
                                 # [6.12303177e-17, 1.00000000e+00]])
                                 [0.00000000e+00, 1.00000000e+00]])
        if quadrant == 0 or quadrant == 2:
            if cw:
                vertices = ARC_VERTICES
            else:
                vertices = ARC_VERTICES[:, ::-1]  # Swap x and y.
        elif quadrant == 1 or quadrant == 3:
            # Negate x.
            if cw:
                # Swap x and y.
                vertices = np.column_stack((-ARC_VERTICES[:, 1],
                                             ARC_VERTICES[:, 0]))
            else:
                vertices = np.column_stack((-ARC_VERTICES[:, 0],
                                             ARC_VERTICES[:, 1]))
        if quadrant > 1:
            radius = -radius  # Rotate 180 deg.
        return list(zip(ARC_CODES, radius * vertices +
                        np.tile(center, (ARC_VERTICES.shape[0], 1))))

    def create_artists(self, legend, orig_handle,
                       xdescent, ydescent, width, height, fontsize,
                       trans):

        markerline, stemlines, baseline = orig_handle

        xdata, xdata_marker = self.get_xdata(legend, xdescent, ydescent,
                                             width, height, fontsize)

        ydata = self.get_ydata(legend, xdescent, ydescent,
                               width, height, fontsize)

        if self._bottom is None:
            bottom = 0.
        else:
            bottom = self._bottom

        leg_markerline = Line2D(xdata_marker, ydata[:len(xdata_marker)])
        self.update_prop(leg_markerline, markerline, legend)

        leg_stemlines = []
        for thisx, thisy in zip(xdata_marker, ydata):
            l = Line2D([thisx, thisx], [bottom, thisy])
            leg_stemlines.append(l)

        for lm, m in zip(leg_stemlines, stemlines):
            self.update_prop(lm, m, legend)

        leg_baseline = Line2D([np.amin(xdata), np.amax(xdata)],
                              [bottom, bottom])

        self.update_prop(leg_baseline, baseline, legend)

        artists = [leg_markerline]
        artists.extend(leg_stemlines)
        artists.append(leg_baseline)

        for artist in artists:
            artist.set_transform(trans)

        return artists

def path_to_3d_segment(path, zs=0, zdir='z'):
    '''Convert a path to a 3D segment.'''

    if not iterable(zs):
        zs = np.ones(len(path)) * zs

    seg = []
    pathsegs = path.iter_segments(simplify=False, curves=False)
    for (((x, y), code), z) in zip(pathsegs, zs):
        seg.append((x, y, z))
    seg3d = [juggle_axes(x, y, z, zdir) for (x, y, z) in seg]
    return seg3d

def paths_to_3d_segments(paths, zs=0, zdir='z'):
    '''
    Convert paths from a collection object to 3D segments.
    '''

    if not iterable(zs):
        zs = np.ones(len(paths)) * zs

    segments = []
    for path, pathz in zip(paths, zs):
        segments.append(path_to_3d_segment(path, pathz, zdir))
    return segments

def zalpha(colors, zs):
    """Modify the alphas of the color list according to depth"""
    # FIXME: This only works well if the points for *zs* are well-spaced
    #        in all three dimensions. Otherwise, at certain orientations,
    #        the min and max zs are very close together.
    #        Should really normalize against the viewing depth.
    colors = get_colors(colors, len(zs))
    if zs.size > 0 :
        norm = Normalize(min(zs), max(zs))
        sats = 1 - norm(zs) * 0.7
        colors = [(c[0], c[1], c[2], c[3] * s) for c, s in zip(colors, sats)]
    return colors

    def create_artists(self, legend, orig_handle, xdescent, ydescent, width, height, fontsize, trans):
        xdata, xdata_marker = self.get_xdata(legend, xdescent, ydescent, width, height, fontsize)

        ydata = self.get_ydata(legend, xdescent, ydescent, width, height, fontsize)

        sizes = self.get_sizes(legend, orig_handle, xdescent, ydescent, width, height, fontsize)

        p = self.create_collection(orig_handle, sizes, offsets=list(zip(xdata_marker, ydata)), transOffset=trans)

        self.update_prop(p, orig_handle, legend)
        p._transOffset = trans
        return [p]

def test_lines_dists():
    import pylab
    ax = pylab.gca()

    xs, ys = (0,30), (20,150)
    pylab.plot(xs, ys)
    points = list(zip(xs, ys))
    p0, p1 = points

    xs, ys = (0,0,20,30), (100,150,30,200)
    pylab.scatter(xs, ys)

    dist = line2d_seg_dist(p0, p1, (xs[0], ys[0]))
    dist = line2d_seg_dist(p0, p1, np.array((xs, ys)))
    for x, y, d in zip(xs, ys, dist):
        c = Circle((x, y), d, fill=0)
        ax.add_patch(c)

    pylab.xlim(-200, 200)
    pylab.ylim(-200, 200)
    pylab.show()

    def get_glyphs_mathtext(self, prop, s, glyph_map=None,
                            return_new_glyphs_only=False):
        """
        convert the string *s* to vertices and codes by parsing it with
        mathtext.
        """

        prop = prop.copy()
        prop.set_size(self.FONT_SCALE)

        width, height, descent, glyphs, rects = self.mathtext_parser.parse(
            s, self.DPI, prop)

        if not glyph_map:
            glyph_map = dict()

        if return_new_glyphs_only:
            glyph_map_new = dict()
        else:
            glyph_map_new = glyph_map

        xpositions = []
        ypositions = []
        glyph_ids = []
        sizes = []

        currx, curry = 0, 0
        for font, fontsize, ccode, ox, oy in glyphs:
            char_id = self._get_char_id(font, ccode)
            if char_id not in glyph_map:
                font.clear()
                font.set_size(self.FONT_SCALE, self.DPI)
                glyph = font.load_char(ccode, flags=LOAD_NO_HINTING)
                glyph_map_new[char_id] = self.glyph_to_path(font)

            xpositions.append(ox)
            ypositions.append(oy)
            glyph_ids.append(char_id)
            size = fontsize / self.FONT_SCALE
            sizes.append(size)

        myrects = []
        for ox, oy, w, h in rects:
            vert1 = [(ox, oy), (ox, oy + h), (ox + w, oy + h),
                     (ox + w, oy), (ox, oy), (0, 0)]
            code1 = [Path.MOVETO,
                     Path.LINETO, Path.LINETO, Path.LINETO, Path.LINETO,
                     Path.CLOSEPOLY]
            myrects.append((vert1, code1))

        return (list(zip(glyph_ids, xpositions, ypositions, sizes)),
                glyph_map_new, myrects)