Graphviz  2.39.20141219.0545
edges.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 "neato.h"
15 #include "mem.h"
16 #include "info.h"
17 #include "edges.h"
18 #include <math.h>
19 
20 
21 double pxmin, pxmax, pymin, pymax; /* clipping window */
22 
23 static int nedges;
24 static Freelist efl;
25 
26 void edgeinit()
27 {
28  freeinit(&efl, sizeof(Edge));
29  nedges = 0;
30 }
31 
32 Edge *bisect(Site * s1, Site * s2)
33 {
34  double dx, dy, adx, ady;
35  Edge *newedge;
36 
37  newedge = (Edge *) getfree(&efl);
38 
39  newedge->reg[0] = s1;
40  newedge->reg[1] = s2;
41  ref(s1);
42  ref(s2);
43  newedge->ep[0] = (Site *) NULL;
44  newedge->ep[1] = (Site *) NULL;
45 
46  dx = s2->coord.x - s1->coord.x;
47  dy = s2->coord.y - s1->coord.y;
48  adx = dx > 0 ? dx : -dx;
49  ady = dy > 0 ? dy : -dy;
50  newedge->c =
51  s1->coord.x * dx + s1->coord.y * dy + (dx * dx + dy * dy) * 0.5;
52  if (adx > ady) {
53  newedge->a = 1.0;
54  newedge->b = dy / dx;
55  newedge->c /= dx;
56  } else {
57  newedge->b = 1.0;
58  newedge->a = dx / dy;
59  newedge->c /= dy;
60  };
61 
62  newedge->edgenbr = nedges;
63 #ifdef STANDALONE
64  out_bisector(newedge);
65 #endif
66  nedges += 1;
67  return (newedge);
68 }
69 
70 
71 static void doSeg(Edge * e, double x1, double y1, double x2, double y2)
72 {
73  addVertex(e->reg[0], x1, y1);
74  addVertex(e->reg[0], x2, y2);
75  addVertex(e->reg[1], x1, y1);
76  addVertex(e->reg[1], x2, y2);
77 }
78 
79 void clip_line(Edge * e)
80 {
81  Site *s1, *s2;
82  double x1, x2, y1, y2;
83 
84  if (e->a == 1.0 && e->b >= 0.0) {
85  s1 = e->ep[1];
86  s2 = e->ep[0];
87  } else {
88  s1 = e->ep[0];
89  s2 = e->ep[1];
90  }
91 
92  if (e->a == 1.0) {
93  if (s1 != (Site *) NULL) {
94  y1 = s1->coord.y;
95  if (y1 > pymax)
96  return;
97  else if (y1 >= pymin)
98  x1 = s1->coord.x;
99  else {
100  y1 = pymin;
101  x1 = e->c - e->b * y1;
102  }
103  } else {
104  y1 = pymin;
105  x1 = e->c - e->b * y1;
106  }
107 
108  if (s2 != (Site *) NULL) {
109  y2 = s2->coord.y;
110  if (y2 < pymin)
111  return;
112  else if (y2 <= pymax)
113  x2 = s2->coord.x;
114  else {
115  y2 = pymax;
116  x2 = e->c - e->b * y2;
117  }
118  } else {
119  y2 = pymax;
120  x2 = e->c - e->b * y2;
121  }
122 
123  if (((x1 > pxmax) & (x2 > pxmax)) | ((x1 < pxmin) & (x2 < pxmin)))
124  return;
125  if (x1 > pxmax) {
126  x1 = pxmax;
127  y1 = (e->c - x1) / e->b;
128  };
129  if (x1 < pxmin) {
130  x1 = pxmin;
131  y1 = (e->c - x1) / e->b;
132  };
133  if (x2 > pxmax) {
134  x2 = pxmax;
135  y2 = (e->c - x2) / e->b;
136  };
137  if (x2 < pxmin) {
138  x2 = pxmin;
139  y2 = (e->c - x2) / e->b;
140  };
141  } else {
142  if (s1 != (Site *) NULL) {
143  x1 = s1->coord.x;
144  if (x1 > pxmax)
145  return;
146  else if (x1 >= pxmin)
147  y1 = s1->coord.y;
148  else {
149  x1 = pxmin;
150  y1 = e->c - e->a * x1;
151  }
152  } else {
153  x1 = pxmin;
154  y1 = e->c - e->a * x1;
155  }
156 
157  if (s2 != (Site *) NULL) {
158  x2 = s2->coord.x;
159  if (x2 < pxmin)
160  return;
161  else if (x2 <= pxmax)
162  y2 = s2->coord.y;
163  else {
164  x2 = pxmax;
165  y2 = e->c - e->a * x2;
166  }
167  } else {
168  x2 = pxmax;
169  y2 = e->c - e->a * x2;
170  }
171 
172  if (((y1 > pymax) & (y2 > pymax)) | ((y1 < pymin) & (y2 < pymin)))
173  return;
174  if (y1 > pymax) {
175  y1 = pymax;
176  x1 = (e->c - y1) / e->a;
177  };
178  if (y1 < pymin) {
179  y1 = pymin;
180  x1 = (e->c - y1) / e->a;
181  };
182  if (y2 > pymax) {
183  y2 = pymax;
184  x2 = (e->c - y2) / e->a;
185  };
186  if (y2 < pymin) {
187  y2 = pymin;
188  x2 = (e->c - y2) / e->a;
189  };
190  }
191 
192  doSeg(e, x1, y1, x2, y2);
193 #ifdef STANDALONE
194  if (doPS)
195  line(x1, y1, x2, y2);
196 #endif
197 }
198 
199 void endpoint(Edge * e, int lr, Site * s)
200 {
201  e->ep[lr] = s;
202  ref(s);
203  if (e->ep[re - lr] == (Site *) NULL)
204  return;
205  clip_line(e);
206 #ifdef STANDALONE
207  out_ep(e);
208 #endif
209  deref(e->reg[le]);
210  deref(e->reg[re]);
211  makefree(e, &efl);
212 }
void s1(graph_t *, node_t *)
Definition: stuff.c:688
int edgenbr
Definition: edges.h:29
double y
Definition: geometry.h:27
void * getfree(Freelist *)
Definition: memory.c:62
double b
Definition: edges.h:26
Definition: site.h:26
Site * ep[2]
Definition: edges.h:27
Definition: edges.h:25
double x
Definition: geometry.h:27
double pxmax
Definition: edges.c:21
void addVertex(Site *s, double x, double y)
Definition: info.c:161
void makefree(void *, Freelist *)
Definition: memory.c:86
double c
Definition: edges.h:26
#define le
Definition: edges.h:32
Definition: mem.h:29
double a
Definition: edges.h:26
Site * reg[2]
Definition: edges.h:28
#define re
Definition: edges.h:33
Definition: grammar.c:79
Edge * bisect(Site *s1, Site *s2)
Definition: edges.c:32
#define NULL
Definition: logic.h:50
void deref(Site *v)
Definition: site.c:63
void ref(Site *v)
Definition: site.c:70
void clip_line(Edge *e)
Definition: edges.c:79
void endpoint(Edge *e, int lr, Site *s)
Definition: edges.c:199
void edgeinit()
Definition: edges.c:26
Point coord
Definition: site.h:27
double pxmin
Definition: edges.c:21
double pymin
Definition: edges.c:21
double pymax
Definition: edges.c:21
void freeinit(Freelist *, int)
Definition: memory.c:43