Graphviz  2.41.20170921.2350
info.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 <stdio.h>
16 #include "mem.h"
17 #include "info.h"
18 
19 
20 Info_t *nodeInfo; /* Array of node info */
21 static Freelist pfl;
22 
23 void infoinit()
24 {
25  freeinit(&pfl, sizeof(PtItem));
26 }
27 
28 /* compare:
29  * returns -1 if p < q
30  * 0 if p = q
31  * 1 if p > q
32  * if q if NULL, returns -1
33  * Ordering is by angle from -pi/2 to 3pi/4.
34  * For equal angles (which should not happen in our context)
35  * ordering is by closeness to origin.
36  */
37 static int compare(Point * o, PtItem * p, PtItem * q)
38 {
39  double x0;
40  double y0;
41  double x1;
42  double y1;
43  double a, b;
44 
45  if (q == NULL)
46  return -1;
47  if ((p->p.x == q->p.x) && (p->p.y == q->p.y))
48  return 0;
49 
50  x0 = ((double) (p->p.x)) - ((double) (o->x));
51  y0 = ((double) (p->p.y)) - ((double) (o->y));
52  x1 = ((double) (q->p.x)) - ((double) (o->x));
53  y1 = ((double) (q->p.y)) - ((double) (o->y));
54  if (x0 >= 0.0) {
55  if (x1 < 0.0)
56  return -1;
57  else if (x0 > 0.0) {
58  if (x1 > 0.0) {
59  a = y1 / x1;
60  b = y0 / x0;
61  if (b < a)
62  return -1;
63  else if (b > a)
64  return 1;
65  else if (x0 < x1)
66  return -1;
67  else
68  return 1;
69  } else { /* x1 == 0.0 */
70  if (y1 > 0.0)
71  return -1;
72  else
73  return 1;
74  }
75  } else { /* x0 == 0.0 */
76  if (x1 > 0.0) {
77  if (y0 <= 0.0)
78  return -1;
79  else
80  return 1;
81  } else { /* x1 == 0.0 */
82  if (y0 < y1) {
83  if (y1 <= 0.0)
84  return 1;
85  else
86  return -1;
87  } else {
88  if (y0 <= 0.0)
89  return -1;
90  else
91  return 1;
92  }
93  }
94  }
95  } else {
96  if (x1 >= 0.0)
97  return 1;
98  else {
99  a = y1 / x1;
100  b = y0 / x0;
101  if (b < a)
102  return -1;
103  else if (b > a)
104  return 1;
105  else if (x0 > x1)
106  return -1;
107  else
108  return 1;
109  }
110  }
111 }
112 
113 #if 0 /* not used */
114 static void printV(PtItem * vp)
115 {
116  if (vp == NULL) {
117  fprintf(stderr, "<empty>\n");
118  return;
119  }
120 
121  while (vp != NULL) {
122  fprintf(stderr, "(%.16f,%.16f)\n", vp->p.x, vp->p.y);
123  vp = vp->next;
124  }
125 }
126 
127 static void error(Info_t * ip, Site * s, double x, double y)
128 {
129  fprintf(stderr,
130  "Unsorted vertex list for site %d (%.16f,%.16f), pt (%f,%f)\n",
131  s->sitenbr, s->coord.x, s->coord.y, x, y);
132  printV(ip->verts);
133 }
134 #endif
135 
136 #if 0 /* not used */
137 static int sorted(Point * origin, PtItem * vp)
138 {
139  PtItem *next;
140 
141  if (vp == NULL)
142  return 1;
143  next = vp->next;
144 
145  while (next != NULL) {
146  if (compare(origin, vp, next) <= 0) {
147  vp = next;
148  next = next->next;
149  } else {
150  fprintf(stderr, "(%.16f,%.16f) > (%.16f,%.16f)\n",
151  vp->p.x, vp->p.y, next->p.x, next->p.y);
152  return 0;
153  }
154  }
155 
156  return 1;
157 
158 }
159 #endif
160 
161 void addVertex(Site * s, double x, double y)
162 {
163  Info_t *ip;
164  PtItem *p;
165  PtItem *curr;
166  PtItem *prev;
167  Point *origin = &(s->coord);
168  PtItem tmp;
169  int cmp;
170 
171  ip = nodeInfo + (s->sitenbr);
172  curr = ip->verts;
173 
174  tmp.p.x = x;
175  tmp.p.y = y;
176 
177  cmp = compare(origin, &tmp, curr);
178  if (cmp == 0)
179  return;
180  else if (cmp < 0) {
181  p = (PtItem *) getfree(&pfl);
182  p->p.x = x;
183  p->p.y = y;
184  p->next = curr;
185  ip->verts = p;
186  return;
187  }
188 
189  prev = curr;
190  curr = curr->next;
191  while ((cmp = compare(origin, &tmp, curr)) > 0) {
192  prev = curr;
193  curr = curr->next;
194  }
195  if (cmp == 0)
196  return;
197  p = (PtItem *) getfree(&pfl);
198  p->p.x = x;
199  p->p.y = y;
200  prev->next = p;
201  p->next = curr;
202 
203  /* This test should be unnecessary */
204  /* if (!sorted(origin,ip->verts)) */
205  /* error (ip,s,x,y); */
206 
207 }
Info_t * nodeInfo
Definition: info.c:20
double y
Definition: geometry.h:27
void * getfree(Freelist *)
Definition: memory.c:62
Definition: site.h:26
double x
Definition: geometry.h:27
void addVertex(Site *s, double x, double y)
Definition: info.c:161
Definition: mem.h:29
Point origin
Definition: geometry.c:18
Definition: info.h:30
void infoinit()
Definition: info.c:23
Definition: grammar.c:79
struct ptitem * next
Definition: info.h:26
Definition: info.h:25
#define NULL
Definition: logic.h:39
Point p
Definition: info.h:27
Definition: geometry.h:26
PtItem * verts
Definition: info.h:35
Point coord
Definition: site.h:27
int sitenbr
Definition: site.h:28
void freeinit(Freelist *, int)
Definition: memory.c:43