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
21double pxmin, pxmax, pymin, pymax; /* clipping window */
22
23static int nedges;
24static Freelist efl;
25
26void edgeinit()
27{
28 freeinit(&efl, sizeof(Edge));
29 nedges = 0;
30}
31
32Edge *gvbisect(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
71static 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
79void 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
199void 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}
213