1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
/*************************************************************************
* Copyright (c) 2011 AT&T Intellectual Property
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
* https://www.eclipse.org/legal/epl-v10.html
*
* Contributors: Details at https://graphviz.org
*************************************************************************/
#include <neatogen/neato.h>
#include <stdio.h>
#include <neatogen/info.h>
#include <stddef.h>
#include <util/alloc.h>
Info_t *nodeInfo; /* Array of node info */
/* returns -1 if p < q.p
* 0 if p = q.p
* 1 if p > q.p
* if q if NULL, returns -1
* Ordering is by angle from -pi/2 to 3pi/4.
* For equal angles (which should not happen in our context)
* ordering is by closeness to origin.
*/
static int compare(Point o, Point p, Point q) {
double x0;
double y0;
double x1;
double y1;
double a, b;
if (p.x == q.x && p.y == q.y)
return 0;
x0 = (double)p.x - (double)o.x;
y0 = (double)p.y - (double)o.y;
x1 = (double)q.x - (double)o.x;
y1 = (double)q.y - (double)o.y;
if (x0 >= 0.0) {
if (x1 < 0.0)
return -1;
else if (x0 > 0.0) {
if (x1 > 0.0) {
a = y1 / x1;
b = y0 / x0;
if (b < a)
return -1;
else if (b > a)
return 1;
else if (x0 < x1)
return -1;
else
return 1;
} else { /* x1 == 0.0 */
if (y1 > 0.0)
return -1;
else
return 1;
}
} else { /* x0 == 0.0 */
if (x1 > 0.0) {
if (y0 <= 0.0)
return -1;
else
return 1;
} else { /* x1 == 0.0 */
if (y0 < y1) {
if (y1 <= 0.0)
return 1;
else
return -1;
} else {
if (y0 <= 0.0)
return -1;
else
return 1;
}
}
}
} else {
if (x1 >= 0.0)
return 1;
else {
a = y1 / x1;
b = y0 / x0;
if (b < a)
return -1;
else if (b > a)
return 1;
else if (x0 > x1)
return -1;
else
return 1;
}
}
}
void addVertex(Site * s, double x, double y)
{
Info_t *ip;
const Point origin_point = s->coord;
ip = nodeInfo + s->sitenbr;
const Point tmp = {.x = x, .y = y};
size_t i;
for (i = 0; i < ip->n_verts; ++i) {
int cmp = compare(origin_point, tmp, ip->verts[i]);
if (cmp == 0) { // we already know this vertex; ignore
return;
}
if (cmp < 0) { // found where to insert this vertex
break;
}
}
ip->verts = gv_recalloc(ip->verts, ip->n_verts, ip->n_verts + 1,
sizeof(ip->verts[0]));
// shuffle existing entries upwards to make room
memmove(&ip->verts[i + 1], &ip->verts[i],
(ip->n_verts - i) * sizeof(ip->verts[0]));
ip->verts[i] = tmp;
++ip->n_verts;
}
|
