Back to index

lightning-sunbird  0.9+nobinonly
cairo-hull.c
Go to the documentation of this file.
00001 /* cairo - a vector graphics library with display and print output
00002  *
00003  * Copyright © 2003 University of Southern California
00004  *
00005  * This library is free software; you can redistribute it and/or
00006  * modify it either under the terms of the GNU Lesser General Public
00007  * License version 2.1 as published by the Free Software Foundation
00008  * (the "LGPL") or, at your option, under the terms of the Mozilla
00009  * Public License Version 1.1 (the "MPL"). If you do not alter this
00010  * notice, a recipient may use your version of this file under either
00011  * the MPL or the LGPL.
00012  *
00013  * You should have received a copy of the LGPL along with this library
00014  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
00015  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
00016  * You should have received a copy of the MPL along with this library
00017  * in the file COPYING-MPL-1.1
00018  *
00019  * The contents of this file are subject to the Mozilla Public License
00020  * Version 1.1 (the "License"); you may not use this file except in
00021  * compliance with the License. You may obtain a copy of the License at
00022  * http://www.mozilla.org/MPL/
00023  *
00024  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
00025  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
00026  * the specific language governing rights and limitations.
00027  *
00028  * The Original Code is the cairo graphics library.
00029  *
00030  * The Initial Developer of the Original Code is University of Southern
00031  * California.
00032  *
00033  * Contributor(s):
00034  *     Carl D. Worth <cworth@cworth.org>
00035  */
00036 
00037 #include "cairoint.h"
00038 
00039 typedef struct cairo_hull
00040 {
00041     cairo_point_t point;
00042     cairo_slope_t slope;
00043     int discard;
00044     int id;
00045 } cairo_hull_t;
00046 
00047 static cairo_hull_t *
00048 _cairo_hull_create (cairo_pen_vertex_t *vertices, int num_vertices)
00049 {
00050     int i;
00051     cairo_hull_t *hull;
00052     cairo_point_t *p, *extremum, tmp;
00053 
00054     extremum = &vertices[0].point;
00055     for (i = 1; i < num_vertices; i++) {
00056        p = &vertices[i].point;
00057        if (p->y < extremum->y || (p->y == extremum->y && p->x < extremum->x))
00058            extremum = p;
00059     }
00060     /* Put the extremal point at the beginning of the array */
00061     tmp = *extremum;
00062     *extremum = vertices[0].point;
00063     vertices[0].point = tmp;
00064 
00065     hull = malloc (num_vertices * sizeof (cairo_hull_t));
00066     if (hull == NULL)
00067        return NULL;
00068 
00069     for (i = 0; i < num_vertices; i++) {
00070        hull[i].point = vertices[i].point;
00071        _cairo_slope_init (&hull[i].slope, &hull[0].point, &hull[i].point);
00072 
00073         /* give each point a unique id for later comparison */
00074         hull[i].id = i;
00075 
00076         /* Don't discard by default */
00077         hull[i].discard = 0;
00078 
00079        /* Discard all points coincident with the extremal point */
00080        if (i != 0 && hull[i].slope.dx == 0 && hull[i].slope.dy == 0)
00081            hull[i].discard = 1;
00082     }
00083 
00084     return hull;
00085 }
00086 
00087 static int
00088 _cairo_hull_vertex_compare (const void *av, const void *bv)
00089 {
00090     cairo_hull_t *a = (cairo_hull_t *) av;
00091     cairo_hull_t *b = (cairo_hull_t *) bv;
00092     int ret;
00093 
00094     ret = _cairo_slope_compare (&a->slope, &b->slope);
00095 
00096     /* In the case of two vertices with identical slope from the
00097        extremal point discard the nearer point. */
00098 
00099     if (ret == 0) {
00100        cairo_fixed_48_16_t a_dist, b_dist;
00101        a_dist = ((cairo_fixed_48_16_t) a->slope.dx * a->slope.dx +
00102                 (cairo_fixed_48_16_t) a->slope.dy * a->slope.dy);
00103        b_dist = ((cairo_fixed_48_16_t) b->slope.dx * b->slope.dx +
00104                 (cairo_fixed_48_16_t) b->slope.dy * b->slope.dy);
00105        /*
00106         * Use the point's ids to ensure a total ordering.
00107         * a well-defined ordering, and avoid setting discard on
00108         * both points.          
00109         */
00110        if (a_dist < b_dist || (a_dist == b_dist && a->id < b->id)) {
00111            a->discard = 1;
00112            ret = -1;
00113        } else {
00114            b->discard = 1;
00115            ret = 1;
00116        }
00117     }
00118 
00119     return ret;
00120 }
00121 
00122 static int
00123 _cairo_hull_prev_valid (cairo_hull_t *hull, int num_hull, int index)
00124 {
00125     do {
00126        /* hull[0] is always valid, so don't test and wraparound */
00127        index--;
00128     } while (hull[index].discard);
00129 
00130     return index;
00131 }
00132 
00133 static int
00134 _cairo_hull_next_valid (cairo_hull_t *hull, int num_hull, int index)
00135 {
00136     do {
00137        index = (index + 1) % num_hull;
00138     } while (hull[index].discard);
00139 
00140     return index;
00141 }
00142 
00143 static cairo_status_t
00144 _cairo_hull_eliminate_concave (cairo_hull_t *hull, int num_hull)
00145 {
00146     int i, j, k;
00147     cairo_slope_t slope_ij, slope_jk;
00148 
00149     i = 0;
00150     j = _cairo_hull_next_valid (hull, num_hull, i);
00151     k = _cairo_hull_next_valid (hull, num_hull, j);
00152 
00153     do {
00154        _cairo_slope_init (&slope_ij, &hull[i].point, &hull[j].point);
00155        _cairo_slope_init (&slope_jk, &hull[j].point, &hull[k].point);
00156 
00157        /* Is the angle formed by ij and jk concave? */
00158        if (_cairo_slope_compare (&slope_ij, &slope_jk) >= 0) {
00159            if (i == k)
00160               return CAIRO_STATUS_SUCCESS;
00161            hull[j].discard = 1;
00162            j = i;
00163            i = _cairo_hull_prev_valid (hull, num_hull, j);
00164        } else {
00165            i = j;
00166            j = k;
00167            k = _cairo_hull_next_valid (hull, num_hull, j);
00168        }
00169     } while (j != 0);
00170 
00171     return CAIRO_STATUS_SUCCESS;
00172 }
00173 
00174 static cairo_status_t
00175 _cairo_hull_to_pen (cairo_hull_t *hull, cairo_pen_vertex_t *vertices, int *num_vertices)
00176 {
00177     int i, j = 0;
00178 
00179     for (i = 0; i < *num_vertices; i++) {
00180        if (hull[i].discard)
00181            continue;
00182        vertices[j++].point = hull[i].point;
00183     }
00184 
00185     *num_vertices = j;
00186 
00187     return CAIRO_STATUS_SUCCESS;
00188 }
00189 
00190 /* Given a set of vertices, compute the convex hull using the Graham
00191    scan algorithm. */
00192 cairo_status_t
00193 _cairo_hull_compute (cairo_pen_vertex_t *vertices, int *num_vertices)
00194 {
00195     cairo_hull_t *hull;
00196     int num_hull = *num_vertices;
00197 
00198     hull = _cairo_hull_create (vertices, num_hull);
00199     if (hull == NULL)
00200        return CAIRO_STATUS_NO_MEMORY;
00201 
00202     qsort (hull + 1, num_hull - 1,
00203           sizeof (cairo_hull_t), _cairo_hull_vertex_compare);
00204 
00205     _cairo_hull_eliminate_concave (hull, num_hull);
00206 
00207     _cairo_hull_to_pen (hull, vertices, num_vertices);
00208 
00209     free (hull);
00210 
00211     return CAIRO_STATUS_SUCCESS;
00212 }