Re: SQL challenge

"Jan Hidders" <jan.hidders_at_REMOVETHIS.pandora.be> wrote in message news:pan.2004.07.13.19.21.51.416635_at_REMOVETHIS.pandora.be...
> > Is there an elegant SQL statement? If you say yes, then, I would think
hard
> > finding it:-)
>
> Yes, there is. We (some people in my research group) found it ourselves,
> but we had to make the assumption that not all points are in a single
> plane. Without that assumption things seem to get ugly.

Consider tetrahedron defined by 4 vertices p1, p2, p3, p4. Then, for any point p it is easily decidable if p belongs to tetrahedron interior or not. Let's call this predicate as

Inside(p, p1, p2, p3, p4)

This predicate is expected to work in the "extreme" cases when p1=p2 (or even when p1=p2=p3). Finding closed form expression for Inside(p, p1, p2, p3, p4) is left as an exercise to the reader.

Lets also introduce a convenience function

R^3 x R^3 -> R^3

Middle(pa,pb)

which returns a point half way between pa and pb.

Then, the query you are after is

select pa.x, pa.y, pa.z,

      pb.x, pb.y, pb.z
from Points pa, Points pb
where not exists (

   select 0 from Points p1, Points p2, Points p3, Points p4    where Inside(pa, p1, p2, p3, p4)
) and not exists (

   select 0 from Points p1, Points p2, Points p3, Points p4    where Inside(pb, p1, p2, p3, p4)
) and not exists (

   select 0 from Points p1, Points p2, Points p3, Points p4    where Inside(Middle(pa,pb), p1, p2, p3, p4)    and pa != p1 and pa != p2 and pa != p3 and pa != p4    and pb != p1 and pb != p2 and pb != p3 and pb != p4 )

The first 2 predicates eliminate all interior points of the polyhedra. The last predicates makes sure we include only those segments that are edges. Received on Wed Jul 14 2004 - 20:35:49 CDT