rectangl.c

R+树的c实现源码

			return (FALSE);
	}
	return (TRUE);
}

Equal2(r, s, ndims)
register struct	Rect	*r, *s;
int			ndims;
{
        if (RYX(r,s,ndims,7,7))
        	return (TRUE);
	else
		return (FALSE);
}

Equal1(r, s, ndims)
register struct Rect    *r, *s;
int                     ndims;
{
	if (Cover(r, s, ndims) || Contain(r, s, ndims) || Equal(r, s, ndims))
		return (TRUE);
	else
		return (FALSE);
}

/*-----------------------------------------------------------------------------
| Inside(r, s, ndims)
|	Decide whether rect s is inside rect r
-----------------------------------------------------------------------------*/
Inside(r, s, ndims)
register struct	Rect	*r, *s;
int			ndims;
{
	return (Contain(s, r, ndims));
}

Inside2(r, s, ndims)
register struct	Rect	*r, *s;
int			ndims;
{
        if (RYX(r,s,ndims,9,9))
        	return (TRUE);
	else
		return (FALSE);
}

Inside1(r, s, ndims)
register struct	Rect	*r, *s;
int			ndims;
{
	if (Disjoint(r, s, ndims) || Meet(r, s, ndims))
		return (FALSE);
	else
		return (TRUE);
}

/*-----------------------------------------------------------------------------
| Covered_by(r, s, ndims)
|	Decide whether rect s is covered_by rect r
-----------------------------------------------------------------------------*/
Covered_by(r, s, ndims)
register struct	Rect	*r, *s;
int			ndims;
{
	return (Cover(s, r, ndims));
}

Covered_by2(r, s, ndims)
register struct	Rect	*r, *s;
int			ndims;
{
        if (RYX(r,s,ndims,6,6) || RYX(r,s,ndims,6,7) || RYX(r,s,ndims,6,9) || 
            RYX(r,s,ndims,6,10) || RYX(r,s,ndims,7,6) || RYX(r,s,ndims,7,7) || 
            RYX(r,s,ndims,7,9) || RYX(r,s,ndims,7,10) || RYX(r,s,ndims,9,6) || 
            RYX(r,s,ndims,9,7) || RYX(r,s,ndims,9,9) || RYX(r,s,ndims,9,10) || 
            RYX(r,s,ndims,10,6) || RYX(r,s,ndims,10,7) || RYX(r,s,ndims,10,9) || 
            RYX(r,s,ndims,10,10))
        	return (TRUE);
	else
		return (FALSE);
}

Covered_by1(r, s, ndims)
register struct	Rect	*r, *s;
int			ndims;
{
	if (Disjoint(r, s, ndims) || Meet(r, s, ndims))
		return (FALSE);
	else
		return (TRUE);
}

/*-----------------------------------------------------------------------------
| Meet(r, s, ndims)
|	Decide whether rect s meets rect r
-----------------------------------------------------------------------------*/
Meet(r, s, ndims)
register struct	Rect	*r, *s;
int			ndims;
{
	register int i, j;
	assert(r && s);

	if (MyOverlap(r, s, ndims))
		for (i=0; i<ndims; i++)
		{
			j = i + ndims;  /* index for high sides */
			if (s->boundary[i] == r->boundary[j] || 
		    	r->boundary[i] == s->boundary[j])
				return (TRUE);
		}
	return (FALSE);
}

Meet2(r, s, ndims)
register struct	Rect	*r, *s;
int			ndims;
{
        if (RX(r,s,ndims,1) || RX(r,s,ndims,13) || 
            RY(r,s,ndims,1) || RY(r,s,ndims,13) || 
            RYX(r,s,ndims,4,9) || RYX(r,s,ndims,5,6) || RYX(r,s,ndims,5,7) || 
            RYX(r,s,ndims,5,9) || RYX(r,s,ndims,5,10) || RYX(r,s,ndims,6,5) || 
            RYX(r,s,ndims,7,5) || RYX(r,s,ndims,7,9) || RYX(r,s,ndims,8,9) || 
            RYX(r,s,ndims,9,4) || RYX(r,s,ndims,9,5) || RYX(r,s,ndims,9,7) || 
            RYX(r,s,ndims,9,8) || RYX(r,s,ndims,10,5))
        	return (FALSE);
	else
		return (TRUE);
}

Meet1(r, s, ndims)
register struct	Rect	*r, *s;
int			ndims;
{
	if (Disjoint(r, s, ndims))
		return (FALSE);
	else
		return (TRUE);
}

/*-----------------------------------------------------------------------------
| RYX(r, s, ndims, y, x), RY(r, s, ndims, y), RX(r, s, ndims, x)
|       Primitive topological functions . x=1..13, y=1..13
-----------------------------------------------------------------------------*/
RYX(r, s, ndims, y, x)
register struct Rect    *r, *s;
int                     ndims, y, x;
{
	if (RY(r, s, ndims, y) && RX(r, s, ndims, x))
		return (TRUE);
	else
		return (FALSE);
}

RY(r, s, ndims, y)
register struct Rect    *r, *s;
int                     ndims, y;
{
        assert(r && s);

	if (y==1)
        	return (s->boundary[1] > r->boundary[3]);
	if (y==2)
        	return (s->boundary[1] == r->boundary[3]);
	if (y==3)
        	return ((s->boundary[3] > r->boundary[3]) &&
                	(s->boundary[1] > r->boundary[1]) &&
                	(s->boundary[1] < r->boundary[3]));
	if (y==4)
        	return ((s->boundary[3] > r->boundary[3]) &&
                	(s->boundary[1] == r->boundary[1]));
	if (y==5)
        	return ((s->boundary[3] > r->boundary[3]) &&
                	(s->boundary[1] < r->boundary[1]));
	if (y==6)
        	return ((s->boundary[3] == r->boundary[3]) &&
                	(s->boundary[1] > r->boundary[1]));
	if (y==7)
        	return ((s->boundary[3] == r->boundary[3]) &&
                	(s->boundary[1] == r->boundary[1]));
	if (y==8)
        	return ((s->boundary[3] == r->boundary[3]) &&
                	(s->boundary[1] < r->boundary[1]));
	if (y==9)
        	return ((s->boundary[3] < r->boundary[3]) &&
                	(s->boundary[1] > r->boundary[1]));
	if (y==10)
        	return ((s->boundary[3] < r->boundary[3]) &&
                	(s->boundary[1] == r->boundary[1]));
	if (y==11)
        	return ((s->boundary[3] < r->boundary[3]) &&
                	(s->boundary[3] > r->boundary[1]) &&
                	(s->boundary[1] < r->boundary[1]));
	if (y==12)
        	return (s->boundary[3] == r->boundary[1]);
	if (y==13)
        	return (s->boundary[3] < r->boundary[1]);
}

RX(r, s, ndims, x)
register struct Rect    *r, *s;
int                     ndims, x;
{
        assert(r && s);

	if (x==1)
        	return (s->boundary[0] > r->boundary[2]);
	if (x==2)
        	return (s->boundary[0] == r->boundary[2]);
	if (x==3)
        	return ((s->boundary[2] > r->boundary[2]) &&
                	(s->boundary[0] > r->boundary[0]) &&
                	(s->boundary[0] < r->boundary[2]));
	if (x==4)
        	return ((s->boundary[2] > r->boundary[2]) &&
                	(s->boundary[0] == r->boundary[0]));
	if (x==5)
        	return ((s->boundary[2] > r->boundary[2]) &&
                	(s->boundary[0] < r->boundary[0]));
	if (x==6)
        	return ((s->boundary[2] == r->boundary[2]) &&
                	(s->boundary[0] > r->boundary[0]));
	if (x==7)
        	return ((s->boundary[2] == r->boundary[2]) &&
                	(s->boundary[0] == r->boundary[0]));
	if (x==8)
        	return ((s->boundary[2] == r->boundary[2]) &&
                	(s->boundary[0] < r->boundary[0]));
	if (x==9)
        	return ((s->boundary[2] < r->boundary[2]) &&
                	(s->boundary[0] > r->boundary[0]));
	if (x==10)
        	return ((s->boundary[2] < r->boundary[2]) &&
                	(s->boundary[0] == r->boundary[0]));
	if (x==11)
        	return ((s->boundary[2] < r->boundary[2]) &&
                	(s->boundary[2] > r->boundary[0]) &&
                	(s->boundary[0] < r->boundary[0]));
	if (x==12)
        	return (s->boundary[2] == r->boundary[0]);
	if (x==13)
        	return (s->boundary[2] < r->boundary[0]);
}



/******************************************************************************
***********************   DIRECTION RELATIONS *********************************
*******************************************************************************/

/*-----------------------------------------------------------------------------
| Strong_North(r, s, ndims)
|       Decide whether rect s is Strong_North of rect r.
-----------------------------------------------------------------------------*/
Strong_North(r, s, ndims)
register struct Rect    *r, *s;
int                     ndims;
{
        assert(r && s);
        return (s->boundary[1] > r->boundary[3]);
}

Strong_North1(r, s, ndims)
register struct Rect    *r, *s;
int                     ndims;
{
        assert(r && s);
        return (s->boundary[3] > r->boundary[3]);
}

/*-----------------------------------------------------------------------------
| Weak_North(r, s, ndims)
|       Decide whether rect s is Weak_North of rect r.
-----------------------------------------------------------------------------*/
Weak_North(r, s, ndims)
register struct Rect    *r, *s;
int                     ndims;
{
        assert(r && s);
        return ((s->boundary[3] > r->boundary[3]) &&
                (s->boundary[1] > r->boundary[1]) &&
                (s->boundary[1] < r->boundary[3]));
}

Weak_North1(r, s, ndims)
register struct Rect    *r, *s;
int                     ndims;
{
        assert(r && s);
        return ((s->boundary[3] > r->boundary[3]) &&
                (s->boundary[1] < r->boundary[3]));
}

/*-----------------------------------------------------------------------------
| Strong_Bounded_North(r, s, ndims)
|       Decide whether rect s is Strong_Bounded_North of rect r.
-----------------------------------------------------------------------------*/
Strong_Bounded_North(r, s, ndims)
register struct Rect    *r, *s;
int                     ndims;
{
        assert(r && s);
        return ((s->boundary[1] > r->boundary[3]) &&
                (s->boundary[1] > r->boundary[1]) &&
                (s->boundary[0] > r->boundary[0]) &&
                (s->boundary[2] < r->boundary[2]) &&
                (s->boundary[3] > r->boundary[3]));
}

Strong_Bounded_North1(r, s, ndims)
register struct Rect    *r, *s;
int                     ndims;
{
        assert(r && s);
        return ((s->boundary[3] > r->boundary[3]) &&
                (s->boundary[0] < r->boundary[2]) &&
                (s->boundary[2] > r->boundary[0]));
}

/*-----------------------------------------------------------------------------
| Weak_Bounded_North(r, s, ndims)
|       Decide whether rect s is Weak_Bounded_North of rect r.
-----------------------------------------------------------------------------*/
Weak_Bounded_North(r, s, ndims)
register struct Rect    *r, *s;
int                     ndims;
{
        assert(r && s);
        return ((s->boundary[3] > r->boundary[3]) &&
                (s->boundary[1] < r->boundary[3]) &&
                (s->boundary[0] > r->boundary[0]) &&
                (s->boundary[1] > r->boundary[1]) &&
                (s->boundary[2] < r->boundary[2]));
}

Weak_Bounded_North1(r, s, ndims)
register struct Rect    *r, *s;
int                     ndims;
{
        assert(r && s);
        return ((s->boundary[3] > r->boundary[3]) &&
                (s->boundary[1] < r->boundary[3]) &&
                (s->boundary[0] < r->boundary[2]) &&
                (s->boundary[2] > r->boundary[0]));
}

/*-----------------------------------------------------------------------------
| Strong_NorthEast(r, s, ndims)
|       Decide whether rect s is Strong_NorthEast of rect r.
-----------------------------------------------------------------------------*/
Strong_NorthEast(r, s, ndims)
register struct Rect    *r, *s;
int                     ndims;
{
        assert(r && s);
        return ((s->boundary[1] > r->boundary[3]) &&
                (s->boundary[0] > r->boundary[2]));
}

Strong_NorthEast1(r, s, ndims)
register struct Rect    *r, *s;
int                     ndims;
{
        assert(r && s);
        return ((s->boundary[3] > r->boundary[3]) &&
                (s->boundary[2] > r->boundary[2]));
}

/*-----------------------------------------------------------------------------
| Weak_NorthEast(r, s, ndims)
|       Decide whether rect s is Weak_NorthEast of rect r.
-----------------------------------------------------------------------------*/
Weak_NorthEast(r, s, ndims)
register struct Rect    *r, *s;
int                     ndims;
{
        assert(r && s);
        return ((s->boundary[3] > r->boundary[3]) &&
                (s->boundary[2] > r->boundary[2]) &&
                (s->boundary[1] > r->boundary[1]) &&
                (s->boundary[0] > r->boundary[0]) &&
                (s->boundary[1] < r->boundary[3]));
}

Weak_NorthEast1(r, s, ndims)
register struct Rect    *r, *s;
int                     ndims;
{
        assert(r && s);
        return ((s->boundary[3] > r->boundary[3]) &&
                (s->boundary[2] > r->boundary[2]) &&
                (s->boundary[1] < r->boundary[3]));
}

/*-----------------------------------------------------------------------------
| Same_Level(r, s, ndims)
|       Decide whether rect s is Same_Level of rect r.
-----------------------------------------------------------------------------*/
Same_Level(r, s, ndims)
register struct Rect    *r, *s;
int                     ndims;
{
        assert(r && s);
        return ((s->boundary[1] >= r->boundary[1]) &&
                (s->boundary[3] <= r->boundary[3]));
}

Same_Level1(r, s, ndims)
register struct Rect    *r, *s;
int                     ndims;
{
        assert(r && s);
        return ((s->boundary[3] >= r->boundary[1]) &&
                (s->boundary[1] <= r->boundary[3]));
}

/*-----------------------------------------------------------------------------
| Strong_Same_Level(r, s, ndims)
|       Decide whether rect s is Strong_Same_Level of rect r.
-----------------------------------------------------------------------------*/
Strong_Same_Level(r, s, ndims)
register struct Rect    *r, *s;
int                     ndims;
{
        assert(r && s);
        return ((s->boundary[1] == r->boundary[1]) &&
                (s->boundary[3] == r->boundary[3]));
}

Strong_Same_Level1(r, s, ndims)
register struct Rect    *r, *s;
int                     ndims;
{
        assert(r && s);
        return ((s->boundary[3] >= r->boundary[1]) &&
                (s->boundary[1] <= r->boundary[3]));
}

/*-----------------------------------------------------------------------------
| Just_North(r, s, ndims)
|       Decide whether rect s is Just_North of rect r.
-----------------------------------------------------------------------------*/
Just_North(r, s, ndims)
register struct Rect    *r, *s;
int                     ndims;
{
        assert(r && s);
        return (s->boundary[1] == r->boundary[3]);
}

Just_North1(r, s, ndims)
register struct Rect    *r, *s;
int                     ndims;
{
        assert(r && s);
        return ((s->boundary[3] >= r->boundary[3]) &&
                (s->boundary[1] <= r->boundary[3]));
}

/*-----------------------------------------------------------------------------
| North_South(r, s, ndims)
|       Decide whether rect s is North_South of rect r.
-----------------------------------------------------------------------------*/
North_South(r, s, ndims)
register struct Rect    *r, *s;
int                     ndims;
{
        assert(r && s);
        return ((s->boundary[3] > r->boundary[3]) &&
                (s->boundary[1] < r->boundary[1]));
}

North_South1(r, s, ndims)
register struct Rect    *r, *s;
int                     ndims;
{
        assert(r && s);
        return ((s->boundary[3] > r->boundary[3]) &&
                (s->boundary[1] < r->boundary[1]));
}

/*-----------------------------------------------------------------------------
| North(r, s, ndims)
|       Decide whether rect s is North of rect r.
-----------------------------------------------------------------------------*/
North(r, s, ndims)
register struct Rect    *r, *s;
int                     ndims;
{
        assert(r && s);
        return ((s->boundary[3] > r->boundary[3]) &&
                (s->boundary[1] > r->boundary[1]));
}

North1(r, s, ndims)
register struct Rect    *r, *s;
int                     ndims;
{
        assert(r && s);
        return (s->boundary[3] > r->boundary[3]);
}