Graphviz  2.41.20170921.2350
geometry.c
Go to the documentation of this file.
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;
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 }
double xmax
Definition: geometry.c:20
double deltax
Definition: geometry.c:21
double y
Definition: geometry.h:27
double xmin
Definition: geometry.c:20
double ymax
Definition: geometry.c:20
double x
Definition: geometry.h:27
double ymin
Definition: geometry.c:20
double deltay
Definition: geometry.c:21
int sqrt_nsites
Definition: geometry.c:25
int
Definition: grammar.c:1264
int leftOf(Point a, Point b, Point c)
Definition: geometry.c:62
Point origin
Definition: geometry.c:18
double dist_2(Point *pp, Point *qp)
Definition: geometry.c:37
Definition: grammar.c:79
double area_2(Point a, Point b, Point c)
Definition: geometry.c:57
void addpt(Point *c, Point a, Point b)
Definition: geometry.c:51
void geominit()
Definition: geometry.c:27
void subpt(Point *a, Point b, Point c)
Definition: geometry.c:45
int nsites
Definition: geometry.c:24
Definition: geometry.h:26
int intersection(Point a, Point b, Point c, Point d, Point *p)
Definition: geometry.c:67