# Re: Box query

From: J M Davitt <jdavitt_at_aeneas.net>
Date: Sun, 23 Apr 2006 21:29:47 GMT

-CELKO- wrote:
> Try a slightly different approach. Begin with one dimension and
> stronger DDL:
>
> CREATE TABLE Boxes
> (box_id CHAR (1) NOT NULL,
> dim CHAR(1) NOT NULL,
> PRIMARY KEY (box_id, dim),
> low INTEGER NOT NULL,
> high INTEGER NOT NULL,
> CHECK (low < high));
>
> INSERT INTO Boxes VALUES ('A', 'x', 0, 2);
> INSERT INTO Boxes VALUES ('B', 'x', 1, 3);
> INSERT INTO Boxes VALUES ('C', 'x', 10, 12);
>
> --in 1 dimension
> SELECT B1.box_id, B2.box_id
> FROM Boxes AS B1, Boxes AS B2
> WHERE B1.box_id < B2.box_id
> AND (B1.high - B1.low) + (B2.high - B2.low)
> > ABS(B1.high - B2.low);
>
> This says that two lines segements overlap when their combined lengths
> are less than their span in the dimension. Math rather than
> between-ness.
>
> /* the cubes A={(x,0,2),(y,0,2),(z,0,2)}
> and B={(x,1,3),(y,1,3),(z,1,3)} intersect, while the box
> C={(x,10,12),(y,0,4),(z,0,100)} */
>
> let's go to 2D
>
> INSERT INTO Boxes VALUES ('A', 'y', 0, 2);
> INSERT INTO Boxes VALUES ('B', 'y', 1, 3);
> INSERT INTO Boxes VALUES ('C', 'y', 0, 4);
>
> --in 2 dimension: first shot:
> SELECT B1.box_id, B2.box_id, B1.dim
> FROM Boxes AS B1, Boxes AS B2
> WHERE B1.box_id < B2.box_id
> AND B1.dim = B2.dim
> AND (B1.high - B1.low) + (B2.high - B2.low)
> > ABS(B1.high - B2.low);
>
> Now look for a common area in (x,y) by having overlaps in both
> dimensions:
>
> SELECT B1.box_id, B2.box_id
> FROM Boxes AS B1, Boxes AS B2
> WHERE B1.box_id < B2.box_id
> AND B1.dim = B2.dim
> AND (B1.high - B1.low) + (B2.high - B2.low)
> > ABS(B1.high - B2.low)
> GROUP BY B1.box_id, B2.box_id
> HAVING COUNT(B1.dim) = 2;
>
> --3 dimensions:
>
> INSERT INTO Boxes VALUES ('A', 'z', 0, 2);
> INSERT INTO Boxes VALUES ('B', 'z', 1, 3);
> INSERT INTO Boxes VALUES ('C', 'z', 0, 100);
>
> Now change the HAVING clause to COUNT(B1.dim) = 3 or (SELECT COUNT
> (DISTINCT dim) FROM Boxes) if you do not know the space you are using.
>

The INTERSECTIONS view I described above along with the cute PRODUCT aggregate function would do things like

select box1

```,       box2
,       product(hi - lo) as volume
```

from intersections
group by 1, 2 ;

to handle the original case where we knew we had 3D things. More precisely, it should be written

select box1

```,       box2
,       product(hi - lo) as volume
```

from intersections
group by 1, 2
having 3 = count(dim) ;

and

select box1

```,       box2
,       product(hi - lo) as area
```

from intersections
group by 1, 2
having 2 = count(dim) ;

Of course, overlapping line segments should be treated as

select box1

```,       box2
,       sum(hi - lo) as length
```

from intersections
group by 1, 2
having 1 = count(dim) ;

But, you know, we wouldn't be calling those *boxes* then, would we? Received on Sun Apr 23 2006 - 23:29:47 CEST

Original text of this message