Graphviz 14.0.2~dev.20251008.0253
Loading...
Searching...
No Matches
edges.c
Go to the documentation of this file.
1/*************************************************************************
2 * Copyright (c) 2011 AT&T Intellectual Property
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * https://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors: Details at https://graphviz.org
9 *************************************************************************/
10
11#include <assert.h>
12#include <neatogen/neato.h>
13#include <neatogen/info.h>
14#include <neatogen/edges.h>
15#include <math.h>
16#include <stddef.h>
17#include <util/arena.h>
18
19double pxmin, pxmax, pymin, pymax; /* clipping window */
20
21Edge *gvbisect(Site *s1, Site *s2, arena_t *allocator) {
22 assert(allocator != NULL);
23 double dx, dy, adx, ady;
24 Edge *newedge = ARENA_NEW(allocator, Edge);
25
26 newedge->reg[0] = s1;
27 newedge->reg[1] = s2;
28 newedge->ep[0] = NULL;
29 newedge->ep[1] = NULL;
30
31 dx = s2->coord.x - s1->coord.x;
32 dy = s2->coord.y - s1->coord.y;
33 adx = fabs(dx);
34 ady = fabs(dy);
35 newedge->c =
36 s1->coord.x * dx + s1->coord.y * dy + (dx * dx + dy * dy) * 0.5;
37 if (adx > ady) {
38 newedge->a = 1.0;
39 newedge->b = dy / dx;
40 newedge->c /= dx;
41 } else {
42 newedge->b = 1.0;
43 newedge->a = dx / dy;
44 newedge->c /= dy;
45 }
46
47 return newedge;
48}
49
50
51static void doSeg(Edge * e, double x1, double y1, double x2, double y2)
52{
53 addVertex(e->reg[0], x1, y1);
54 addVertex(e->reg[0], x2, y2);
55 addVertex(e->reg[1], x1, y1);
56 addVertex(e->reg[1], x2, y2);
57}
58
59void clip_line(Edge * e)
60{
61 Site *s1, *s2;
62 double x1, x2, y1, y2;
63
64 if (e->a == 1.0 && e->b >= 0.0) {
65 s1 = e->ep[1];
66 s2 = e->ep[0];
67 } else {
68 s1 = e->ep[0];
69 s2 = e->ep[1];
70 }
71
72 if (e->a == 1.0) {
73 if (s1 != NULL) {
74 y1 = s1->coord.y;
75 if (y1 > pymax)
76 return;
77 else if (y1 >= pymin)
78 x1 = s1->coord.x;
79 else {
80 y1 = pymin;
81 x1 = e->c - e->b * y1;
82 }
83 } else {
84 y1 = pymin;
85 x1 = e->c - e->b * y1;
86 }
87
88 if (s2 != NULL) {
89 y2 = s2->coord.y;
90 if (y2 < pymin)
91 return;
92 else if (y2 <= pymax)
93 x2 = s2->coord.x;
94 else {
95 y2 = pymax;
96 x2 = e->c - e->b * y2;
97 }
98 } else {
99 y2 = pymax;
100 x2 = e->c - e->b * y2;
101 }
102
103 if ((x1 > pxmax && x2 > pxmax) || (x1 < pxmin && x2 < pxmin))
104 return;
105 if (x1 > pxmax) {
106 x1 = pxmax;
107 y1 = (e->c - x1) / e->b;
108 }
109 if (x1 < pxmin) {
110 x1 = pxmin;
111 y1 = (e->c - x1) / e->b;
112 }
113 if (x2 > pxmax) {
114 x2 = pxmax;
115 y2 = (e->c - x2) / e->b;
116 }
117 if (x2 < pxmin) {
118 x2 = pxmin;
119 y2 = (e->c - x2) / e->b;
120 }
121 } else {
122 if (s1 != NULL) {
123 x1 = s1->coord.x;
124 if (x1 > pxmax)
125 return;
126 else if (x1 >= pxmin)
127 y1 = s1->coord.y;
128 else {
129 x1 = pxmin;
130 y1 = e->c - e->a * x1;
131 }
132 } else {
133 x1 = pxmin;
134 y1 = e->c - e->a * x1;
135 }
136
137 if (s2 != NULL) {
138 x2 = s2->coord.x;
139 if (x2 < pxmin)
140 return;
141 else if (x2 <= pxmax)
142 y2 = s2->coord.y;
143 else {
144 x2 = pxmax;
145 y2 = e->c - e->a * x2;
146 }
147 } else {
148 x2 = pxmax;
149 y2 = e->c - e->a * x2;
150 }
151
152 if ((y1 > pymax && y2 > pymax) || (y1 < pymin && y2 < pymin))
153 return;
154 if (y1 > pymax) {
155 y1 = pymax;
156 x1 = (e->c - y1) / e->a;
157 }
158 if (y1 < pymin) {
159 y1 = pymin;
160 x1 = (e->c - y1) / e->a;
161 }
162 if (y2 > pymax) {
163 y2 = pymax;
164 x2 = (e->c - y2) / e->a;
165 }
166 if (y2 < pymin) {
167 y2 = pymin;
168 x2 = (e->c - y2) / e->a;
169 }
170 }
171
172 doSeg(e, x1, y1, x2, y2);
173}
174
175void endpoint(Edge *e, int lr, Site *s, arena_t *allocator) {
176 assert(allocator != NULL);
177 e->ep[lr] = s;
178 if (e->ep[re - lr] == NULL)
179 return;
180 clip_line(e);
181 gv_arena_free(allocator, e, sizeof(*e));
182}
void gv_arena_free(arena_t *arena, void *ptr, size_t size)
Definition arena.c:147
Region-based memory allocator.
#define ARENA_NEW(arena, type)
Definition arena.h:55
static float dy
Definition draw.c:40
static float dx
Definition draw.c:39
static Agedge_t * newedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, IDTYPE id)
Definition edge.c:192
double pymin
Definition edges.c:19
static void doSeg(Edge *e, double x1, double y1, double x2, double y2)
Definition edges.c:51
double pymax
Definition edges.c:19
double pxmin
Definition edges.c:19
void clip_line(Edge *e)
Definition edges.c:59
void endpoint(Edge *e, int lr, Site *s, arena_t *allocator)
Definition edges.c:175
Edge * gvbisect(Site *s1, Site *s2, arena_t *allocator)
Definition edges.c:21
double pxmax
Definition edges.c:19
#define re
Definition edges.h:30
node NULL
Definition grammar.y:181
void addVertex(Site *s, double x, double y)
insert vertex into sorted list
Definition info.c:101
NEATOPROCS_API void s1(graph_t *, node_t *)
Definition stuff.c:663
Definition edges.h:23
Site * ep[2]
Definition edges.h:25
double b
Definition edges.h:24
double c
Definition edges.h:24
Site * reg[2]
Definition edges.h:26
double a
Definition edges.h:24
double x
Definition geometry.h:24
double y
Definition geometry.h:24
Definition site.h:23
Point coord
Definition site.h:24
Definition grammar.c:90