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., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, 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
#include "cairo-slope-private.h"
40

            
41
/* Compare two slopes. Slope angles begin at 0 in the direction of the
42
   positive X axis and increase in the direction of the positive Y
43
   axis.
44

            
45
   This function always compares the slope vectors based on the
46
   smaller angular difference between them, (that is based on an
47
   angular difference that is strictly less than pi). To break ties
48
   when comparing slope vectors with an angular difference of exactly
49
   pi, the vector with a positive dx (or positive dy if dx's are zero)
50
   is considered to be more positive than the other.
51

            
52
   Also, all slope vectors with both dx==0 and dy==0 are considered
53
   equal and more positive than any non-zero vector.
54

            
55
   <  0 => a less positive than b
56
   == 0 => a equal to b
57
   >  0 => a more positive than b
58
*/
59
int
60
512436
_cairo_slope_compare (const cairo_slope_t *a, const cairo_slope_t *b)
61
{
62
512436
    cairo_int64_t ady_bdx = _cairo_int32x32_64_mul (a->dy, b->dx);
63
512436
    cairo_int64_t bdy_adx = _cairo_int32x32_64_mul (b->dy, a->dx);
64
    int cmp;
65

            
66
512436
    cmp = _cairo_int64_cmp (ady_bdx, bdy_adx);
67
512436
    if (cmp)
68
501015
	return cmp;
69

            
70
    /* special-case zero vectors.  the intended logic here is:
71
     * zero vectors all compare equal, and more positive than any
72
     * non-zero vector.
73
     */
74
11421
    if (a->dx == 0 && a->dy == 0 && b->dx == 0 && b->dy ==0)
75
	return 0;
76
11421
    if (a->dx == 0 && a->dy == 0)
77
	return 1;
78
11421
    if (b->dx == 0 && b->dy ==0)
79
3
	return -1;
80

            
81
    /* Finally, we're looking at two vectors that are either equal or
82
     * that differ by exactly pi. We can identify the "differ by pi"
83
     * case by looking for a change in sign in either dx or dy between
84
     * a and b.
85
     *
86
     * And in these cases, we eliminate the ambiguity by reducing the angle
87
     * of b by an infinitesimally small amount, (that is, 'a' will
88
     * always be considered less than 'b').
89
     */
90
11418
    if ((a->dx ^ b->dx) < 0 || (a->dy ^ b->dy) < 0) {
91
3321
	if (a->dx > 0 || (a->dx == 0 && a->dy > 0))
92
1923
	    return -1;
93
	else
94
1398
	    return +1;
95
    }
96

            
97
    /* Finally, for identical slopes, we obviously return 0. */
98
8097
    return 0;
99
}