# Re: Box query

Date: Sun, 23 Apr 2006 21:29:47 GMT

Message-ID: <flS2g.13381$P2.6106_at_tornado.ohiordc.rr.com>

-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