#ifndef lint
static char sccsid[] = "@(#)intersect.c 9.2 88/01/19 Copyright 1985 Sun Micro";
#endif

/*
 * Copyright (c) 1985 by Sun Microsystems, Inc. 
 */

/*-
	Trapezon intersection routine

		"Meditation here
		 May think down hours to moments.  Here the heart
		 May give a useful lesson to the head,
		 And learning, wiser grow without his books."
					-- William Cowper

	intersect.c, Mon Jul  1 16:18:03 1985

 */

#ifdef REF
#include <sys/types.h>
#include <ref/config.h>
#endif
#include "qalloc.h"
#include "shape.h"

struct shape_trapezon *
intersect_one_trap(a, b)
    struct shape_trapezon *a,
               *b;
{
    register struct shape_trapseg *p;
    register struct shape_trapezon *ret;
    int         top,
                bottom,
		left,
		right;
    top = max(a->top, b->top);
    bottom = min(a->bottom, b->bottom);
    left = max(a->left, b->left);
    right = min(a->right, b->right);
    if (top >= bottom || left>=right)
	return 0;
    {
	register    size = sizeof(struct shape_trapezon) + (bottom - top + 1) * sizeof(struct shape_trapseg);
	QALLOC(ret, size, (struct shape_trapezon *));
    }
    ret->next = 0;
    ret->refcnt = 1;
    ret->bottom = bottom;
    ret->size = bottom - top + 1;
    ret->left = left;
    ret->right = right;
    p = ret->segs;
    {
	register struct shape_trapseg *ap,
	           *bp;
	register    y;
	ap = a->segs;
	while (ap[1].y < top)
	    ap++;
	bp = b->segs;
	while (bp[1].y < top)
	    bp++;
	y = top;
	while (y < bottom) {
	    p->y = y;
	    p->x1 = max(ap->x1, bp->x1);
	    p->x2 = min(ap->x2, bp->x2);
	    if (p->x1 >= p->x2) {
		if (p != ret->segs && (p[-1].x1 != 0 || p[-1].x2 != 0)) {
		    p->x2 = p->x1 = 0;
		    p++;
		}
	    }
	    else if (p[-1].x1 != p[0].x1 || p[-1].x2 != p[0].x2 || p == ret->segs)
		p++;
	    if (ap[1].y == bp[1].y) {
		bp++;
		ap++;
		y = ap->y;
	    }
	    else if (ap[1].y < bp[1].y) {
		ap++;
		y = ap->y;
	    }
	    else {
		bp++;
		y = bp->y;
	    }
	}
	if (p == ret->segs) {
	    QFREE(ret);
	    ret = 0;
	} else {
	ret->top = ret->segs[0].y;
	if (p[-1].x1 == p[-1].x2) {
	    ret->bottom = p[-1].y;
	    p--;
	}
	else {
	    p->y = y;
	    p->x1 = 0;
	    p->x2 = 0;
	}
	ret->used = p - ret->segs;
	}
    }
    return ret;
}

struct shape *
sh_intersect(as, bs)
register struct shape *as, *bs;
{
    register struct shape *rets;
    if (as == 0 || bs == 0)
	return 0;
    if (as == bs
	    || (as->pos.x == bs->pos.x
		&& as->pos.y == bs->pos.y
		&& as->size.x == bs->size.x
		&& as->size.y == bs->size.y
		&& as->is_rect == bs->is_rect
		&& (as->is_rect || sh_equal(as, bs)))) {
	sh_incref(as);
	return as;
    }
    qtalloc(rets, (struct shape *));
    *rets = *as;
    {
	register    T;
	if ((T = rets->pos.x - bs->pos.x) < 0) {
	    rets->size.x += T;
	    rets->pos.x -= T;
	}
	if ((T = rets->pos.x + rets->size.x - bs->pos.x - bs->size.x) > 0)
	    rets->size.x -= T;
	if ((T = rets->pos.y - bs->pos.y) < 0) {
	    rets->size.y += T;
	    rets->pos.y -= T;
	}
	if ((T = rets->pos.y + rets->size.y - bs->pos.y - bs->size.y) > 0)
	    rets->size.y -= T;
    }
    if (rets->size.y <= 0 || rets->size.x <= 0) {
	qtfree(rets);
	return 0;
    }
    rets->refcnt = 1;
    if (rets->is_rect) {
	if (!bs->is_rect) {
	    rets->trapset = bs->trapset;
	    rets->is_rect = 0;
	    sh_incref(rets->trapset);
	}
    }
    else if (bs->is_rect)
	sh_incref(rets->trapset);
    else {
	register struct shape_trapezon *a = rets->trapset,
	           *b = bs->trapset;
	struct shape_trapezon *first = 0;
	struct shape_trapezon *ret;
	while (a && b) {
	    if (a->bottom <= b->top)
		a = a->next;
	    else if (b->bottom <= a->top)
		b = b->next;
	    else {
		struct shape_trapezon *bprime = b;
		while (bprime && bprime->top < a->bottom) {
		    ret = intersect_one_trap(a, bprime);
		    if (ret)
			if (first == 0) {
			    first = ret;
			    ret->next = 0;
			}
			else {	/* Insertion sort */
			    register struct shape_trapezon **p = &first;
			    while (*p && (*p)->top <= ret->top)
				p = &(*p)->next;
			    ret->next = *p;
			    *p = ret;
			}
		    bprime = bprime->next;
		}
		a = a->next;
	    }
	}
	if (first == 0) {
	    qtfree(rets);
	    return 0;
	}
	rets->trapset = first;
	if (first->next == 0 && first->used == 1) {	/* Rectangular! */
	    register    T;
	    if ((T = first->top - rets->pos.y) > 0) {
		rets->pos.y += T;
		rets->size.y -= T;
	    }
	    if (first->bottom < rets->pos.y + rets->size.y)
		rets->size.y = first->bottom - rets->pos.y;
	    if ((T = first->segs[0].x1 - rets->pos.x) > 0) {
		rets->pos.x += T;
		rets->size.x -= T;
	    }
	    if (first->segs[0].x2 < rets->pos.x + rets->size.x)
		rets->size.x = first->segs[0].x2 - rets->pos.x;
	    /*-	    if (first->top > rets->pos.y)
			    rets->pos.y = first->top;
		        if (first->bottom < rets->pos.y + rets->size.y)
			    rets->pos.y = first->bottom - rets->size.y;
		        if (first->left > rets->pos.x)
			    rets->pos.x = first->left;
		        if (first->right < rets->pos.x + rets->size.x)
			    rets->pos.x = first->right - rets->size.x; */
	    QFREE(first);
	    rets->is_rect = 1;
	    rets->trapset = 0;
	}
    }
    trim_traps(rets);
    if (rets->size.x <= 0 || rets->size.y <= 0) {
	qtfree(rets);
	return 0;
    }
    return rets;
}