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
18Point origin = { 0, 0 };
19
20double xmin, xmax, ymin, ymax; /* min and max x and y values of sites */
21double deltax, /* xmax - xmin */
22 deltay; /* ymax - ymin */
23
24int nsites;
25int sqrt_nsites;
26
27void 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
37double 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
45void subpt(Point * a, Point b, Point c)
46{
47 a->x = b.x - c.x;
48 a->y = b.y - c.y;
49}
50
51void addpt(Point * c, Point a, Point b)
52{
53 c->x = a.x + b.x;
54 c->y = a.y + b.y;
55}
56
57double 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
62int leftOf(Point a, Point b, Point c)
63{
64 return (area_2(a, b, c) > 0);
65}
66
67int 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