← Back to branch summary

~ubuntu-branches/ubuntu/lucid/graphviz/lucid-security

« back to all changes in this revision

Viewing changes to incr/edgeclip.c

  • Committer: Bazaar Package Importer
  • Author(s): Stephen M Moraco
  • Date: 2002-02-05 18:52:12 UTC
  • Revision ID: james.westby@ubuntu.com-20020205185212-8i04c70te00rc40y
Tags: upstream-1.7.16
Import upstream version 1.7.16

Show diffs side-by-side

added added

removed removed

Lines of Context:
incr/edgeclip.c
 
1
#include <engine.h>
 
2
#include <math.h>
 
3
#define EPSILON (.005)
 
4
 
 
5
#ifdef DMALLOC
 
6
#include "dmalloc.h"
 
7
#endif
 
8
 
 
9
static int seg_size(ilcurve_t *curve)
 
10
{
 
11
        switch (curve->type) {
 
12
                case IL_SPLINE :        return 4;
 
13
                case IL_POLYLINE : return 2;
 
14
        }
 
15
        abort(); return 0;
 
16
}
 
17
 
 
18
static ilbool pt_eq(ilcoord_t p, ilcoord_t q)
 
19
{
 
20
        return ((p.x == q.x) && (p.y == q.y));
 
21
}
 
22
 
 
23
static ilcoord_t sub_pt(ilcoord_t p0, ilcoord_t p1)
 
24
{
 
25
        ilcoord_t       rv;
 
26
        rv.x = p0.x - p1.x; rv.y = p0.y - p1.y;
 
27
        return rv;
 
28
}
 
29
 
 
30
static void install_seg(ilcoord_t *src, int n, ilcurve_t *result)
 
31
{
 
32
        int             i;
 
33
 
 
34
        if (result->n == 0)
 
35
                result->p[result->n++] = src[0];
 
36
        else {
 
37
                /* check that curve is continuous */
 
38
                assert(pt_eq(result->p[result->n - 1], src[0]));
 
39
        }
 
40
 
 
41
        for (i = 1; i < n; i++)
 
42
                result->p[result->n++] = src[i];
 
43
}
 
44
 
 
45
#define W_DEGREE 5
 
46
ilcoord_t Bezier (ilcoord_t *V, int degree, double t,
 
47
        ilcoord_t *Left, ilcoord_t *Right)
 
48
{
 
49
    int                 i, j;   /* Index variables  */
 
50
    ilcoord_t   Vtemp[W_DEGREE + 1][W_DEGREE + 1];
 
51
 
 
52
    /* Copy control points  */
 
53
    for (j = 0; j <= degree; j++) {
 
54
        Vtemp[0][j] = V[j];
 
55
    }
 
56
 
 
57
    /* Triangle computation */
 
58
    for (i = 1; i <= degree; i++) {
 
59
        for (j = 0; j <= degree - i; j++) {
 
60
            Vtemp[i][j].x =
 
61
                (1.0 - t) * Vtemp[i-1][j].x + t * Vtemp[i-1][j+1].x;
 
62
            Vtemp[i][j].y =
 
63
                (1.0 - t) * Vtemp[i-1][j].y + t * Vtemp[i-1][j+1].y;
 
64
        }
 
65
    }
 
66
 
 
67
    if (Left != NIL(ilcoord_t*))
 
68
        for (j = 0; j <= degree; j++)
 
69
                Left[j] = Vtemp[j][0];
 
70
    if (Right != NIL(ilcoord_t*))
 
71
        for (j = 0; j <= degree; j++)
 
72
                Right[j] = Vtemp[degree-j][j];
 
73
    return (Vtemp[degree][0]);
 
74
}
 
75
 
 
76
static ilbool inshape(ILnode_t *spec, ilcoord_t coord)
 
77
{
 
78
        return il_inshape(spec->shape,sub_pt(coord,spec->pos));
 
79
}
 
80
 
 
81
static ilcoord_t *clip(ilcoord_t *A, int n, ILnode_t *node, ilcoord_t *out)
 
82
{
 
83
        double          high, low, t;
 
84
        ilcoord_t       p,*lowseg,*highseg,theseg[4];
 
85
        int                     i;
 
86
        ilbool          inside, low_inside, high_inside;
 
87
        ilcoord_t       best[4];
 
88
 
 
89
        high = 1.0;
 
90
        low = 0.0;
 
91
        low_inside = inshape(node,A[0]);
 
92
        high_inside = inshape(node,A[n-1]);
 
93
        if (low_inside == high_inside) return A;
 
94
        if (low_inside) {highseg = theseg; lowseg = NIL(ilcoord_t*);}
 
95
        else {lowseg = theseg; highseg = NIL(ilcoord_t*);}
 
96
 
 
97
        do {
 
98
                t = (high + low) / 2.0;
 
99
                p = Bezier(A,n-1,t,lowseg,highseg);
 
100
                inside = inshape(node,p);
 
101
                if (NOT(inside)) {
 
102
                        for (i = 0; i < n; i++) best[i] = theseg[i];
 
103
                }
 
104
                if (inside == low_inside) low = t;
 
105
                else high = t;
 
106
        } while (high - low > EPSILON); /* should be adaptive with resolution */
 
107
        for (i = 0; i < n; i++) out[i] = best[i];
 
108
        return out;
 
109
}
 
110
 
 
111
ilcurve_t *il_clip_endpoints(engview_t *view, ilcurve_t *curve, ILnode_t *tl, ILnode_t *hd)
 
112
{
 
113
        int                     i, n, segsz, fst_i, lst_i;
 
114
        ilcurve_t       *result;
 
115
        ilcoord_t       *section,temp[4];
 
116
 
 
117
        result = il_newcurve(agheap(view->model.main),curve->type,curve->n);
 
118
        segsz = seg_size(curve);
 
119
        n = curve->n;
 
120
 
 
121
        /* find terminal sections */
 
122
        for (fst_i = 0; fst_i < n; fst_i = fst_i + (segsz - 1))
 
123
                if (NOT(inshape(tl,curve->p[fst_i + segsz - 1]))) break;
 
124
        for (lst_i = n - segsz; lst_i >= 0; lst_i = lst_i - (segsz - 1))
 
125
                if (NOT(inshape(hd,curve->p[lst_i]))) break;
 
126
 
 
127
        for (i = fst_i; i <= lst_i; i = i + segsz - 1) {
 
128
                section = &(curve->p[i]);
 
129
                if (i == fst_i) section = clip(section,segsz,tl,temp);
 
130
                if (i == lst_i) section = clip(section,segsz,hd,temp);
 
131
                install_seg(section,segsz,result);
 
132
        }
 
133
        return result;
 
134
}
 
135
 
 
136
int il_get_seg(ilcurve_t *curve, double y)
 
137
{
 
138
        int             i,i0;
 
139
                int                             sz;
 
140
                double                  y0,y1;
 
141
 
 
142
                sz = seg_size(curve) - 1;
 
143
        for (i = 0; i < curve->n - 1; i += sz) {
 
144
                for (i0 = i; i0 < i + sz; i0++) {
 
145
                        y0 = curve->p[i0].y;
 
146
                                                y1 = curve->p[i0+1].y;
 
147
                                                if (((y0 <= y) && (y <= y1)) || ((y1 <= y) && (y <= y0)))
 
148
                                return i;
 
149
                }
 
150
        }
 
151
                return -1;
 
152
}
 
153
 
 
154
ilcoord_t il_intersect_at_y(ilcurve_t *curve, double y)
 
155
{
 
156
        ilcoord_t       rv;
 
157
 
 
158
        if (il_test_y_intersection(curve, y, &rv) == FALSE)
 
159
                abort();
 
160
        return rv;
 
161
}
 
162
 
 
163
ilbool il_test_y_intersection(ilcurve_t *curve, double y, ilcoord_t *rv)
 
164
{
 
165
        double  high, low, t, abs_d;
 
166
        double  d, abs_dd;
 
167
        int             i, seg, sz;
 
168
        ilcoord_t       p,q;
 
169
 
 
170
        if (curve->n <= 0) return FALSE;
 
171
        for (i = 0; i < curve->n; i += curve->n - 1)
 
172
                if (curve->p[i].y == y) {*rv = curve->p[i]; return TRUE;}
 
173
        if (curve->p[curve->n-1].y == y) {*rv = curve->p[0]; return TRUE;}
 
174
        sz = seg_size(curve) - 1;
 
175
        seg = il_get_seg(curve,y);
 
176
        if (seg < 0) return FALSE;
 
177
        if (curve->p[seg].y < curve->p[seg+sz].y) { high = 1.0; low = 0.0; }
 
178
        else  { high = 0.0; low = 1.0; }
 
179
        abs_dd = MAXDOUBLE;
 
180
 
 
181
    do {
 
182
        t = (high + low) / 2.0;
 
183
        p = Bezier(&(curve->p[seg]),sz,t,NIL(ilcoord_t *),NIL(ilcoord_t *));
 
184
                d = p.y - y;
 
185
                abs_d = fabs(d);
 
186
                if (abs_d < abs_dd) {q = p; abs_dd = abs_d;}
 
187
                if (d > 0) high = t;
 
188
                else low = t;
 
189
    } while (fabs(high - low) > .01); /* should be adaptive */
 
190
        *rv = q;
 
191
        return TRUE;
 
192
}