![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to circle.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv9 / jtools / src / sunlib|
Return to circle.c CVS log | Up to [Research Unix] / researchv9 / jtools / src / sunlib |
1.1 root 1:
2: #include "jerq.h"
3:
4: /* jerq routines: circle, disc, ellipse, eldisc, arc */
5:
6: /* circle:
7: Form a circle of radius r centered at x1,y1
8: The boundary is a sequence of vertically, horizontally,
9: or diagonally adjacent points that minimize
10: abs(x^2+y^2-r^2).
11: The circle is guaranteed to be symmetric about
12: the horizontal, vertical, and diagonal axes
13: */
14: circle (b, p, r, f)
15: Bitmap *b;
16: Point p;
17: {
18: int x1=p.x;
19: register y1 = p.y;
20: register eps = 0; /* x^2 + y^2 - r^2 */
21: register dxsq = 1; /* (x+dx)^2-x^2*/
22: register dysq = 1 - 2*r;
23: register exy;
24: int x0 = x1;
25: register y0 = y1 - r;
26: y1 += r;
27: initpoints(b, f);
28: if(f == F_XOR){ /* endpoints coincide */
29: points(Pt(x0,y0));
30: points(Pt(x0,y1));
31: }
32: while(y1 > y0){
33: points(Pt(x0,y0));
34: points(Pt(x0,y1));
35: points(Pt(x1,y0));
36: points(Pt(x1,y1));
37: exy = eps + dxsq + dysq;
38: if(-exy <= eps + dxsq){
39: y1--;
40: y0++;
41: eps += dysq;
42: dysq += 2;
43: }
44: if(exy <= -eps){
45: x1++;
46: x0--;
47: eps += dxsq;
48: dxsq += 2;
49: }
50: }
51: points(Pt(x0,y0));
52: points(Pt(x1,y0));
53: endpoints();
54: }
55:
56: /* Fill a disc of radius r centered at x1,y1
57: The boundary is a sequence of vertically, horizontally,
58: or diagonally adjacent points that minimize
59: abs(x^2+y^2-r^2).
60: The circle is guaranteed to be symmetric about
61: the horizontal, vertical, and diagonal axes
62: */
63: disc (b, p, r, f)
64: Bitmap *b;
65: Point p;
66: int r;
67: int f;
68: {
69: register x1, y1;
70: register eps = 0; /* x^2 + y^2 - r^2 */
71: int dxsq = 1; /* (x+dx)^2-x^2 */
72: int dysq = 1 - 2 * r;
73: int exy;
74: register x0;
75: register y0;
76:
77: if(b->flag & BI_OFFSCREEN)
78: p = sub(p, b->rect.origin);
79: x1 = p.x;
80: y1 = p.y;
81: x0 = x1;
82: y0 = y1 - r;
83: x1++; /* to offset jerq's half-open lines */
84: y1 += r;
85: while(y1 > y0){
86: exy = eps + dxsq + dysq;
87: if(-exy <= eps + dxsq){
88: rectf(b, Rect(x0, y0, x1, y0+1), f);
89: rectf(b, Rect(x0, y1, x1, y1+1), f);
90: y1--;
91: y0++;
92: eps += dysq;
93: dysq += 2;
94: }
95: if(exy <= -eps){
96: x1++;
97: x0--;
98: eps += dxsq;
99: dxsq += 2;
100: }
101: }
102: rectf(b, Rect(x0, y0, x1, y0+1), f);
103: }
104:
105: /* arc:
106: draw an approximate arc centered at x0,y0 of an
107: integer grid and running anti-clockwise from
108: x1,y1 to the vicinity of x2,y2.
109: If the endpoints coincide, draw a complete circle.
110: The "arc" is a sequence of vertically, horizontally,
111: or diagonally adjacent points that minimize
112: abs(x^2+y^2-r^2).
113: The circle is guaranteed to be symmetric about
114: the horizontal, vertical, and diagonal axes
115: */
116: #define sq(x) ((long)(x)*(x))
117: #define sgn(x) ((x) < 0 ? -1 : (x)==0 ? 0 : 1)
118: #define mabs(x) (x < 0 ? -x : x)
119:
120: static
121: Point
122: nearby (p1, p2) /* called by arc() */
123: Point p1, p2;
124: {
125: long eps, exy; /*integers but many bits*/
126: int d;
127: register dy;
128: register dx;
129: register x1 = p1.x;
130: register y1 = p1.y;
131: register x2 = p2.x;
132: register y2 = p2.y;
133: eps = sq(x2) + sq(y2) - sq(x1) - sq(y1);
134: d = eps>0? -1: 1;
135: for( ; ; eps=exy, x2+=dx, y2+=dy){
136: if(abs(y2) > abs(x2)){
137: dy = d*sgn(y2);
138: dx = 0;
139: }
140: else{
141: dy = 0;
142: dx = d*sgn(x2);
143: if(dx==0)
144: dx = 1;
145: }
146: exy = eps + (2*x2+dx)*dx + (2*y2+dy)*dy;
147: if(mabs(eps) <= mabs(exy))
148: break;
149: }
150: p2.x = x2;
151: p2.y = y2;
152: return(p2);
153: }
154:
155: arc (bp, p0, p2, p1, f)
156: register Bitmap *bp;
157: Point p0, p1, p2;
158: {
159: register dx, dy;
160: register eps; /* x^2 + y^2 - r^2 */
161: int dxsq, dysq; /* (x+dx)^2-x^2, ...*/
162: int ex, ey, exy;
163: p1 = sub(p1, p0);
164: p2 = sub(p2, p0);
165: p2 = nearby(p1, p2);
166: dx = -sgn(p1.y); /* y1==0 is soon fixed */
167: dy = sgn(p1.x);
168: dxsq = (2*p1.x + dx)*dx;
169: dysq = (2*p1.y + dy)*dy;
170: eps = 0;
171: initpoints(bp, f);
172: do{
173: if(p1.x == 0){
174: dy = -sgn(p1.y);
175: dysq = (2*p1.y + dy)*dy;
176: }
177: else if(p1.y == 0){
178: dx = -sgn(p1.x);
179: dxsq = (2*p1.x + dx)*dx;
180: }
181: ex = abs(eps + dxsq);
182: ey = abs(eps + dysq);
183: exy = abs(eps + dxsq + dysq);
184: if(ex<ey || exy<=ey){
185: p1.x += dx;
186: eps += dxsq;
187: dxsq += 2;
188: }
189: if(ey<ex || exy<=ex){
190: p1.y += dy;
191: eps += dysq;
192: dysq += 2;
193: }
194: points(Pt(p0.x+p1.x, p0.y+p1.y));
195: } while(!(p1.x==p2.x && p1.y==p2.y));
196: /* the equality end test is justified
197: because it is impossible that
198: abs(x^2+y^2-r^2)==abs((x++-1)^2+y^2-r^2) or
199: abs(x^2+y^2-r^2)==abs(x^2+(y++-1)-r^2),
200: and no values of x or y are skipped. */
201: endpoints();
202: }
203:
204: ellipse (bp, p, a, b, f)
205: Bitmap *bp;
206: Point p;
207: long a, b;
208: Code f;
209: {
210: if(a==0 || b==0)
211: segment(bp, Pt(p.x-a, p.y-b), Pt(p.x+a, p.y+b), f);
212: else
213: ellip2(bp, p, a, b, Pt(0, b), Pt(0, b), f);
214: }
215:
216: #define BIG 077777
217: #define HUGE 07777777777L
218: /*
219: resid: calculate b*b*x*x + a*a*y*y - a*a*b*b avoiding ovfl
220: called by ellip1() and ellip2()
221: */
222: static long
223: resid (a,b,x,y)
224: register long a, b;
225: long x, y;
226: {
227: long e = 0;
228: long u = b*(a*a - x*x);
229: long v = a*y*y;
230: register q = u>BIG? HUGE/u: BIG;
231: register r = v>BIG? HUGE/v: BIG;
232: while(a || b){
233: if(e>=0 && b){
234: if(q>b) q = b;
235: e -= q*u;
236: b -= q;
237: }
238: else{
239: if(r>a) r = a;
240: e += r*v;
241: a -= r;
242: }
243: }
244: return(e);
245: }
246:
247: #define labs(x,y) if((x=y)<0) x = -x
248: #define samesign(x,y) (((int)(x)^(int)(y)) > 0)
249:
250: ellip2 (bp, p0, a, b, p1, p2, f)
251: Point p0, p1, p2;
252: long a, b;
253: register Bitmap *bp;
254: Code f;
255: {
256: int dx = p1.y>0 ? 1 : p1.y<0 ? -1 : p1.x>0 ? -1 : 1;
257: int dy = p1.x>0 ? -1 : p1.x<0 ? 1 : p1.y>0 ? -1 : 1;
258: long a2 = a*a;
259: long b2 = b*b;
260: register long dex = b2*(2*dx*p1.x+1);
261: register long e;
262: register long dey = a2*(2*dy*p1.y+1);
263: register long ex, ey, exy;
264: int partial = !eqpt(p1, p2);
265:
266: if(partial &&
267: (p1.x==0 && p2.x==0 && samesign(p1.y, p2.y) ||
268: p1.y==0 && p2.y==0 && samesign(p1.x, p2.x))) {
269: segment(bp, add(p0, p1), add(p0,p2), f);
270: return;
271: }
272: e = resid(a, b, p1.x, p1.y);
273: a2 *= 2;
274: b2 *= 2;
275: initpoints(bp, f);
276: do{
277: labs(ex, e+dex);
278: labs(ey, e+dey);
279: labs(exy, e+dex+dey);
280: if(exy<=ex || ey<ex){
281: p1.y += dy;
282: e += dey;
283: dey += a2;
284: }
285: if(exy<=ey || ex<ey){
286: p1.x += dx;
287: e += dex;
288: dex += b2;
289: }
290: if(p1.x == 0){
291: if(abs(p1.y) == b){
292: dy = -dy;
293: dey = -dey + a2;
294: partial = 0;
295: }
296: /* don't double-draw skinny ends */
297: else if(!samesign(p1.y, dy) && !partial)
298: continue;
299: }
300: else if(p1.y == 0){
301: if(abs(p1.x) == a){
302: dx = -dx;
303: dex = -dex + b2;
304: partial = 0;
305: }
306: else if(!samesign(p1.x, dx) && !partial)
307: continue;
308: }
309: points(add(p0, p1));
310: } while(! eqpt(p1, p2));
311: endpoints();
312: }
313:
314: ellip1 (bp, p0, a, b, action, p1, p2, f)
315: Bitmap *bp;
316: Point p0, p1, p2;
317: long a, b;
318: register void (*action) ();
319: int f;
320: {
321: int dx = p1.y > 0 ? 1 : p1.y < 0 ? -1 : p1.x > 0 ? -1 : 1;
322: int dy = p1.x > 0 ? -1 : p1.x < 0 ? 1 : p1.y > 0 ? -1 : 1;
323: long a2 = a * a;
324: long b2 = b * b;
325: register long dex = b2 * (2 * dx * p1.x + 1);
326: register long e;
327: register long dey = a2 * (2 * dy * p1.y + 1);
328: register long ex, ey, exy;
329: int partial = !eqpt (p1, p2);
330:
331: if(partial &&
332: (p1.x == 0 && p2.x == 0 && samesign (p1.y, p2.y) ||
333: p1.y == 0 && p2.y == 0 && samesign (p1.x, p2.x))){
334: segment(bp, add (p0, p1), add (p0, p2), f);
335: return;
336: }
337: e = resid(a, b, p1.x, p1.y);
338: a2 *= 2;
339: b2 *= 2;
340: do{
341: labs(ex, e + dex);
342: labs(ey, e + dey);
343: labs(exy, e + dex + dey);
344: if(exy <= ex || ey < ex){
345: p1.y += dy;
346: e += dey;
347: dey += a2;
348: }
349: if(exy <= ey || ex < ey){
350: p1.x += dx;
351: e += dex;
352: dex += b2;
353: }
354: if(p1.x == 0){
355: if(abs(p1.y) == b){
356: dy = -dy;
357: dey = -dey + a2;
358: partial = 0;
359: }
360: else
361: if(!samesign (p1.y, dy) && !partial)
362: continue;
363: /* don't double-draw skinny ends */
364: }
365: else
366: if(p1.y == 0){
367: if(abs (p1.x) == a){
368: dx = -dx;
369: dex = -dex + b2;
370: partial = 0;
371: }
372: else
373: if(!samesign (p1.x, dx) && !partial)
374: continue;
375: }
376: (*action)(bp, add (p0, p1), f);
377: } while(!eqpt (p1, p2));
378: }
379:
380: static int yaxis; /* used in scan and eldisc */
381: static int xaxis; /* used in scan and eldisc */
382: static Point lp; /* used in scan and eldisc */
383:
384: static
385: void
386: scan (bp, p, f) /* called by eldisc() and ellip1() */
387: Bitmap *bp;
388: Point p;
389: Code f;
390: {
391: register x, y;
392:
393: if((p.y != lp.y) && (lp.y != -1)){
394: x = xaxis - lp.x;
395: y = yaxis - lp.y;
396: rectf(bp, Rect(lp.x, lp.y, x+1, lp.y+1), f);
397: rectf(bp, Rect(lp.x, y, x+1, y+1), f);
398: }
399: lp = p;
400: }
401:
402: eldisc (bp, p, a, b, f)
403: Bitmap *bp;
404: Point p;
405: int a, b;
406: Code f;
407: {
408: register x0 = p.x;
409: register y0 = p.y;
410:
411: yaxis = 2*p.y;
412: xaxis = 2*p.x;
413: lp.y = -1;
414: if(a==0 || b==0)
415: segment(bp, Pt(x0-a,y0-b), Pt(x0+a,y0+b), f);
416: else{
417: ellip1(bp, p, a, b, scan, Pt(0, -b), Pt(-a, 0), f);
418: scan(bp, Pt(0, -1), f);
419: rectf(bp, Rect(p.x-a, p.y, p.x+a+1, p.y+1), f);
420: }
421: }
422:
423: /* elarc routines */
424:
425: static struct dist {
426: Point s;
427: Point m;
428: long e;
429: } d1, d2;
430:
431: static
432: void
433: test(x, p) /* called by survet() */
434: Point x;
435: register struct dist *p;
436: {
437: register long dx = x.x - p->s.x;
438: register long dy = x.y - p->s.y;
439: register long e = dx*dx+dy*dy;
440:
441: if(e <= p->e){
442: p->m = x;
443: p->e = e;
444: }
445: }
446:
447: static
448: void
449: survey(bp, x, f) /* called by elarc() */
450: Bitmap *bp;
451: Point x;
452: Code f;
453: {
454: test(x, &d1);
455: test(x, &d2);
456: }
457:
458: #define HUGE2 017777777777
459: #define sgn2(x) ((x)<0? -1 : (x)==0? 0 : 1)
460:
461: /*
462: elarc(bp,p0,a,b,p1,p2,f) draws in bitmap bp an arc of the ellipse
463: centered at p0 with half-axes a,b extending counterclockwise
464: from a point near p1 to a point near p2
465: args reversed because ellip1 draws clockwise
466: */
467: elarc (bp, p0, a, b, p1, p2, f)
468: Bitmap *bp;
469: Point p0, p1, p2;
470: Code f;
471: {
472: if(a==0)
473: segment(bp, Pt(p0.x, p1.y), Pt(p0.x, p2.y), f);
474: else if(b==0)
475: segment(bp, Pt(p1.x, p0.y), Pt(p2.x, p0.y), f);
476: else{
477: int sx1;
478: int sy1;
479: int sx2;
480: int sy2;
481:
482: d1.s = sub(p1, p0);
483: d2.s = sub(p2, p0);
484: sx1 = sgn2(d1.s.x);
485: sy1 = sgn2(d1.s.y);
486: sx2 = sgn2(d2.s.x);
487: sy2 = sgn2(d2.s.y);
488: d1.s.x *= sx1;
489: d1.s.y *= sy1;
490: d2.s.x *= sx2;
491: d2.s.y *= sy2;
492: d1.e = d2.e = HUGE2;
493: survey(bp, Pt(0, b), f);
494: ellip1(bp, Pt(0, 0), a, b, survey, Pt(0,b), Pt(a, 0), f);
495: if(!eqpt(d1.m, d2.m))
496: point(bp, d1.m, f);
497: ellip1(bp, p0, a, b, point,
498: Pt(d1.m.x*sx1, d1.m.y*sy1),
499: Pt(d2.m.x*sx2, d2.m.y*sy2), f);
500: }
501: }
502:
503: /*
504: dak's points routines for buffering X calls
505: */
506: #ifdef X11
507: #define PBSIZE 100
508: #define flushpt() if (xpcnt) flushpoints();
509: static XPoint xp[PBSIZE];
510: static xpcnt;
511: #endif X11
512: static Code fc;
513: static ispixmap;
514: static Bitmap *bitm;
515:
516: points (p)
517: Point p;
518: {
519: #ifdef SUNTOOLS
520: point(bitm,p,fc);
521: #endif SUNTOOLS
522: #ifdef X11
523: register XPoint *x;
524:
525: if(ispixmap)
526: p = sub(p, bitm->rect.origin);
527: x = &xp[xpcnt];
528: x->x = p.x;
529: x->y = p.y;
530: if (++xpcnt == PBSIZE)
531: flushpoints();
532: #endif X11
533: }
534:
535: initpoints (b, f)
536: Bitmap *b;
537: Code f;
538: {
539: if(b->flag & BI_OFFSCREEN)
540: ispixmap = 1;
541: else {
542: #ifdef SUNTOOLS
543: struct rect lkrect;
544: if(!(b->flag & BI_OFFSCREEN)){
545: win_getsize(displayfd, &lkrect);
546: pw_lock((Pixwin *)b->dr, &lkrect);
547: }
548: #endif SUNTOOLS
549: ispixmap = 0;
550: }
551: bitm = b;
552: #ifdef X11
553: XSetFunction(dpy, gc, f);
554: #endif X11
555: fc = f;
556: }
557:
558: endpoints()
559: {
560: #ifdef SUNTOOLS
561: if(!ispixmap)
562: pw_unlock((Pixwin *)bitm->dr);
563: #endif SUNTOOLS
564: #ifdef X11
565: flushpt();
566: #endif X11
567: }
568:
569: #ifdef X11
570: flushpoints()
571: {
572: if(xpcnt){
573: XDrawPoints(dpy, bitm->dr, gc, xp, xpcnt, CoordModeOrigin);
574: xpcnt = 0;
575: }
576: }
577: #endif X11
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.