2 * Copyright (c) 2001 James "Wez" Weatherall, Johannes E. Schindelin
4 * A general purpose region clipping library
5 * Only deals with rectangular regions, though.
14 /* -=- Internal Span structure */
18 typedef struct sraSpan
{
19 struct sraSpan
*_next
;
20 struct sraSpan
*_prev
;
23 struct sraRegion
*subspan
;
26 typedef struct sraRegion
{
31 /* -=- Span routines */
33 sraSpanList
*sraSpanListDup(const sraSpanList
*src
);
34 void sraSpanListDestroy(sraSpanList
*list
);
37 sraSpanCreate(int start
, int end
, const sraSpanList
*subspan
) {
38 sraSpan
*item
= (sraSpan
*)malloc(sizeof(sraSpan
));
39 item
->_next
= item
->_prev
= NULL
;
42 item
->subspan
= sraSpanListDup(subspan
);
47 sraSpanDup(const sraSpan
*src
) {
49 if (!src
) return NULL
;
50 span
= sraSpanCreate(src
->start
, src
->end
, src
->subspan
);
55 sraSpanInsertAfter(sraSpan
*newspan
, sraSpan
*after
) {
56 newspan
->_next
= after
->_next
;
57 newspan
->_prev
= after
;
58 after
->_next
->_prev
= newspan
;
59 after
->_next
= newspan
;
63 sraSpanInsertBefore(sraSpan
*newspan
, sraSpan
*before
) {
64 newspan
->_next
= before
;
65 newspan
->_prev
= before
->_prev
;
66 before
->_prev
->_next
= newspan
;
67 before
->_prev
= newspan
;
71 sraSpanRemove(sraSpan
*span
) {
72 span
->_prev
->_next
= span
->_next
;
73 span
->_next
->_prev
= span
->_prev
;
77 sraSpanDestroy(sraSpan
*span
) {
78 if (span
->subspan
) sraSpanListDestroy(span
->subspan
);
83 sraSpanCheck(const sraSpan
*span
, const char *text
) {
84 /* Check the span is valid! */
85 if (span
->start
== span
->end
) {
86 printf("%s:%d-%d\n", text
, span
->start
, span
->end
);
91 /* -=- SpanList routines */
93 void sraSpanPrint(const sraSpan
*s
);
96 sraSpanListPrint(const sraSpanList
*l
) {
102 curr
= l
->front
._next
;
104 while (curr
!= &(l
->back
)) {
112 sraSpanPrint(const sraSpan
*s
) {
113 printf("(%d-%d)", (s
->start
), (s
->end
));
115 sraSpanListPrint(s
->subspan
);
119 sraSpanListCreate() {
120 sraSpanList
*item
= (sraSpanList
*)malloc(sizeof(sraSpanList
));
121 item
->front
._next
= &(item
->back
);
122 item
->front
._prev
= NULL
;
123 item
->back
._prev
= &(item
->front
);
124 item
->back
._next
= NULL
;
129 sraSpanListDup(const sraSpanList
*src
) {
130 sraSpanList
*newlist
;
131 sraSpan
*newspan
, *curr
;
133 if (!src
) return NULL
;
134 newlist
= sraSpanListCreate();
135 curr
= src
->front
._next
;
136 while (curr
!= &(src
->back
)) {
137 newspan
= sraSpanDup(curr
);
138 sraSpanInsertBefore(newspan
, &(newlist
->back
));
146 sraSpanListDestroy(sraSpanList
*list
) {
147 sraSpan
*curr
, *next
;
148 while (list
->front
._next
!= &(list
->back
)) {
149 curr
= list
->front
._next
;
152 sraSpanDestroy(curr
);
159 sraSpanListMakeEmpty(sraSpanList
*list
) {
160 sraSpan
*curr
, *next
;
161 while (list
->front
._next
!= &(list
->back
)) {
162 curr
= list
->front
._next
;
165 sraSpanDestroy(curr
);
168 list
->front
._next
= &(list
->back
);
169 list
->front
._prev
= NULL
;
170 list
->back
._prev
= &(list
->front
);
171 list
->back
._next
= NULL
;
175 sraSpanListEqual(const sraSpanList
*s1
, const sraSpanList
*s2
) {
182 printf("sraSpanListEqual:incompatible spans (only one NULL!)\n");
187 sp1
= s1
->front
._next
;
188 sp2
= s2
->front
._next
;
189 while ((sp1
!= &(s1
->back
)) &&
190 (sp2
!= &(s2
->back
))) {
191 if ((sp1
->start
!= sp2
->start
) ||
192 (sp1
->end
!= sp2
->end
) ||
193 (!sraSpanListEqual(sp1
->subspan
, sp2
->subspan
))) {
200 if ((sp1
== &(s1
->back
)) && (sp2
== &(s2
->back
))) {
208 sraSpanListEmpty(const sraSpanList
*list
) {
209 return (list
->front
._next
== &(list
->back
));
213 sraSpanListCount(const sraSpanList
*list
) {
214 sraSpan
*curr
= list
->front
._next
;
215 unsigned long count
= 0;
216 while (curr
!= &(list
->back
)) {
218 count
+= sraSpanListCount(curr
->subspan
);
228 sraSpanMergePrevious(sraSpan
*dest
) {
229 sraSpan
*prev
= dest
->_prev
;
230 while ((prev
->end
== dest
->start
) &&
232 (sraSpanListEqual(prev
->subspan
, dest
->subspan
))) {
234 printf("merge_prev:");
240 dest
->start
= prev
->start
;
242 sraSpanDestroy(prev
);
248 sraSpanMergeNext(sraSpan
*dest
) {
249 sraSpan
*next
= dest
->_next
;
250 while ((next
->start
== dest
->end
) &&
252 (sraSpanListEqual(next
->subspan
, dest
->subspan
))) {
254 printf("merge_next:");
260 dest
->end
= next
->end
;
262 sraSpanDestroy(next
);
268 sraSpanListOr(sraSpanList
*dest
, const sraSpanList
*src
) {
269 sraSpan
*d_curr
, *s_curr
;
276 printf("sraSpanListOr:incompatible spans (only one NULL!)\n");
281 d_curr
= dest
->front
._next
;
282 s_curr
= src
->front
._next
;
283 s_start
= s_curr
->start
;
285 while (s_curr
!= &(src
->back
)) {
287 /* - If we are at end of destination list OR
288 If the new span comes before the next destination one */
289 if ((d_curr
== &(dest
->back
)) ||
290 (d_curr
->start
>= s_end
)) {
292 sraSpanInsertBefore(sraSpanCreate(s_start
, s_end
,
295 if (d_curr
!= &(dest
->back
))
296 sraSpanMergePrevious(d_curr
);
297 s_curr
= s_curr
->_next
;
298 s_start
= s_curr
->start
;
302 /* - If the new span overlaps the existing one */
303 if ((s_start
< d_curr
->end
) &&
304 (s_end
> d_curr
->start
)) {
306 /* - Insert new span before the existing destination one? */
307 if (s_start
< d_curr
->start
) {
308 sraSpanInsertBefore(sraSpanCreate(s_start
,
312 sraSpanMergePrevious(d_curr
);
315 /* Split the existing span if necessary */
316 if (s_end
< d_curr
->end
) {
317 sraSpanInsertAfter(sraSpanCreate(s_end
,
323 if (s_start
> d_curr
->start
) {
324 sraSpanInsertBefore(sraSpanCreate(d_curr
->start
,
328 d_curr
->start
= s_start
;
331 /* Recursively OR subspans */
332 sraSpanListOr(d_curr
->subspan
, s_curr
->subspan
);
334 /* Merge this span with previous or next? */
335 if (d_curr
->_prev
!= &(dest
->front
))
336 sraSpanMergePrevious(d_curr
);
337 if (d_curr
->_next
!= &(dest
->back
))
338 sraSpanMergeNext(d_curr
);
340 /* Move onto the next pair to compare */
341 if (s_end
> d_curr
->end
) {
342 s_start
= d_curr
->end
;
343 d_curr
= d_curr
->_next
;
345 s_curr
= s_curr
->_next
;
346 s_start
= s_curr
->start
;
350 /* - No overlap. Move to the next destination span */
351 d_curr
= d_curr
->_next
;
358 sraSpanListAnd(sraSpanList
*dest
, const sraSpanList
*src
) {
359 sraSpan
*d_curr
, *s_curr
, *d_next
;
365 printf("sraSpanListAnd:incompatible spans (only one NULL!)\n");
370 d_curr
= dest
->front
._next
;
371 s_curr
= src
->front
._next
;
372 while ((s_curr
!= &(src
->back
)) && (d_curr
!= &(dest
->back
))) {
374 /* - If we haven't reached a destination span yet then move on */
375 if (d_curr
->start
>= s_curr
->end
) {
376 s_curr
= s_curr
->_next
;
380 /* - If we are beyond the current destination span then remove it */
381 if (d_curr
->end
<= s_curr
->start
) {
382 sraSpan
*next
= d_curr
->_next
;
383 sraSpanRemove(d_curr
);
384 sraSpanDestroy(d_curr
);
389 /* - If we partially overlap a span then split it up or remove bits */
390 if (s_curr
->start
> d_curr
->start
) {
391 /* - The top bit of the span does not match */
392 d_curr
->start
= s_curr
->start
;
394 if (s_curr
->end
< d_curr
->end
) {
395 /* - The end of the span does not match */
396 sraSpanInsertAfter(sraSpanCreate(s_curr
->end
,
400 d_curr
->end
= s_curr
->end
;
403 /* - Now recursively process the affected span */
404 if (!sraSpanListAnd(d_curr
->subspan
, s_curr
->subspan
)) {
405 /* - The destination subspan is now empty, so we should remove it */
406 sraSpan
*next
= d_curr
->_next
;
407 sraSpanRemove(d_curr
);
408 sraSpanDestroy(d_curr
);
411 /* Merge this span with previous or next? */
412 if (d_curr
->_prev
!= &(dest
->front
))
413 sraSpanMergePrevious(d_curr
);
415 /* - Move on to the next span */
417 if (s_curr
->end
>= d_curr
->end
) {
418 d_next
= d_curr
->_next
;
420 if (s_curr
->end
<= d_curr
->end
) {
421 s_curr
= s_curr
->_next
;
427 while (d_curr
!= &(dest
->back
)) {
428 sraSpan
*next
= d_curr
->_next
;
429 sraSpanRemove(d_curr
);
430 sraSpanDestroy(d_curr
);
434 return !sraSpanListEmpty(dest
);
438 sraSpanListSubtract(sraSpanList
*dest
, const sraSpanList
*src
) {
439 sraSpan
*d_curr
, *s_curr
;
445 printf("sraSpanListSubtract:incompatible spans (only one NULL!)\n");
450 d_curr
= dest
->front
._next
;
451 s_curr
= src
->front
._next
;
452 while ((s_curr
!= &(src
->back
)) && (d_curr
!= &(dest
->back
))) {
454 /* - If we haven't reached a destination span yet then move on */
455 if (d_curr
->start
>= s_curr
->end
) {
456 s_curr
= s_curr
->_next
;
460 /* - If we are beyond the current destination span then skip it */
461 if (d_curr
->end
<= s_curr
->start
) {
462 d_curr
= d_curr
->_next
;
466 /* - If we partially overlap the current span then split it up */
467 if (s_curr
->start
> d_curr
->start
) {
468 sraSpanInsertBefore(sraSpanCreate(d_curr
->start
,
472 d_curr
->start
= s_curr
->start
;
474 if (s_curr
->end
< d_curr
->end
) {
475 sraSpanInsertAfter(sraSpanCreate(s_curr
->end
,
479 d_curr
->end
= s_curr
->end
;
482 /* - Now recursively process the affected span */
483 if ((!d_curr
->subspan
) || !sraSpanListSubtract(d_curr
->subspan
, s_curr
->subspan
)) {
484 /* - The destination subspan is now empty, so we should remove it */
485 sraSpan
*next
= d_curr
->_next
;
486 sraSpanRemove(d_curr
);
487 sraSpanDestroy(d_curr
);
490 /* Merge this span with previous or next? */
491 if (d_curr
->_prev
!= &(dest
->front
))
492 sraSpanMergePrevious(d_curr
);
493 if (d_curr
->_next
!= &(dest
->back
))
494 sraSpanMergeNext(d_curr
);
496 /* - Move on to the next span */
497 if (s_curr
->end
> d_curr
->end
) {
498 d_curr
= d_curr
->_next
;
500 s_curr
= s_curr
->_next
;
505 return !sraSpanListEmpty(dest
);
508 /* -=- Region routines */
512 return (sraRegion
*)sraSpanListCreate();
516 sraRgnCreateRect(int x1
, int y1
, int x2
, int y2
) {
517 sraSpanList
*vlist
, *hlist
;
518 sraSpan
*vspan
, *hspan
;
520 /* - Build the horizontal portion of the span */
521 hlist
= sraSpanListCreate();
522 hspan
= sraSpanCreate(x1
, x2
, NULL
);
523 sraSpanInsertAfter(hspan
, &(hlist
->front
));
525 /* - Build the vertical portion of the span */
526 vlist
= sraSpanListCreate();
527 vspan
= sraSpanCreate(y1
, y2
, hlist
);
528 sraSpanInsertAfter(vspan
, &(vlist
->front
));
530 sraSpanListDestroy(hlist
);
532 return (sraRegion
*)vlist
;
536 sraRgnCreateRgn(const sraRegion
*src
) {
537 return (sraRegion
*)sraSpanListDup((sraSpanList
*)src
);
541 sraRgnDestroy(sraRegion
*rgn
) {
542 sraSpanListDestroy((sraSpanList
*)rgn
);
546 sraRgnMakeEmpty(sraRegion
*rgn
) {
547 sraSpanListMakeEmpty((sraSpanList
*)rgn
);
550 /* -=- Boolean Region ops */
553 sraRgnAnd(sraRegion
*dst
, const sraRegion
*src
) {
554 return sraSpanListAnd((sraSpanList
*)dst
, (sraSpanList
*)src
);
558 sraRgnOr(sraRegion
*dst
, const sraRegion
*src
) {
559 sraSpanListOr((sraSpanList
*)dst
, (sraSpanList
*)src
);
563 sraRgnSubtract(sraRegion
*dst
, const sraRegion
*src
) {
564 return sraSpanListSubtract((sraSpanList
*)dst
, (sraSpanList
*)src
);
568 sraRgnOffset(sraRegion
*dst
, int dx
, int dy
) {
569 sraSpan
*vcurr
, *hcurr
;
571 vcurr
= ((sraSpanList
*)dst
)->front
._next
;
572 while (vcurr
!= &(((sraSpanList
*)dst
)->back
)) {
576 hcurr
= vcurr
->subspan
->front
._next
;
577 while (hcurr
!= &(vcurr
->subspan
->back
)) {
580 hcurr
= hcurr
->_next
;
583 vcurr
= vcurr
->_next
;
588 sraRgnPopRect(sraRegion
*rgn
, sraRect
*rect
, unsigned long flags
) {
589 sraSpan
*vcurr
, *hcurr
;
590 sraSpan
*vend
, *hend
;
591 Bool right2left
= flags
& 2;
592 Bool bottom2top
= flags
& 1;
594 /* - Pick correct order */
596 vcurr
= ((sraSpanList
*)rgn
)->back
._prev
;
597 vend
= &(((sraSpanList
*)rgn
)->front
);
599 vcurr
= ((sraSpanList
*)rgn
)->front
._next
;
600 vend
= &(((sraSpanList
*)rgn
)->back
);
604 rect
->y1
= vcurr
->start
;
605 rect
->y2
= vcurr
->end
;
607 /* - Pick correct order */
609 hcurr
= vcurr
->subspan
->back
._prev
;
610 hend
= &(vcurr
->subspan
->front
);
612 hcurr
= vcurr
->subspan
->front
._next
;
613 hend
= &(vcurr
->subspan
->back
);
617 rect
->x1
= hcurr
->start
;
618 rect
->x2
= hcurr
->end
;
620 sraSpanRemove(hcurr
);
621 sraSpanDestroy(hcurr
);
623 if (sraSpanListEmpty(vcurr
->subspan
)) {
624 sraSpanRemove(vcurr
);
625 sraSpanDestroy(vcurr
);
629 printf("poprect:(%dx%d)-(%dx%d)\n",
630 rect
->x1
, rect
->y1
, rect
->x2
, rect
->y2
);
640 sraRgnCountRects(const sraRegion
*rgn
) {
641 unsigned long count
= sraSpanListCount((sraSpanList
*)rgn
);
646 sraRgnEmpty(const sraRegion
*rgn
) {
647 return sraSpanListEmpty((sraSpanList
*)rgn
);
651 sraRectangleIterator
*sraRgnGetIterator(sraRegion
*s
)
653 /* these values have to be multiples of 4 */
656 sraRectangleIterator
*i
=
657 (sraRectangleIterator
*)malloc(sizeof(sraRectangleIterator
));
661 /* we have to recurse eventually. So, the first sPtr is the pointer to
662 the sraSpan in the first level. the second sPtr is the pointer to
663 the sraRegion.back. The third and fourth sPtr are for the second
664 recursion level and so on. */
665 i
->sPtrs
= (sraSpan
**)malloc(sizeof(sraSpan
*)*DEFSIZE
);
670 i
->ptrSize
= DEFSIZE
;
671 i
->sPtrs
[0] = &(s
->front
);
672 i
->sPtrs
[1] = &(s
->back
);
679 sraRectangleIterator
*sraRgnGetReverseIterator(sraRegion
*s
,Bool reverseX
,Bool reverseY
)
681 sraRectangleIterator
*i
= sraRgnGetIterator(s
);
683 i
->sPtrs
[1] = &(s
->front
);
684 i
->sPtrs
[0] = &(s
->back
);
686 i
->reverseX
= reverseX
;
687 i
->reverseY
= reverseY
;
691 Bool
sraReverse(sraRectangleIterator
*i
)
693 return( ((i
->ptrPos
&2) && i
->reverseX
) ||
694 (!(i
->ptrPos
&2) && i
->reverseY
));
697 sraSpan
* sraNextSpan(sraRectangleIterator
*i
)
700 return(i
->sPtrs
[i
->ptrPos
]->_prev
);
702 return(i
->sPtrs
[i
->ptrPos
]->_next
);
705 Bool
sraRgnIteratorNext(sraRectangleIterator
* i
,sraRect
* r
)
707 /* is the subspan finished? */
708 while(sraNextSpan(i
) == i
->sPtrs
[i
->ptrPos
+1]) {
710 if(i
->ptrPos
< 0) /* the end */
714 i
->sPtrs
[i
->ptrPos
] = sraNextSpan(i
);
716 /* is this a new subspan? */
717 while(i
->sPtrs
[i
->ptrPos
]->subspan
) {
718 if(i
->ptrPos
+2 > i
->ptrSize
) { /* array is too small */
719 i
->ptrSize
+= DEFSTEP
;
720 i
->sPtrs
= (sraSpan
**)realloc(i
->sPtrs
, sizeof(sraSpan
*)*i
->ptrSize
);
724 i
->sPtrs
[i
->ptrPos
] = i
->sPtrs
[i
->ptrPos
-2]->subspan
->back
._prev
;
725 i
->sPtrs
[i
->ptrPos
+1] = &(i
->sPtrs
[i
->ptrPos
-2]->subspan
->front
);
727 i
->sPtrs
[i
->ptrPos
] = i
->sPtrs
[i
->ptrPos
-2]->subspan
->front
._next
;
728 i
->sPtrs
[i
->ptrPos
+1] = &(i
->sPtrs
[i
->ptrPos
-2]->subspan
->back
);
732 if((i
->ptrPos
%4)!=2) {
733 fprintf(stderr
,"sraRgnIteratorNext: offset is wrong (%d%%4!=2)\n",i
->ptrPos
);
737 r
->y1
= i
->sPtrs
[i
->ptrPos
-2]->start
;
738 r
->y2
= i
->sPtrs
[i
->ptrPos
-2]->end
;
739 r
->x1
= i
->sPtrs
[i
->ptrPos
]->start
;
740 r
->x2
= i
->sPtrs
[i
->ptrPos
]->end
;
745 void sraRgnReleaseIterator(sraRectangleIterator
* i
)
752 sraRgnPrint(const sraRegion
*rgn
) {
753 sraSpanListPrint((sraSpanList
*)rgn
);
757 sraClipRect(int *x
, int *y
, int *w
, int *h
,
758 int cx
, int cy
, int cw
, int ch
) {
773 return (*w
>0) && (*h
>0);
779 /* pipe the output to sort|uniq -u and you'll get the errors. */
780 int main(int argc
, char** argv
)
782 sraRegionPtr region
, region1
, region2
;
783 sraRectangleIterator
* i
;
787 region
= sraRgnCreateRect(10, 10, 600, 300);
788 region1
= sraRgnCreateRect(40, 50, 350, 200);
789 region2
= sraRgnCreateRect(0, 0, 20, 40);
792 printf("\n[(10-300)[(10-600)]]\n\n");
794 b
= sraRgnSubtract(region
, region1
);
795 printf("%s ",b
?"true":"false");
797 printf("\ntrue [(10-50)[(10-600)](50-200)[(10-40)(350-600)](200-300)[(10-600)]]\n\n");
799 sraRgnOr(region
, region2
);
800 printf("%ld\n6\n\n", sraRgnCountRects(region
));
802 i
= sraRgnGetIterator(region
);
803 while(sraRgnIteratorNext(i
, &rect
))
804 printf("%dx%d+%d+%d ",
805 rect
.x2
-rect
.x1
,rect
.y2
-rect
.y1
,
807 sraRgnReleaseIterator(i
);
808 printf("\n20x10+0+0 600x30+0+10 590x10+10+40 30x150+10+50 250x150+350+50 590x100+10+200\n\n");
810 i
= sraRgnGetReverseIterator(region
,1,0);
811 while(sraRgnIteratorNext(i
, &rect
))
812 printf("%dx%d+%d+%d ",
813 rect
.x2
-rect
.x1
,rect
.y2
-rect
.y1
,
815 sraRgnReleaseIterator(i
);
816 printf("\n20x10+0+0 600x30+0+10 590x10+10+40 250x150+350+50 30x150+10+50 590x100+10+200\n\n");
818 i
= sraRgnGetReverseIterator(region
,1,1);
819 while(sraRgnIteratorNext(i
, &rect
))
820 printf("%dx%d+%d+%d ",
821 rect
.x2
-rect
.x1
,rect
.y2
-rect
.y1
,
823 sraRgnReleaseIterator(i
);
824 printf("\n590x100+10+200 250x150+350+50 30x150+10+50 590x10+10+40 600x30+0+10 20x10+0+0\n\n");