Re: SQL challenge
Date: Tue, 13 Jul 2004 17:45:00 GMT
Message-Id: <pan.2004.07.13.17.45.22.985796_at_REMOVETHIS.pandora.be>
On Mon, 12 Jul 2004 17:36:53 -0700, Mikito Harakiri wrote:
> "Jan Hidders" <jan.hidders_at_REMOVETHIS.pandora.be> wrote in message
> news:pan.2004.07.12.23.10.13.427982_at_REMOVETHIS.pandora.be...
>> At the last SIGMOD conference I heard an anecdote about how Jim Gray had >> gained the respect of some of his colleagues by computing the >> convex hull of a set of three-dimensional points in a table with a single >> SQL query that used only basic SQL (SQL-89). To be a little more concrete, >> the input is a relation P(x,y,z) and the output L(x1,y1,z1,x2,y2,z2) that >> describes the minimal set of edges that span the convex hull of the nodes >> in P.
>
> It is easier to think of the convex hull in terms of [triangular] faces
> rather than edges. Indeed, each face defines a plane that divides the space
> into 2 halves and all the points would be in the one half-space or the
> other.
>
> Suppose we have triangle with vertices (p1.x,p1.y,p1.z), (p2.x,p2.y,p2.z),
> (p3.x,p3.y,p3.z). What side of the plane some other point (p.x,p.y,p.z) is
> positioned at? It is easy to see that we have to calculate cross product of
>
> (p1.x-p2.x,p1.y-p2.y,p1.z-p2.z) and (p1.x-p3.x,p1.y-p3.y,p1.z-p3.z)
>
> and scalarly multiply it into
>
> (p1.x-p.x,p1.y-p.y,p1.z-p.z)
>
> Then the sign of the result would indicate which side of the plane the point
> is positioned at.
>
> Technically, we have to calculate determinant
>
> det(matrix(3,3,[[p1.x-p2.x,p1.y-p2.y,p1.z-p2.z],[p1.x-p3.x,p1.y-p3.y,p1.z-p3
> .z],[p1.x-p.x,p1.y-py,p1.z-p.z]]));
>
> and Mapple says that it's eqial to
>
> p1.x*p.z*p3.y-p1.x*p.y*p3.z-p2.x*p.z*p3.y+p2.x*p.z*p1.y-
> p1.x*p.z*p2.y+p2.x*p.y*p3.z-p2.x*p.y*p1.z+p1.x*p.y*p2.z+
> p3.x*p.z*p2.y-p3.x*p.z*p1.y-p.x*p2.z*p1.y-p.x*p1.z*p3.y-
> p.x*p2.y*p3.z+p.x*p2.y*p1.z+ p.x*p1.y*p3.z-p3.x*p.y*p2.z+
> p3.x*p.y*p1.z+p.x*p2.z*p3.y-p3.x*p2.y*p1.z+p3.x*p2.z*p1.y+
> p1.x*p2.y*p3.z-p1.x*p2.z*p3.y+p2.x*p1.z*p3.y-p2.x*p1.y*p3.z
Ha, Mikito. I knew I could count on you. :-) Yes this is indeed the way to do it although you can write the above a bit more succinctly as:
((p1.y-p2.y)*(p1.z-p3.z)-(p1.z-p2.z)*(p1.y-p3.y))*(p.x-p1.x) + ((p1.z-p2.z)*(p1.x-p3.x)-(p1.x-p2.x)*(p1.z-p3.z))*(p.y-p1.y) + ((p1.x-p2.x)*(p1.y-p3.y)-(p1.y-p2.y)*(p1.x-p3.x))*(p.z-p1.z)
> Therefore, we can proceed converting the above to SQL:
>
> create table points (
> X integer,
> Y integer,
> Z integer
> )
>
> delete from points;
> insert into points values (0,0,0);
> insert into points values (0,0,1);
> insert into points values (0,1,0);
> insert into points values (1,0,0);
>
> commit;
>
> select p1.x,p1.y,p1.z,
> p2.x,p2.y,p2.z,
> p3.x,p3.y,p3.z
> from points p1, points p2, points p3
> where (p1.x!=p2.x or p1.y!=p2.y or p1.z!=p2.z) // p1,p2,and p3 are distinct
> and (p1.x!=p3.x or p1.y!=p3.y or p1.z!=p3.z)
> and (p2.x!=p3.x or p2.y!=p3.y or p2.z!=p3.z)
> and (
> 0=(select count(1) from points p where
> p1.x*p.z*p3.y-p1.x*p.y*p3.z-p2.x*p.z*p3.y+p2.x*p.z*p1.y-
> p1.x*p.z*p2.y+p2.x*p.y*p3.z-p2.x*p.y*p1.z+p1.x*p.y*p2.z+
> p3.x*p.z*p2.y-p3.x*p.z*p1.y-p.x*p2.z*p1.y-p.x*p1.z*p3.y-
> p.x*p2.y*p3.z+p.x*p2.y*p1.z+ p.x*p1.y*p3.z-p3.x*p.y*p2.z+
> p3.x*p.y*p1.z+p.x*p2.z*p3.y-p3.x*p2.y*p1.z+p3.x*p2.z*p1.y+
> p1.x*p2.y*p3.z-p1.x*p2.z*p3.y+p2.x*p1.z*p3.y-p2.x*p1.y*p3.z
> > 0 )
> or
> 0=(select count(1) from points p where
> p1.x*p.z*p3.y-p1.x*p.y*p3.z-p2.x*p.z*p3.y+p2.x*p.z*p1.y-
> p1.x*p.z*p2.y+p2.x*p.y*p3.z-p2.x*p.y*p1.z+p1.x*p.y*p2.z+
> p3.x*p.z*p2.y-p3.x*p.z*p1.y-p.x*p2.z*p1.y-p.x*p1.z*p3.y-
> p.x*p2.y*p3.z+p.x*p2.y*p1.z+ p.x*p1.y*p3.z-p3.x*p.y*p2.z+
> p3.x*p.y*p1.z+p.x*p2.z*p3.y-p3.x*p2.y*p1.z+p3.x*p2.z*p1.y+
> p1.x*p2.y*p3.z-p1.x*p2.z*p3.y+p2.x*p1.z*p3.y-p2.x*p1.y*p3.z
> < 0 )
> )
>
> Finally, the remaining tiny problem is selecting edges from faces.
- Jan Hidders