← Back to branch summary

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

« back to all changes in this revision

Viewing changes to dotneato/neatogen/intersect.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:
dotneato/neatogen/intersect.c
 
1
/*
 
2
    This software may only be used by you under license from AT&T Corp.
 
3
    ("AT&T").  A copy of AT&T's Source Code Agreement is available at
 
4
    AT&T's Internet website having the URL:
 
5
    <http://www.research.att.com/sw/tools/graphviz/license/source.html>
 
6
    If you received this software without first entering into a license
 
7
    with AT&T, you have an infringing copy of this software and cannot use
 
8
    it without violating AT&T's intellectual property rights.
 
9
*/
 
10
#pragma prototyped
 
11
#include "neato.h"
 
12
#include "simple.h"
 
13
 
 
14
#ifdef DMALLOC
 
15
#include "dmalloc.h"
 
16
#endif
 
17
 
 
18
static void
 
19
sgnarea(l,m,i) struct vertex *l,*m; int i[];
 
20
        /* find the sign of the area of each of the triangles
 
21
                formed by adding a vertex of m to l     
 
22
        also find the sign of their product     */
 
23
{       float a,b,c,d,e,f,g,h,t;
 
24
        a = l->pos.x; b = l->pos.y;
 
25
        c = after(l)->pos.x - a; d = after(l)->pos.y - b;
 
26
        e = m->pos.x - a ; f = m->pos.y - b ;
 
27
        g = after(m)->pos.x - a; h = after(m)->pos.y - b ;
 
28
        t = (c*f) - (d*e); i[0] = ((t == 0)?0:(t>0?1:-1));
 
29
        t = (c*h) - (d*g); i[1] = ((t == 0)?0:(t>0?1:-1));
 
30
        i[2] = i[0]*i[1];
 
31
}
 
32
 
 
33
static int
 
34
between(f,g,h)  /* determine if g lies between f and h  */
 
35
float f,g,h;
 
36
{       if((f==g)||(g==h)) return(0); return((f<g)?(g<h?1:-1): (h<g?1:-1)); }
 
37
 
 
38
static int
 
39
online(l,m,i)   /* determine if vertex i of line m is on line l */
 
40
struct vertex *l,*m; 
 
41
int i;
 
42
{       struct position a,b,c;
 
43
        a = l->pos; b = after(l)->pos; c = (i == 0) ? m->pos : after(m)->pos ;
 
44
        return((a.x == b.x) ? ((a.x == c.x) && (-1 != between(a.y,c.y,b.y))) : 
 
45
                        between(a.x,c.x,b.x));
 
46
}
 
47
 
 
48
static int
 
49
intpoint(l,m,x,y,cond)
 
50
struct vertex *l,*m;     
 
51
float *x,*y;
 
52
int cond; /* determine point of detected intersections  */ 
 
53
{       struct position ls,le,ms,me,pt1,pt2;
 
54
        float m1,m2,c1,c2;
 
55
 
 
56
        if (cond <= 0) return(0);
 
57
        ls = l->pos ; le = after(l)->pos ;
 
58
        ms = m->pos ; me = after(m)->pos;
 
59
 
 
60
        switch(cond)    {
 
61
 
 
62
        case 3:      /* a simple intersection        */
 
63
                if (ls.x == le.x)   
 
64
                   {  *x = ls.x; *y = me.y + SLOPE(ms,me) * (*x - me.x); }
 
65
                else if (ms.x == me.x)   
 
66
                   {  *x = ms.x; *y = le.y + SLOPE(ls,le) * (*x - le.x); }
 
67
                else 
 
68
                 {  m1 = SLOPE(ms,me); m2 = SLOPE(ls,le);
 
69
                    c1 = ms.y - (m1*ms.x); c2 = ls.y - (m2*ls.x);
 
70
                    *x = (c2-c1)/(m1-m2); *y = ((m1*c2) -(c1*m2))/(m1-m2); }
 
71
                break;
 
72
 
 
73
        case 2:     /*     the two lines  have a common segment  */
 
74
                if (online(l,m,0) == -1)  /* ms between ls and le */
 
75
                {  pt1 = ms;
 
76
                   pt2 = (online(m,l,1) == -1)?((online(m,l,0) == -1)?le:ls):me;
 
77
                }
 
78
                else if (online(l,m,1) == -1)   /* me between ls and le */
 
79
                { pt1 = me ;
 
80
                  pt2 = (online(l,m,0) == -1)?((online(m,l,0) == -1)?le:ls):ms;}
 
81
                else  {
 
82
                        /* may be degenerate? */
 
83
                        if (online(m,l,0) != -1) return 0;
 
84
                        pt1 = ls; pt2 = le;
 
85
                }
 
86
 
 
87
                *x = (pt1.x + pt2.x)/2; *y = (pt1.y + pt2.y)/2;
 
88
                break;
 
89
 
 
90
        case 1:   /* a vertex of line m is on line l */
 
91
                if ((ls.x-le.x)*(ms.y-ls.y) == (ls.y-le.y)*(ms.x-ls.x))
 
92
                        { *x = ms.x; *y = ms.y; }
 
93
                else    { *x = me.x; *y = me.y; }
 
94
        }/* end switch  */
 
95
        return(1);
 
96
}
 
97
 
 
98
  /*detect whether lines l and m intersect      */
 
99
void
 
100
find_intersection(struct vertex *l,
 
101
                  struct vertex *m,
 
102
                  struct intersection ilist[],
 
103
                  struct data *input)
 
104
{       float x,y; 
 
105
        int i[3]; 
 
106
        sgnarea(l,m,i);
 
107
 
 
108
        if (i[2] > 0) return;
 
109
 
 
110
        if (i[2] < 0)   {
 
111
            sgnarea(m,l,i);
 
112
            if (i[2] > 0) return;
 
113
            if (!intpoint(l,m,&x,&y,(i[2]<0)?3:online(m,l,ABS(i[0])))) return; }
 
114
 
 
115
        else if (!intpoint(l,m,&x,&y,(i[0] == i[1])? 
 
116
                2*MAX(online(l,m,0),online(l,m,1)) : online(l,m,ABS(i[0]))))
 
117
                        return;
 
118
 
 
119
        if (input->ninters >= MAXINTS)  {
 
120
                fprintf(stderr,"\n**ERROR**\n using too many intersections\n");
 
121
                exit(1);                }
 
122
 
 
123
        ilist[input->ninters].firstv  = l;
 
124
        ilist[input->ninters].secondv = m;
 
125
        ilist[input->ninters].firstp  = l->poly;
 
126
        ilist[input->ninters].secondp = m->poly;
 
127
        ilist[input->ninters].x = x;
 
128
        ilist[input->ninters].y = y;
 
129
        input->ninters++;
 
130
}
 
131