path.c

/*
 * The Python Imaging Library.
 *
 * 2D path utilities
 *
 * history:
 * 1996-11-04 fl   Added to PIL (incomplete)
 * 1996-11-05 fl   Added sequence semantics
 * 1997-02-28 fl   Fixed getbbox
 * 1997-06-12 fl   Added id attribute
 * 1997-06-14 fl   Added slicing and setitem
 * 1998-12-29 fl   Improved sequence handling (from Richard Jones)
 * 1999-01-10 fl   Fixed IndexError test for 1.5 (from Fred Drake)
 * 2000-10-12 fl   Added special cases for tuples and lists
 * 2002-10-27 fl   Added clipping boilerplate
 * 2004-09-19 fl   Added tolist(flat) variant
 * 2005-05-06 fl   Added buffer interface support to path constructor
 *
 * notes:
 * FIXME: fill in remaining slots in the sequence api
 *
 * Copyright (c) 1997-2005 by Secret Labs AB
 * Copyright (c) 1997-2005 by Fredrik Lundh
 *
 * See the README file for information on usage and redistribution.
 */


#include "Python.h"
#include "Imaging.h"

#include <math.h>

/* compatibility wrappers (defined in _imaging.c) */
extern int PyImaging_CheckBuffer(PyObject* buffer);
extern int PyImaging_GetBuffer(PyObject* buffer, Py_buffer *view);

/* -------------------------------------------------------------------- */
/* Class                                                                */
/* -------------------------------------------------------------------- */

typedef struct {
    PyObject_HEAD
    Py_ssize_t count;
    double *xy;
    int index; /* temporary use, e.g. in decimate */
} PyPathObject;

static PyTypeObject PyPathType;

static double*
alloc_array(Py_ssize_t count)
{
    double* xy;
    if (count < 0) {
        PyErr_NoMemory();
        return NULL;
    }
    if (count > (SIZE_MAX / (2 * sizeof(double))) - 1 ) {
        PyErr_NoMemory();
        return NULL;
    }
    xy = malloc(2 * count * sizeof(double) + 1);
    if (!xy) {
        PyErr_NoMemory();
    }
    return xy;
}

static PyPathObject*
path_new(Py_ssize_t count, double* xy, int duplicate)
{
    PyPathObject *path;

    if (duplicate) {
        /* duplicate path */
        double* p = alloc_array(count);
        if (!p) {
            return NULL;
        }
        memcpy(p, xy, count * 2 * sizeof(double));
        xy = p;
    }

    if (PyType_Ready(&PyPathType) < 0) {
        free(xy);
        return NULL;
    }

    path = PyObject_New(PyPathObject, &PyPathType);
    if (path == NULL) {
        free(xy);
        return NULL;
    }

    path->count = count;
    path->xy = xy;

    return path;
}

static void
path_dealloc(PyPathObject* path)
{
    free(path->xy);
    PyObject_Del(path);
}

/* -------------------------------------------------------------------- */
/* Helpers                                                              */
/* -------------------------------------------------------------------- */

#define PyPath_Check(op) (Py_TYPE(op) == &PyPathType)

Py_ssize_t
PyPath_Flatten(PyObject* data, double **pxy)
{
    Py_ssize_t i, j, n;
    double *xy;

    if (PyPath_Check(data)) {
        /* This was another path object. */
        PyPathObject *path = (PyPathObject*) data;
        xy = alloc_array(path->count);
        if (!xy) {
            return -1;
        }
        memcpy(xy, path->xy, 2 * path->count * sizeof(double));
        *pxy = xy;
        return path->count;
    }

    if (PyImaging_CheckBuffer(data)) {
        /* Assume the buffer contains floats */
        Py_buffer buffer;
        if (PyImaging_GetBuffer(data, &buffer) == 0) {
            float *ptr = (float*) buffer.buf;
            n = buffer.len / (2 * sizeof(float));
            xy = alloc_array(n);
            if (!xy) {
                return -1;
            }
            for (i = 0; i < n+n; i++) {
                xy[i] = ptr[i];
            }
            *pxy = xy;
            PyBuffer_Release(&buffer);
            return n;
        }
        PyErr_Clear();
    }

    if (!PySequence_Check(data)) {
        PyErr_SetString(PyExc_TypeError, "argument must be sequence");
        return -1;
    }

    j = 0;
    n = PyObject_Length(data);
    /* Just in case __len__ breaks (or doesn't exist) */
    if (PyErr_Occurred()) {
        return -1;
    }

    /* Allocate for worst case */
    xy = alloc_array(n);
    if (!xy) {
        return -1;
    }

    /* Copy table to path array */
    if (PyList_Check(data)) {
        for (i = 0; i < n; i++) {
            double x, y;
            PyObject *op = PyList_GET_ITEM(data, i);
            if (PyFloat_Check(op)) {
                xy[j++] = PyFloat_AS_DOUBLE(op);
            } else if (PyLong_Check(op)) {
                xy[j++] = (float) PyLong_AS_LONG(op);
            } else if (PyNumber_Check(op)) {
                xy[j++] = PyFloat_AsDouble(op);
            } else if (PyArg_ParseTuple(op, "dd", &x, &y)) {
                xy[j++] = x;
                xy[j++] = y;
            } else {
                free(xy);
                return -1;
            }
        }
    } else if (PyTuple_Check(data)) {
        for (i = 0; i < n; i++) {
            double x, y;
            PyObject *op = PyTuple_GET_ITEM(data, i);
            if (PyFloat_Check(op)) {
                xy[j++] = PyFloat_AS_DOUBLE(op);
            } else if (PyLong_Check(op)) {
                xy[j++] = (float) PyLong_AS_LONG(op);
            } else if (PyNumber_Check(op)) {
                xy[j++] = PyFloat_AsDouble(op);
            } else if (PyArg_ParseTuple(op, "dd", &x, &y)) {
                xy[j++] = x;
                xy[j++] = y;
            } else {
                free(xy);
                return -1;
            }
        }
    } else {
        for (i = 0; i < n; i++) {
            double x, y;
            PyObject *op = PySequence_GetItem(data, i);
            if (!op) {
                /* treat IndexError as end of sequence */
                if (PyErr_Occurred() &&
                    PyErr_ExceptionMatches(PyExc_IndexError)) {
                    PyErr_Clear();
                    break;
                } else {
                    free(xy);
                    return -1;
                }
            }
            if (PyFloat_Check(op)) {
                xy[j++] = PyFloat_AS_DOUBLE(op);
            } else if (PyLong_Check(op)) {
                xy[j++] = (float) PyLong_AS_LONG(op);
            } else if (PyNumber_Check(op)) {
                xy[j++] = PyFloat_AsDouble(op);
            } else if (PyArg_ParseTuple(op, "dd", &x, &y)) {
                xy[j++] = x;
                xy[j++] = y;
            } else {
                Py_DECREF(op);
                free(xy);
                return -1;
            }
            Py_DECREF(op);
        }
    }

    if (j & 1) {
        PyErr_SetString(PyExc_ValueError, "wrong number of coordinates");
        free(xy);
        return -1;
    }

    *pxy = xy;
    return j/2;
}


/* -------------------------------------------------------------------- */
/* Factories                                                            */
/* -------------------------------------------------------------------- */

PyObject*
PyPath_Create(PyObject* self, PyObject* args)
{
    PyObject* data;
    Py_ssize_t count;
    double *xy;

    if (PyArg_ParseTuple(args, "n:Path", &count)) {

        /* number of vertices */
        xy = alloc_array(count);
        if (!xy) {
            return NULL;
        }

    } else {

        /* sequence or other path */
        PyErr_Clear();
        if (!PyArg_ParseTuple(args, "O", &data)) {
            return NULL;
        }

        count = PyPath_Flatten(data, &xy);
        if (count < 0) {
            return NULL;
        }
    }

    return (PyObject*) path_new(count, xy, 0);
}


/* -------------------------------------------------------------------- */
/* Methods                                                              */
/* -------------------------------------------------------------------- */

static PyObject*
path_compact(PyPathObject* self, PyObject* args)
{
    /* Simple-minded method to shorten path.  A point is removed if
       the city block distance to the previous point is less than the
       given distance */
    Py_ssize_t i, j;
    double *xy;

    double cityblock = 2.0;

    if (!PyArg_ParseTuple(args, "|d:compact", &cityblock)) {
        return NULL;
    }

    xy = self->xy;

    /* remove bogus vertices */
    for (i = j = 1; i < self->count; i++) {
        if (fabs(xy[j+j-2]-xy[i+i]) + fabs(xy[j+j-1]-xy[i+i+1]) >= cityblock) {
            xy[j+j] = xy[i+i];
            xy[j+j+1] = xy[i+i+1];
            j++;
        }
    }

    i = self->count - j;
    self->count = j;

    /* shrink coordinate array */
    /* malloc check ok, self->count is smaller than it was before */
    self->xy = realloc(self->xy, 2 * self->count * sizeof(double));

    return Py_BuildValue("i", i); /* number of removed vertices */
}

static PyObject*
path_getbbox(PyPathObject* self, PyObject* args)
{
    /* Find bounding box */
    Py_ssize_t i;
    double *xy;
    double x0, y0, x1, y1;

    if (!PyArg_ParseTuple(args, ":getbbox")) {
        return NULL;
    }

    xy = self->xy;

    x0 = x1 = xy[0];
    y0 = y1 = xy[1];

    for (i = 1; i < self->count; i++) {
        if (xy[i+i] < x0) {
            x0 = xy[i+i];
        }
        if (xy[i+i] > x1) {
            x1 = xy[i+i];
        }
        if (xy[i+i+1] < y0) {
            y0 = xy[i+i+1];
        }
        if (xy[i+i+1] > y1) {
            y1 = xy[i+i+1];
        }
    }

    return Py_BuildValue("dddd", x0, y0, x1, y1);
}

static PyObject*
path_getitem(PyPathObject* self, Py_ssize_t i)
{
    if (i < 0) {
        i = self->count + i;
    }
    if (i < 0 || i >= self->count) {
        PyErr_SetString(PyExc_IndexError, "path index out of range");
        return NULL;
    }

    return Py_BuildValue("dd", self->xy[i+i], self->xy[i+i+1]);
}

static PyObject*
path_getslice(PyPathObject* self, Py_ssize_t ilow, Py_ssize_t ihigh)
{
    /* adjust arguments */
    if (ilow < 0) {
        ilow = 0;
    } else if (ilow >= self->count) {
        ilow = self->count;
    }
    if (ihigh < 0) {
        ihigh = 0;
    }
    if (ihigh < ilow) {
        ihigh = ilow;
    } else if (ihigh > self->count) {
        ihigh = self->count;
    }

    return (PyObject*) path_new(ihigh - ilow, self->xy + ilow * 2, 1);
}

static Py_ssize_t
path_len(PyPathObject* self)
{
    return self->count;
}

static PyObject*
path_map(PyPathObject* self, PyObject* args)
{
    /* Map coordinate set through function */
    Py_ssize_t i;
    double *xy;
    PyObject* function;

    if (!PyArg_ParseTuple(args, "O:map", &function)) {
        return NULL;
    }

    xy = self->xy;

    /* apply function to coordinate set */
    for (i = 0; i < self->count; i++) {
        double x = xy[i+i];
        double y = xy[i+i+1];
        PyObject* item = PyObject_CallFunction(function, "dd", x, y);
        if (!item || !PyArg_ParseTuple(item, "dd", &x, &y)) {
            Py_XDECREF(item);
            return NULL;
        }
        xy[i+i] = x;
        xy[i+i+1] = y;
        Py_DECREF(item);
    }

    Py_INCREF(Py_None);
    return Py_None;
}

static int
path_setitem(PyPathObject* self, Py_ssize_t i, PyObject* op)
{
    double* xy;

    if (i < 0 || i >= self->count) {
        PyErr_SetString(PyExc_IndexError,
                        "path assignment index out of range");
        return -1;
    }

    if (op == NULL) {
        PyErr_SetString(PyExc_TypeError,
                        "cannot delete from path");
        return -1;
    }

    xy = &self->xy[i+i];

    if (!PyArg_ParseTuple(op, "dd", &xy[0], &xy[1])) {
        return -1;
    }

    return 0;
}

static PyObject*
path_tolist(PyPathObject* self, PyObject* args)
{
    PyObject *list;
    Py_ssize_t i;

    int flat = 0;
    if (!PyArg_ParseTuple(args, "|i:tolist", &flat)) {
        return NULL;
    }

    if (flat) {
        list = PyList_New(self->count*2);
        for (i = 0; i < self->count*2; i++) {
            PyObject* item;
            item = PyFloat_FromDouble(self->xy[i]);
            if (!item) {
                goto error;
            }
            PyList_SetItem(list, i, item);
        }
    } else {
        list = PyList_New(self->count);
        for (i = 0; i < self->count; i++) {
            PyObject* item;
            item = Py_BuildValue("dd", self->xy[i+i], self->xy[i+i+1]);
            if (!item) {
                goto error;
            }
            PyList_SetItem(list, i, item);
        }
    }

    return list;

error:
    Py_DECREF(list);
    return NULL;
}

static PyObject*
path_transform(PyPathObject* self, PyObject* args)
{
    /* Apply affine transform to coordinate set */
    Py_ssize_t i;
    double *xy;
    double a, b, c, d, e, f;

    double wrap = 0.0;

    if (!PyArg_ParseTuple(args, "(dddddd)|d:transform",
                          &a, &b, &c, &d, &e, &f,
                          &wrap)) {
        return NULL;
    }

    xy = self->xy;

    /* transform the coordinate set */
    if (b == 0.0 && d == 0.0) {
        /* scaling */
        for (i = 0; i < self->count; i++) {
            xy[i+i]   = a*xy[i+i]+c;
            xy[i+i+1] = e*xy[i+i+1]+f;
        }
    } else {
        /* affine transform */
        for (i = 0; i < self->count; i++) {
            double x = xy[i+i];
            double y = xy[i+i+1];
            xy[i+i]   = a*x+b*y+c;
            xy[i+i+1] = d*x+e*y+f;
        }
    }

    /* special treatment of geographical map data */
    if (wrap != 0.0) {
        for (i = 0; i < self->count; i++) {
            xy[i+i] = fmod(xy[i+i], wrap);
        }
    }

    Py_INCREF(Py_None);
    return Py_None;
}

static struct PyMethodDef methods[] = {
    {"getbbox", (PyCFunction)path_getbbox, 1},
    {"tolist", (PyCFunction)path_tolist, 1},
    {"compact", (PyCFunction)path_compact, 1},
    {"map", (PyCFunction)path_map, 1},
    {"transform", (PyCFunction)path_transform, 1},
    {NULL, NULL} /* sentinel */
};

static PyObject*
path_getattr_id(PyPathObject* self, void* closure)
{
        return Py_BuildValue("n", (Py_ssize_t) self->xy);
}

static struct PyGetSetDef getsetters[] = {
    { "id", (getter) path_getattr_id },
    { NULL }
};

static PyObject*
path_subscript(PyPathObject* self, PyObject* item) {
    if (PyIndex_Check(item)) {
        Py_ssize_t i;
        i = PyNumber_AsSsize_t(item, PyExc_IndexError);
        if (i == -1 && PyErr_Occurred()) {
            return NULL;
        }
        return path_getitem(self, i);
    }
    if (PySlice_Check(item)) {
        int len = 4;
        Py_ssize_t start, stop, step, slicelength;

        if (PySlice_GetIndicesEx(item, len, &start, &stop, &step, &slicelength) < 0) {
            return NULL;
        }

        if (slicelength <= 0) {
            double *xy = alloc_array(0);
            return (PyObject*) path_new(0, xy, 0);
        }
        else if (step == 1) {
            return path_getslice(self, start, stop);
        }
        else {
            PyErr_SetString(PyExc_TypeError, "slice steps not supported");
            return NULL;
        }
    }
    else {
        PyErr_Format(PyExc_TypeError,
                     "Path indices must be integers, not %.200s",
                     Py_TYPE(item)->tp_name);
        return NULL;
    }
}

static PySequenceMethods path_as_sequence = {
        (lenfunc)path_len, /*sq_length*/
        (binaryfunc)0, /*sq_concat*/
        (ssizeargfunc)0, /*sq_repeat*/
        (ssizeargfunc)path_getitem, /*sq_item*/
        (ssizessizeargfunc)path_getslice, /*sq_slice*/
        (ssizeobjargproc)path_setitem, /*sq_ass_item*/
        (ssizessizeobjargproc)0, /*sq_ass_slice*/
};

static PyMappingMethods path_as_mapping = {
    (lenfunc)path_len,
    (binaryfunc)path_subscript,
    NULL
};

static PyTypeObject PyPathType = {
    PyVarObject_HEAD_INIT(NULL, 0)
    "Path",                         /*tp_name*/
    sizeof(PyPathObject),           /*tp_size*/
    0,                              /*tp_itemsize*/
    /* methods */
    (destructor)path_dealloc,       /*tp_dealloc*/
    0,                              /*tp_print*/
    0,                                  /*tp_getattr*/
    0,                              /*tp_setattr*/
    0,                              /*tp_compare*/
    0,                              /*tp_repr*/
    0,                              /*tp_as_number */
    &path_as_sequence,              /*tp_as_sequence */
    &path_as_mapping,           /*tp_as_mapping */
    0,                          /*tp_hash*/
    0,                          /*tp_call*/
    0,                          /*tp_str*/
    0,                          /*tp_getattro*/
    0,                          /*tp_setattro*/
    0,                          /*tp_as_buffer*/
    Py_TPFLAGS_DEFAULT,         /*tp_flags*/
    0,                          /*tp_doc*/
    0,                          /*tp_traverse*/
    0,                          /*tp_clear*/
    0,                          /*tp_richcompare*/
    0,                          /*tp_weaklistoffset*/
    0,                          /*tp_iter*/
    0,                          /*tp_iternext*/
    methods,                    /*tp_methods*/
    0,                          /*tp_members*/
    getsetters,                 /*tp_getset*/
};