This file is indexed.

/usr/share/pyshared/matplotlib/delaunay/interpolate.py is in python-matplotlib 1.3.1-1ubuntu5.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
from __future__ import print_function
import numpy as np

from matplotlib._delaunay import compute_planes, linear_interpolate_grid
from matplotlib._delaunay import nn_interpolate_grid
from matplotlib._delaunay import nn_interpolate_unstructured

__all__ = ['LinearInterpolator', 'NNInterpolator']


def slice2gridspec(key):
    """Convert a 2-tuple of slices to start,stop,steps for x and y.

    key -- (slice(ystart,ystop,ystep), slice(xtart, xstop, xstep))

    For now, the only accepted step values are imaginary integers (interpreted
    in the same way numpy.mgrid, etc. do).
    """
    if ((len(key) != 2) or
        (not isinstance(key[0], slice)) or
        (not isinstance(key[1], slice))):
        raise ValueError("only 2-D slices, please")

    x0 = key[1].start
    x1 = key[1].stop
    xstep = key[1].step
    if not isinstance(xstep, complex) or int(xstep.real) != xstep.real:
        raise ValueError("only the [start:stop:numsteps*1j] form supported")
    xstep = int(xstep.imag)
    y0 = key[0].start
    y1 = key[0].stop
    ystep = key[0].step
    if not isinstance(ystep, complex) or int(ystep.real) != ystep.real:
        raise ValueError("only the [start:stop:numsteps*1j] form supported")
    ystep = int(ystep.imag)

    return x0, x1, xstep, y0, y1, ystep


class LinearInterpolator(object):
    """Interpolate a function defined on the nodes of a triangulation by
    using the planes defined by the three function values at each corner of
    the triangles.

    LinearInterpolator(triangulation, z, default_value=numpy.nan)

    triangulation -- Triangulation instance
    z -- the function values at each node of the triangulation
    default_value -- a float giving the default value should the interpolating
      point happen to fall outside of the convex hull of the triangulation

    At the moment, the only regular rectangular grids are supported for
    interpolation.

        vals = interp[ystart:ystop:ysteps*1j, xstart:xstop:xsteps*1j]

    vals would then be a (ysteps, xsteps) array containing the interpolated
    values. These arguments are interpreted the same way as numpy.mgrid.

    Attributes:
      planes -- (ntriangles, 3) array of floats specifying the plane for each
        triangle.

    Linear Interpolation
    --------------------
    Given the Delauany triangulation (or indeed *any* complete triangulation)
    we can interpolate values inside the convex hull by locating the enclosing
    triangle of the interpolation point and returning the value at that point
    of the plane defined by the three node values.

        f = planes[tri,0]*x + planes[tri,1]*y + planes[tri,2]

    The interpolated function is C0 continuous across the convex hull of the
    input points. It is C1 continuous across the convex hull except for the
    nodes and the edges of the triangulation.
    """
    def __init__(self, triangulation, z, default_value=np.nan):
        self.triangulation = triangulation
        self.z = np.asarray(z, dtype=np.float64)
        self.default_value = default_value

        self.planes = compute_planes(triangulation.x, triangulation.y, self.z,
            triangulation.triangle_nodes)

    def __getitem__(self, key):
        x0, x1, xstep, y0, y1, ystep = slice2gridspec(key)
        grid = linear_interpolate_grid(
            x0, x1, xstep, y0, y1, ystep, self.default_value,
            self.planes, self.triangulation.x, self.triangulation.y,
            self.triangulation.triangle_nodes,
            self.triangulation.triangle_neighbors)
        return grid


class NNInterpolator(object):
    """Interpolate a function defined on the nodes of a triangulation by
    the natural neighbors method.

    NNInterpolator(triangulation, z, default_value=numpy.nan)

    triangulation -- Triangulation instance
    z -- the function values at each node of the triangulation
    default_value -- a float giving the default value should the interpolating
      point happen to fall outside of the convex hull of the triangulation

    At the moment, the only regular rectangular grids are supported for
    interpolation.

        vals = interp[ystart:ystop:ysteps*1j, xstart:xstop:xsteps*1j]

    vals would then be a (ysteps, xsteps) array containing the interpolated
    values. These arguments are interpreted the same way as numpy.mgrid.

    Natural Neighbors Interpolation
    -------------------------------
    One feature of the Delaunay triangulation is that for each triangle, its
    circumcircle contains no other point (although in degenerate cases, like
    squares, other points may be *on* the circumcircle). One can also
    construct what is called the Voronoi diagram from a Delaunay triangulation
    by connecting the circumcenters of the triangles to those of their
    neighbors to form a tesselation of irregular polygons covering the plane
    and containing only one node from the triangulation. Each point in one
    node's Voronoi polygon is closer to that node than any other node.

    To compute the Natural Neighbors interpolant, we consider adding the
    interpolation point to the triangulation. We define the natural neighbors
    of this point as the set of nodes participating in Delaunay triangles
    whose circumcircles contain the point. To restore the Delaunay-ness of the
    triangulation, one would only have to alter those triangles and Voronoi
    polygons. The new Voronoi diagram would have a polygon around the
    inserted point. This polygon would "steal" area from the original Voronoi
    polygons. For each node i in the natural neighbors set, we compute the
    area stolen from its original Voronoi polygon, stolen[i]. We define the
    natural neighbors coordinates

        phi[i] = stolen[i] / sum(stolen,axis=0)

    We then use these phi[i] to weight the corresponding function values from
    the input data z to compute the interpolated value.

    The interpolated surface is C1-continuous except at the nodes themselves
    across the convex hull of the input points. One can find the set of points
    that a given node will affect by computing the union of the areas covered
    by the circumcircles of each Delaunay triangle that node participates in.
    """

    def __init__(self, triangulation, z, default_value=np.nan):
        self.triangulation = triangulation
        self.z = np.asarray(z, dtype=np.float64)
        self.default_value = default_value

    def __getitem__(self, key):
        x0, x1, xstep, y0, y1, ystep = slice2gridspec(key)
        grid = nn_interpolate_grid(
            x0, x1, xstep, y0, y1, ystep, self.default_value,
            self.triangulation.x, self.triangulation.y, self.z,
            self.triangulation.circumcenters,
            self.triangulation.triangle_nodes,
            self.triangulation.triangle_neighbors)
        return grid

    def __call__(self, intx, inty):
        intz = nn_interpolate_unstructured(intx, inty, self.default_value,
            self.triangulation.x, self.triangulation.y, self.z,
            self.triangulation.circumcenters,
            self.triangulation.triangle_nodes,
            self.triangulation.triangle_neighbors)
        return intz