cairo/src/cairo-slope.c

   1 /* cairo - a vector graphics library with display and print output
   2  *
   3  * Copyright © 2002 University of Southern California
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it either under the terms of the GNU Lesser General Public
   7  * License version 2.1 as published by the Free Software Foundation
   8  * (the "LGPL") or, at your option, under the terms of the Mozilla
   9  * Public License Version 1.1 (the "MPL"). If you do not alter this
  10  * notice, a recipient may use your version of this file under either
  11  * the MPL or the LGPL.
  12  *
  13  * You should have received a copy of the LGPL along with this library
  14  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  15  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  16  * You should have received a copy of the MPL along with this library
  17  * in the file COPYING-MPL-1.1
  18  *
  19  * The contents of this file are subject to the Mozilla Public License
  20  * Version 1.1 (the "License"); you may not use this file except in
  21  * compliance with the License. You may obtain a copy of the License at
  22  * http://www.mozilla.org/MPL/
  23  *
  24  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  25  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  26  * the specific language governing rights and limitations.
  27  *
  28  * The Original Code is the cairo graphics library.
  29  *
  30  * The Initial Developer of the Original Code is University of Southern
  31  * California.
  32  *
  33  * Contributor(s):
  34  *      Carl D. Worth <cworth@cworth.org>
  35  */
  36
  37 #include "cairoint.h"
  38
  39 void
  40 _cairo_slope_init (cairo_slope_t *slope,
  41                    const cairo_point_t *a,
  42                    const cairo_point_t *b)
  43 {
  44     slope->dx = b->x - a->x;
  45     slope->dy = b->y - a->y;
  46 }
  47
  48 /* Compare two slopes. Slope angles begin at 0 in the direction of the
  49    positive X axis and increase in the direction of the positive Y
  50    axis.
  51
  52    This function always compares the slope vectors based on the
  53    smaller angular difference between them, (that is based on an
  54    angular difference that is strictly less than pi). To break ties
  55    when comparing slope vectors with an angular difference of exactly
  56    pi, the vector with a positive dx (or positive dy if dx's are zero)
  57    is considered to be more positive than the other.
  58
  59    Also, all slope vectors with both dx==0 and dy==0 are considered
  60    equal and more positive than any non-zero vector.
  61
  62    <  0 => a less positive than b
  63    == 0 => a equal to b
  64    >  0 => a more positive than b
  65 */
  66 int
  67 _cairo_slope_compare (const cairo_slope_t *a, const cairo_slope_t *b)
  68 {
  69     cairo_int64_t ady_bdx = _cairo_int32x32_64_mul (a->dy, b->dx);
  70     cairo_int64_t bdy_adx = _cairo_int32x32_64_mul (b->dy, a->dx);
  71     int cmp;
  72
  73     cmp = _cairo_int64_cmp (ady_bdx, bdy_adx);
  74     if (cmp)
  75         return cmp;
  76
  77     /* special-case zero vectors.  the intended logic here is:
  78      * zero vectors all compare equal, and more positive than any
  79      * non-zero vector.
  80      */
  81     if (a->dx == 0 && a->dy == 0 && b->dx == 0 && b->dy ==0)
  82         return 0;
  83     if (a->dx == 0 && a->dy == 0)
  84         return 1;
  85     if (b->dx == 0 && b->dy ==0)
  86         return -1;
  87
  88     /* Finally, we're looking at two vectors that are either equal or
  89      * that differ by exactly pi. We can identify the "differ by pi"
  90      * case by looking for a change in sign in either dx or dy between
  91      * a and b.
  92      *
  93      * And in these cases, we eliminate the ambiguity by reducing the angle
  94      * of b by an infinitesimally small amount, (that is, 'a' will
  95      * always be considered less than 'b').
  96      */
  97     if (((a->dx > 0) != (b->dx > 0)) ||
  98         ((a->dy > 0) != (b->dy > 0)))
  99     {
 100         if (a->dx > 0 || (a->dx == 0 && a->dy > 0))
 101             return +1;
 102         else
 103             return -1;
 104     }
 105
 106     /* Finally, for identical slopes, we obviously return 0. */
 107     return 0;
 108 }