← Back to branch summary

~ubuntu-branches/ubuntu/lucid/graphviz/lucid-updates

« back to all changes in this revision

Viewing changes to lib/utilities/intersect.c

  • Committer: Bazaar Package Importer
  • Author(s): Bryce Harrington
  • Date: 2008-06-19 20:23:23 UTC
  • mfrom: (1.2.5 upstream)
  • Revision ID: james.westby@ubuntu.com-20080619202323-ls23h96ntj9ny94m
Tags: 2.18-1ubuntu1
https://launchpad.net/bugs/174749
* Merge from debian unstable, remaining changes:
  - Build depend on liblualib50-dev instead of liblua5.1-0-dev.
  - Drop libttf-dev (libttf-dev is in universe) (LP: #174749).
  - Replace gs-common with ghostscript.
  - Build-depend on python-dev instead of python2.4-dev or python2.5-dev.
  - Mention the correct python version for the python bindings in the
    package description.

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/utilities/intersect.c
 
1
#include <math.h>
 
2
 
 
3
typedef struct {
 
4
    double x, y;
 
5
} pointf;
 
6
 
 
7
#define SMALL 0.0000000001
 
8
 
 
9
static pointf
 
10
subPt (pointf a, pointf b)
 
11
{
 
12
    pointf c;
 
13
 
 
14
    c.x = a.x-b.x;
 
15
    c.y = a.y-b.y;
 
16
    return c;
 
17
}
 
18
 
 
19
static pointf
 
20
perp (pointf a)
 
21
{
 
22
    pointf c;
 
23
 
 
24
    c.x = -a.y;
 
25
    c.y = a.x;
 
26
    return c;
 
27
}
 
28
 
 
29
static double
 
30
dot (pointf a, pointf b)
 
31
{
 
32
    return (a.x*b.x + a.y*b.y);
 
33
}
 
34
 
 
35
static pointf
 
36
scale (double c, pointf a)
 
37
{
 
38
    pointf b;
 
39
 
 
40
    b.x = c*a.x;
 
41
    b.y = c*a.y;
 
42
    return b;
 
43
}
 
44
 
 
45
/* intersect:
 
46
 * Computes intersection of lines a-b and c-d, returning intersection
 
47
 * point in *x.
 
48
 * Returns 0 if no intersection (lines parallel), 1 otherwise.
 
49
 */
 
50
int
 
51
intersect (pointf a, pointf b, pointf c, pointf d, pointf* x)
 
52
{
 
53
    pointf mv = subPt (b,a);
 
54
    pointf lv = subPt (d,c);
 
55
    pointf ln = perp (lv);
 
56
    double lc = -dot(ln,c);
 
57
    double dt = dot(ln,mv);
 
58
 
 
59
    if (fabs(dt) < SMALL) return 0;
 
60
 
 
61
    *x = subPt(a,scale((dot(ln,a)+lc)/dt,mv));
 
62
    return 1;
 
63
}
 
64
 
 
65
#ifdef DEBUG
 
66
#include <stdio.h>
 
67
 
 
68
main ()
 
69
{
 
70
    pointf a, b, c, d, x;
 
71
    int ax, ay, bx, by, cx, cy, dx, dy;
 
72
    char buf[1024];
 
73
    while (1) {
 
74
          fflush(stdin);
 
75
      fgets (buf, 1024, stdin);
 
76
      sscanf (buf, "%d %d %d %d", &ax, &ay, &bx, &by);
 
77
           fflush(stdin);
 
78
      fgets (buf, 1024, stdin);
 
79
      sscanf (buf, "%d %d %d %d", &cx, &cy, &dx, &dy);
 
80
      a.x = ax;
 
81
      a.y = ay;
 
82
      b.x = bx;
 
83
      b.y = by;
 
84
      c.x = cx;
 
85
      c.y = cy;
 
86
      d.x = dx;
 
87
      d.y = dy;
 
88
      if (intersect (a,b,c,d,&x))
 
89
                printf ("(%f,%f)\n", x.x,x.y);
 
90
      else
 
91
                printf ("no intersection\n");
 
92
      }
 
93
}
 
94
#endif