1 | /* $Id$ $Revision$ */ |
2 | /* vim:set shiftwidth=4 ts=8: */ |
3 | |
4 | /************************************************************************* |
5 | * Copyright (c) 2011 AT&T Intellectual Property |
6 | * All rights reserved. This program and the accompanying materials |
7 | * are made available under the terms of the Eclipse Public License v1.0 |
8 | * which accompanies this distribution, and is available at |
9 | * http://www.eclipse.org/legal/epl-v10.html |
10 | * |
11 | * Contributors: See CVS logs. Details at http://www.graphviz.org/ |
12 | *************************************************************************/ |
13 | |
14 | #include "geometry.h" |
15 | #include <math.h> |
16 | |
17 | |
18 | Point origin = { 0, 0 }; |
19 | |
20 | double xmin, xmax, ymin, ymax; /* min and max x and y values of sites */ |
21 | double deltax, /* xmax - xmin */ |
22 | deltay; /* ymax - ymin */ |
23 | |
24 | int nsites; |
25 | int sqrt_nsites; |
26 | |
27 | void geominit() |
28 | { |
29 | double sn; |
30 | |
31 | sn = nsites + 4; |
32 | sqrt_nsites = (int) sqrt(sn); |
33 | /* deltay = ymax - ymin; */ |
34 | /* deltax = xmax - xmin; */ |
35 | } |
36 | |
37 | double dist_2(Point * pp, Point * qp) |
38 | { |
39 | double dx = pp->x - qp->x; |
40 | double dy = pp->y - qp->y; |
41 | |
42 | return (dx * dx + dy * dy); |
43 | } |
44 | |
45 | void subpt(Point * a, Point b, Point c) |
46 | { |
47 | a->x = b.x - c.x; |
48 | a->y = b.y - c.y; |
49 | } |
50 | |
51 | void addpt(Point * c, Point a, Point b) |
52 | { |
53 | c->x = a.x + b.x; |
54 | c->y = a.y + b.y; |
55 | } |
56 | |
57 | double area_2(Point a, Point b, Point c) |
58 | { |
59 | return ((a.y - b.y) * (c.x - b.x) - (c.y - b.y) * (a.x - b.x)); |
60 | } |
61 | |
62 | int leftOf(Point a, Point b, Point c) |
63 | { |
64 | return (area_2(a, b, c) > 0); |
65 | } |
66 | |
67 | int intersection(Point a, Point b, Point c, Point d, Point * p) |
68 | { |
69 | double s, t; /* The two parameters of the parametric eqns. */ |
70 | double denom; /* Denominator of solutions. */ |
71 | |
72 | denom = |
73 | a.x * (d.y - c.y) + |
74 | b.x * (c.y - d.y) + d.x * (b.y - a.y) + c.x * (a.y - b.y); |
75 | |
76 | /* If denom is zero, then the line segments are parallel. */ |
77 | /* In this case, return false even though the segments might overlap. */ |
78 | if (denom == 0.0) |
79 | return 0; |
80 | |
81 | s = (a.x * (d.y - c.y) + c.x * (a.y - d.y) + d.x * (c.y - a.y) |
82 | ) / denom; |
83 | t = -(a.x * (c.y - b.y) + b.x * (a.y - c.y) + c.x * (b.y - a.y) |
84 | ) / denom; |
85 | |
86 | p->x = a.x + s * (b.x - a.x); |
87 | p->y = a.y + s * (b.y - a.y); |
88 | |
89 | if ((0.0 <= s) && (s <= 1.0) && (0.0 <= t) && (t <= 1.0)) |
90 | return 1; |
91 | else |
92 | return 0; |
93 | } |
94 | |