1/* vim:set shiftwidth=4 ts=8: */
2
3/*************************************************************************
4 * Copyright (c) 2011 AT&T Intellectual Property
5 * All rights reserved. This program and the accompanying materials
6 * are made available under the terms of the Eclipse Public License v1.0
7 * which accompanies this distribution, and is available at
8 * http://www.eclipse.org/legal/epl-v10.html
9 *
10 * Contributors: See CVS logs. Details at http://www.graphviz.org/
11 *************************************************************************/
12
13#include "config.h"
14
15#include "index.h"
16#include <stdio.h>
17#include <assert.h>
18#include <limits.h>
19#include "logic.h"
20#include "arith.h"
21#include "rectangle.h"
22#include <cgraph.h>
23
24#define Undefined(x) ((x)->boundary[0] > (x)->boundary[NUMDIMS])
25
26extern Rect_t CoverAll;
27
28/*-----------------------------------------------------------------------------
29| Initialize a rectangle to have all 0 coordinates.
30-----------------------------------------------------------------------------*/
31void InitRect(Rect_t * r)
32{
33 register int i;
34 for (i = 0; i < NUMSIDES; i++)
35 r->boundary[i] = 0;
36}
37
38/*-----------------------------------------------------------------------------
39| Return a rect whose first low side is higher than its opposite side -
40| interpreted as an undefined rect.
41-----------------------------------------------------------------------------*/
42Rect_t NullRect()
43{
44 Rect_t r;
45 register int i;
46
47 r.boundary[0] = 1;
48 r.boundary[NUMDIMS] = -1;
49 for (i = 1; i < NUMDIMS; i++)
50 r.boundary[i] = r.boundary[i + NUMDIMS] = 0;
51 return r;
52}
53
54#ifdef UNUSED
55/*-----------------------------------------------------------------------------
56| Fills in random coordinates in a rectangle.
57| The low side is guaranteed to be less than the high side.
58-----------------------------------------------------------------------------*/
59RandomRect(Rect_t * r)
60{
61 register int i, width;
62 for (i = 0; i < NUMDIMS; i++) {
63 /* width from 1 to 1000 / 4, more small ones */
64 width = rand() % (1000 / 4) + 1;
65
66 /* sprinkle a given size evenly but so they stay in [0,100] */
67 r->boundary[i] = rand() % (1000 - width); /* low side */
68 r->boundary[i + NUMDIMS] = r->boundary[i] + width; /* high side */
69 }
70}
71
72/*-----------------------------------------------------------------------------
73| Fill in the boundaries for a random search rectangle.
74| Pass in a pointer to a rect that contains all the data,
75| and a pointer to the rect to be filled in.
76| Generated rect is centered randomly anywhere in the data area,
77| and has size from 0 to the size of the data area in each dimension,
78| i.e. search rect can stick out beyond data area.
79-----------------------------------------------------------------------------*/
80SearchRect(Rect_t * search, Rect_t * data)
81{
82 register int i, j, size, center;
83
84 assert(search);
85 assert(data);
86
87 for (i = 0; i < NUMDIMS; i++) {
88 j = i + NUMDIMS; /* index for high side boundary */
89 if (data->boundary[i] > INT_MIN && data->boundary[j] < INT_MAX) {
90 size =
91 (rand() % (data->boundary[j] - data->boundary[i] + 1)) / 2;
92 center = data->boundary[i]
93 + rand() % (data->boundary[j] - data->boundary[i] + 1);
94 search->boundary[i] = center - size / 2;
95 search->boundary[j] = center + size / 2;
96 } else { /* some open boundary, search entire dimension */
97 search->boundary[i] = INT_MIN;
98 search->boundary[j] = INT_MAX;
99 }
100 }
101}
102#endif
103
104#ifdef RTDEBUG
105/*-----------------------------------------------------------------------------
106| Print rectangle lower upper bounds by dimension
107-----------------------------------------------------------------------------*/
108void PrintRect(Rect_t * r)
109{
110 register int i;
111 assert(r);
112 fprintf(stderr, "rect:");
113 for (i = 0; i < NUMDIMS; i++)
114 fprintf(stderr, "\t%d\t%d\n", r->boundary[i],
115 r->boundary[i + NUMDIMS]);
116}
117#endif
118
119/*-----------------------------------------------------------------------------
120| Calculate the n-dimensional area of a rectangle
121-----------------------------------------------------------------------------*/
122
123#if LLONG_MAX > UINT_MAX
124unsigned int RectArea(Rect_t * r)
125{
126 register int i;
127 unsigned int area;
128 assert(r);
129
130 if (Undefined(r))
131 return 0;
132
133 /*
134 * XXX add overflow checks
135 */
136 area = 1;
137 for (i = 0; i < NUMDIMS; i++) {
138 long long a_test = area * r->boundary[i + NUMDIMS] - r->boundary[i];
139 if( a_test > UINT_MAX) {
140 agerr (AGERR, "label: area too large for rtree\n");
141 return UINT_MAX;
142 }
143 area = a_test;
144 }
145 return area;
146}
147#else
148unsigned int RectArea(Rect_t * r)
149{
150 register int i;
151 unsigned int area=1, a=1;
152 assert(r);
153
154 if (Undefined(r)) return 0;
155
156 /*
157 * XXX add overflow checks
158 */
159 area = 1;
160 for (i = 0; i < NUMDIMS; i++) {
161 unsigned int b = r->boundary[i + NUMDIMS] - r->boundary[i];
162 a *= b;
163 if( (a / b ) != area) {
164 agerr (AGERR, "label: area too large for rtree\n");
165 return UINT_MAX;
166 }
167 area = a;
168 }
169 return area;
170}
171#endif /*LLONG_MAX > UINT_MAX*/
172#if 0 /*original code*/
173int RectArea(Rect_t * r)
174{
175 register int i, area=1;
176 assert(r);
177
178 if (Undefined(r))
179 return 0;
180 area = 1;
181 for (i = 0; i < NUMDIMS; i++) {
182 area *= r->boundary[i + NUMDIMS] - r->boundary[i];
183 }
184 return area;
185}
186#endif
187
188/*-----------------------------------------------------------------------------
189| Combine two rectangles, make one that includes both.
190-----------------------------------------------------------------------------*/
191Rect_t CombineRect(Rect_t * r, Rect_t * rr)
192{
193 register int i, j;
194 Rect_t new;
195 assert(r && rr);
196
197 if (Undefined(r))
198 return *rr;
199 if (Undefined(rr))
200 return *r;
201
202 for (i = 0; i < NUMDIMS; i++) {
203 new.boundary[i] = MIN(r->boundary[i], rr->boundary[i]);
204 j = i + NUMDIMS;
205 new.boundary[j] = MAX(r->boundary[j], rr->boundary[j]);
206 }
207 return new;
208}
209
210/*-----------------------------------------------------------------------------
211| Decide whether two rectangles overlap.
212-----------------------------------------------------------------------------*/
213int Overlap(Rect_t * r, Rect_t * s)
214{
215 register int i, j;
216 assert(r && s);
217
218 for (i = 0; i < NUMDIMS; i++) {
219 j = i + NUMDIMS; /* index for high sides */
220 if (r->boundary[i] > s->boundary[j]
221 || s->boundary[i] > r->boundary[j])
222 return FALSE;
223 }
224 return TRUE;
225}
226
227/*-----------------------------------------------------------------------------
228| Decide whether rectangle r is contained in rectangle s.
229-----------------------------------------------------------------------------*/
230int Contained(Rect_t * r, Rect_t * s)
231{
232 register int i, j, result;
233 assert(r && s);
234
235 /* undefined rect is contained in any other */
236 if (Undefined(r))
237 return TRUE;
238 /* no rect (except an undefined one) is contained in an undef rect */
239 if (Undefined(s))
240 return FALSE;
241
242 result = TRUE;
243 for (i = 0; i < NUMDIMS; i++) {
244 j = i + NUMDIMS; /* index for high sides */
245 result = result && r->boundary[i] >= s->boundary[i]
246 && r->boundary[j] <= s->boundary[j];
247 }
248 return result;
249}
250