1 /*
2 * Copyright (C) 1988-1991 Yale University
3 *
4 * This work is distributed in the hope that it will be useful; you can
5 * redistribute it and/or modify it under the terms of the
6 * GNU General Public License as published by the Free Software Foundation;
7 * either version 2 of the License,
8 * or any later version, on the following conditions:
9 *
10 * (a) YALE MAKES NO, AND EXPRESSLY DISCLAIMS
11 * ALL, REPRESENTATIONS OR WARRANTIES THAT THE MANUFACTURE, USE, PRACTICE,
12 * SALE OR
13 * OTHER DISPOSAL OF THE SOFTWARE DOES NOT OR WILL NOT INFRINGE UPON ANY
14 * PATENT OR
15 * OTHER RIGHTS NOT VESTED IN YALE.
16 *
17 * (b) YALE MAKES NO, AND EXPRESSLY DISCLAIMS ALL, REPRESENTATIONS AND
18 * WARRANTIES
19 * WHATSOEVER WITH RESPECT TO THE SOFTWARE, EITHER EXPRESS OR IMPLIED,
20 * INCLUDING,
21 * BUT NOT LIMITED TO, WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A
22 * PARTICULAR
23 * PURPOSE.
24 *
25 * (c) LICENSEE SHALL MAKE NO STATEMENTS, REPRESENTATION OR WARRANTIES
26 * WHATSOEVER TO
27 * ANY THIRD PARTIES THAT ARE INCONSISTENT WITH THE DISCLAIMERS BY YALE IN
28 * ARTICLE
29 * (a) AND (b) above.
30 *
31 * (d) IN NO EVENT SHALL YALE, OR ITS TRUSTEES, DIRECTORS, OFFICERS,
32 * EMPLOYEES AND
33 * AFFILIATES BE LIABLE FOR DAMAGES OF ANY KIND, INCLUDING ECONOMIC DAMAGE OR
34 * INJURY TO PROPERTY AND LOST PROFITS, REGARDLESS OF WHETHER YALE SHALL BE
35 * ADVISED, SHALL HAVE OTHER REASON TO KNOW, OR IN FACT SHALL KNOW OF THE
36 * POSSIBILITY OF THE FOREGOING.
37 *
38 */
39
40 /* -----------------------------------------------------------------
41 FILE: buster.c
42 DESCRIPTION:This file contains the utility routine to break a
43 rectilinear cell up into tiles.
44 CONTENTS: YBUSTBOXPTR Ybuster()
45 INT Ybuster_init() ;
46 INT Ybuster_addpt( x, y ) ;
47 void Ybuster_free() ;
48 void Ybuster_clear() ;
49 INT x, y ;
50 DATE: Aug 7, 1988 - rewrote to match new parser.
51 REVISIONS: May 1, 1990 - made sure we cannot match the 0
52 record in the redundancy check for points.
53 May 4, 1990 - moved to the library since it now occurs
54 in many files.
55 Aug 23,1990 - added Ybuster_free, Ybuster_clear.
56 Sat Dec 15 22:55:53 EST 1990 - added debug_verify
57 code to buster.
58 Wed Apr 17 23:39:20 EDT 1991 - rewrote buster verify
59 for more extensive error checking.
60 Thu Oct 17 11:08:18 EDT 1991 - added buster_chcek_rect.
61 ----------------------------------------------------------------- */
62
63 #include <yalecad/base.h>
64 #include <yalecad/buster.h>
65 #include <yalecad/debug.h>
66 #include <yalecad/message.h>
67
68 #define EXPECTEDPTS 50
69 /* detect problems with clockwise rotation pattern */
70 #define E_STATE 0
71 #define U_STATE 1
72 #define L_STATE 2
73 #define R_STATE 3
74 #define D_STATE 4
75 #define S_STATE 5 /* start state */
76
77 /* ####################### STATIC definitions ######################### */
78 static INT cornerCountS ; /* current number of corners */
79 static INT ptAllocS = 0 ; /* current allocation for pts */
80 static YBUSTBOXPTR ptS = NIL(YBUSTBOXPTR) ;/* array of pts for boundary */
81 static YBUSTBOXPTR resultS; /* the array of pts to break into tiles */
82 static INT cur_stateS ; /* current state direction of edge */
83 static char *user_messageS; /* output message on error */
84 /* ################## END STATIC definitions ########################## */
85 static BOOL check_rect( P4(INT xx1, INT yy1, INT xx2, INT yy2 ) ) ;
86 BOOL Ybuster_check_rect(INT xx1, INT yy1, INT xx2, INT yy2 );
87
Ybuster()88 YBUSTBOXPTR Ybuster()
89 {
90
91 INT k , Pk[2] , Pl[2] , Pm[2] ;
92 INT xmin , ymin , kmin , found ;
93
94 if( cornerCountS <= 0 ){
95 return( NIL(YBUSTBOXPTR) ) ;
96 }
97 D( "Ybuster/debug", Ybuster_verify( NULL ) ; ) ;
98
99 /* find Pk */
100 ymin = INT_MAX ;
101 for( k = 1 ; k <= cornerCountS ; k++ ) {
102 if( ptS[k].y < ymin ) {
103 ymin = ptS[k].y ;
104 }
105 } /* we have the lowest y coordinate */
106 xmin = INT_MAX ;
107 for( k = 1 ; k <=cornerCountS ; k++ ) {
108 if( ptS[k].y == ymin ) {
109 if( ptS[k].x < xmin ) {
110 xmin = ptS[k].x ;
111 kmin = k ;
112 }
113 }
114 } /* we have the leftmost lowest corner */
115 Pk[0] = xmin ;
116 Pk[1] = ymin ;
117 xmin = INT_MAX ;
118 for( k = 1 ; k <= cornerCountS ; k++ ) {
119 if( k == kmin ) {
120 continue ;
121 }
122 if( ptS[k].y == ymin ) {
123 if( ptS[k].x < xmin ) {
124 xmin = ptS[k].x ;
125 }
126 }
127 } /* we have the next leftmost lowest corner */
128 Pl[0] = xmin ;
129 Pl[1] = ymin ;
130 ymin = INT_MAX ;
131 for( k = 1 ; k <= cornerCountS ; k++ ) {
132 if( ptS[k].y == Pk[1] ) {
133 continue ;
134 }
135 if( ptS[k].y < ymin ) {
136 ymin = ptS[k].y ;
137 }
138 } /* we have the next lowest y coordinate */
139 xmin = INT_MAX ;
140 for( k = 1 ; k <= cornerCountS ; k++ ) {
141 if( ptS[k].y == ymin ) {
142 if( ptS[k].x < Pk[0] || ptS[k].x > Pl[0] ) {
143 continue ;
144 }
145 if( ptS[k].x < xmin ) {
146 xmin = ptS[k].x ;
147 }
148 }
149 } /* we have the leftmost next lowest corner */
150 Pm[0] = xmin ;
151 Pm[1] = ymin ;
152
153 /*
154 * According to the instruction sheet I read, we can
155 * output the bounding rectangle of Pk , Pl , Pm.
156 */
157 resultS[1].x = Pk[0] ;
158 resultS[1].y = Pk[1] ;
159 resultS[2].x = Pk[0] ;
160 resultS[2].y = Pm[1] ;
161 resultS[3].x = Pl[0] ;
162 resultS[3].y = Pm[1] ;
163 resultS[4].x = Pl[0] ;
164 resultS[4].y = Pk[1] ;
165
166 /*
167 * Now weed out those elements of R which are in A and
168 * add those elements of R which are not in A.
169 * Note that index 1 and 4 are necessarily in A, and thus
170 * have to be removed from A.
171 */
172 for( k = 1 ; k <= cornerCountS ; k++ ) {
173 if( resultS[1].x == ptS[k].x && resultS[1].y == ptS[k].y ) {
174 ptS[k].x = ptS[ cornerCountS ].x ;
175 ptS[k].y = ptS[ cornerCountS-- ].y ;
176 break ;
177 }
178 }
179 for( k = 1 ; k <= cornerCountS ; k++ ) {
180 if( resultS[4].x == ptS[k].x && resultS[4].y == ptS[k].y ) {
181 ptS[k].x = ptS[ cornerCountS ].x ;
182 ptS[k].y = ptS[ cornerCountS-- ].y ;
183 break ;
184 }
185 }
186 found = 0 ;
187 for( k = 1 ; k <= cornerCountS ; k++ ) {
188 if( resultS[2].x == ptS[k].x && resultS[2].y == ptS[k].y ) {
189 ptS[k].x = ptS[ cornerCountS ].x ;
190 ptS[k].y = ptS[ cornerCountS-- ].y ;
191 found = 1 ;
192 break ;
193 }
194 }
195 if( found == 0 ) {
196 /*
197 * Add the thing to the list A
198 */
199 ptS[ ++cornerCountS ].x = resultS[2].x ;
200 ptS[ cornerCountS ].y = resultS[2].y ;
201 }
202 found = 0 ;
203 for( k = 1 ; k <= cornerCountS ; k++ ) {
204 if( resultS[3].x == ptS[k].x && resultS[3].y == ptS[k].y ) {
205 ptS[k].x = ptS[ cornerCountS ].x ;
206 ptS[k].y = ptS[ cornerCountS-- ].y ;
207 found = 1 ;
208 break ;
209 }
210 }
211 if( found == 0 ) {
212 /*
213 * Add the thing to the list A
214 */
215 ptS[ ++cornerCountS ].x = resultS[3].x ;
216 ptS[ cornerCountS ].y = resultS[3].y ;
217 }
218 return( resultS ) ;
219
220 } /* end buster */
221 /* ***************************************************************** */
222
Ybuster_addpt(xpos,ypos)223 void Ybuster_addpt( xpos, ypos )
224 INT xpos, ypos ;
225 {
226 if( xpos == ptS[cornerCountS].x && ypos == ptS[cornerCountS].y ){
227 /* avoid redundant points */
228 return ;
229 }
230 /* increase the space if necessary */
231 if( ++cornerCountS >= ptAllocS ){
232 ptAllocS += EXPECTEDPTS ;
233 ptS = YREALLOC( ptS, ptAllocS, YBUSTBOX ) ;
234 }
235 ptS[cornerCountS].x = xpos ;
236 ptS[cornerCountS].y = ypos ;
237 } /* end add_arb_pt */
238 /* ***************************************************************** */
239
Ybuster_init()240 void Ybuster_init()
241 {
242 /* allocate memory if needed */
243 if(!(ptS)){
244 ptAllocS = EXPECTEDPTS ;
245 ptS = YMALLOC( ptAllocS, YBUSTBOX );
246 resultS = YMALLOC( 5, YBUSTBOX ) ;
247 }
248 /* make sure we cannot match the 0 record in the redundancy */
249 /* check above in add_arb_pt */
250 ptS[0].x = INT_MIN ;
251 ptS[0].y = INT_MIN ;
252 cornerCountS = 0 ;
253 } /* end Ybuster_init */
254 /* ***************************************************************** */
255
Ybuster_free()256 void Ybuster_free()
257 {
258 /* free allocate memory */
259 if(ptS){
260 YFREE( ptS ) ;
261 YFREE( resultS ) ;
262 ptS = NULL ;
263 }
264 } /* end Ybuster_free */
265 /* ***************************************************************** */
266
267
268 /*--------------------------------
269 run a sanity check on data.
270 returns TRUE if data might be ok
271 reutrns FALSE if data not ok
272 --------------------------------*/
Ybuster_verify(user_string)273 BOOL Ybuster_verify( user_string )
274 char *user_string ;
275 {
276 INT l;
277
278 cur_stateS = S_STATE ;
279 user_messageS = user_string ;
280
281 /* verify corner count */
282
283 if (cornerCountS < 4) {
284 sprintf(YmsgG," %s : There must be at least 4 corners\n", user_messageS ) ;
285 M(ERRMSG,"Ybuster_verify",YmsgG);
286 return(FALSE) ;
287 }
288
289 if ( cornerCountS & 1) {
290 sprintf(YmsgG," %s : There must be an even # of corners\n", user_messageS ) ;
291 M(ERRMSG,"Ybuster_verify",YmsgG);
292 return(FALSE) ;
293 }
294
295 /* check all points for consistency */
296
297 for (l=1; l < cornerCountS;l++) {
298 if( Ybuster_check_rect( ptS[l].x, ptS[l].y, ptS[l+1].x, ptS[l+1].y )){
299 return( FALSE ) ;
300 }
301 }
302 /* check the last and the first point */
303 if( Ybuster_check_rect( ptS[l].x,ptS[l].y, ptS[1].x, ptS[1].y ) ){
304 return( FALSE ) ;
305 }
306
307
308 /* if we get to this point, everything is ok */
309 return(TRUE);
310 } /* end Ybuster_verify */
311 /* ***************************************************************** */
312
313 /* ***************************************************************** */
314 /* detect problems with clockwise rotation pattern */
315
Ybuster_check_rect(INT xx1,INT yy1,INT xx2,INT yy2)316 BOOL Ybuster_check_rect(INT xx1, INT yy1, INT xx2, INT yy2 )
317 {
318 INT next_state ; /* the next direction of the edge */
319 static INT errorArrayL[6] =
320 {
321 /* E - U - L - R - D - S */
322 E_STATE, D_STATE, R_STATE, L_STATE, U_STATE, R_STATE
323 } ;
324
325 if( xx1 == xx2 && yy1 == yy2 ) {
326 M(ERRMSG,"Ybuster_verify","a zero length side was found ");
327 sprintf(YmsgG,"%s @(%d,%d)\n", user_messageS, xx1, yy1 );
328 M(ERRMSG,NULL,YmsgG);
329 return( TRUE ) ;
330 } else if( xx1 != xx2 && yy1 != yy2 ) {
331 M(ERRMSG,"Ybuster_verify","a non rectilinear side was found");
332 sprintf(YmsgG," %s @(%d,%d)\n",
333 user_messageS, xx1, yy1 );
334 M(ERRMSG,NULL,YmsgG);
335 return( TRUE ) ;
336 } else if( xx2 == xx1 ){
337 if( yy2 < yy1 ){
338 next_state = D_STATE ;
339 } else {
340 next_state = U_STATE ;
341 }
342 } else if( yy2 == yy1 ){
343 if( xx2 < xx1 ){
344 next_state = L_STATE ;
345 } else {
346 next_state = R_STATE ;
347 }
348 }
349 /* check to see if this is an error by looking in error array */
350 /* the first state has two bad states explicitly enum. the second */
351 if( next_state == errorArrayL[cur_stateS] ||
352 (cur_stateS == S_STATE && next_state != U_STATE )){
353 sprintf( YmsgG,
354 "%s is not specified in a CW direction\n",
355 user_messageS ) ;
356 M(ERRMSG,"Ybuster_check_rect", YmsgG ) ;
357 return( TRUE ) ;
358 }
359 /* update state */
360 cur_stateS = next_state ;
361 return( FALSE ) ;
362 } /* end Ybuster_check_rect */
363
Ybuster_check_rect_init(user_string)364 void Ybuster_check_rect_init( user_string )
365 char *user_string ;
366 {
367 cur_stateS = S_STATE ;
368 user_messageS = user_string ;
369 } /* end Ybuster_check_init */
370